Current quantum annealing (QA) hardware suffers from practical limitations such as finite temperature, sparse connectivity, small qubit numbers, and control error. We propose new algorithms for mapping Boolean constraint satisfaction problems (CSPs) onto QA hardware mitigating these limitations. In particular, we develop a new embedding algorithm for mapping a CSP onto a hardware Ising model with a fixed sparse set of interactions and propose two new decomposition algorithms for solving problems too large to map directly into hardware. The mapping technique is locally structured, as hardware compatible Ising models are generated for each problem constraint, and variables appearing in different constraints are chained together using ferromagnetic couplings. By contrast, global embedding techniques generate a hardware-independent Ising model for all the constraints, and then use a minor-embedding algorithm to generate a hardware compatible Ising model. We give an example of a class of CSPs for which the scaling performance of the D-Wave hardware using the local mapping technique is significantly better than global embedding. We validate the approach by applying D- Wave’s QA hardware to circuit-based fault diagnosis. For circuits that embed directly, we find that the hardware is typically able to find all solutions from a min-fault diagnosis set of size N using 1000 N samples, using an annealing rate that is 25 times faster than a leading SAT-based sampling method. Furthermore, we apply decomposition algorithms to find min-cardinality faults for circuits that are up to 5 times larger than can be solved directly on current hardware.

1 aBian, Zhengbing1 aChudak, Fabian1 aIsrael, Robert, Brian1 aLackey, Brad1 aMacready, William, G1 aRoy, Aiden uhttp://journal.frontiersin.org/article/10.3389/fict.2016.00014/full01371nas a2200193 4500008004100000245007300041210006900114260002600183300000700209490000600216520073500222100002000957700001900977700001900996700001701015700002501032700001501057856010501072 2014 eng d00aDiscrete optimization using quantum annealing on sparse Ising models0 aDiscrete optimization using quantum annealing on sparse Ising mo bFrontiersc2014/09/01 a560 v23 aThis paper discusses techniques for solving discrete optimization problems using quantum annealing. Practical issues likely to affect the computation include precision limitations, finite temperature, bounded energy range, sparse connectivity, and small numbers of qubits. To address these concerns we propose a way of finding energy representations with large classical gaps between ground and first excited states, efficient algorithms for mapping non-compatible Ising models into the hardware, and the use of decomposition methods for problems that are too large to fit in hardware. We validate the approach by describing experiments with D-Wave quantum hardware for low density parity check decoding with up to 1000 variables.1 aBian, Zhengbing1 aChudak, Fabian1 aIsrael, Robert1 aLackey, Brad1 aMacready, William, G1 aRoy, Aidan uhttps://quics.umd.edu/publications/discrete-optimization-using-quantum-annealing-sparse-ising-models