TY - JOUR
T1 - Mapping constrained optimization problems to quantum annealing with application to fault diagnosis
Y1 - 2016
A1 - Bian, Zhengbing
A1 - Chudak, Fabian
A1 - Israel, Robert
A1 - Lackey, Brad
A1 - Macready, William G
A1 - Roy, Aidan
AB - 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. In 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 D-Wave's QA hardware using the local mapping technique is significantly better than global embedding. We validate the approach by applying D-Wave's 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 1000N samples, using an annealing rate that is 25 times faster than a leading SAT-based sampling method. Further, 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.
UR - http://arxiv.org/abs/1603.03111
ER -
TY - JOUR
T1 - Discrete optimization using quantum annealing on sparse Ising models
JF - Frontiers in Physics
Y1 - 2014
A1 - Bian, Zhengbing
A1 - Chudak, Fabian
A1 - Israel, Robert
A1 - Brad Lackey
A1 - Macready, William G
A1 - Roy, Aidan
AB - This 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.
PB - Frontiers
VL - 2
U4 - 56
ER -