CoChat

Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis

Open access
Bian, Zhengbing, Chudak, Fabian, Israel, Robert Brian, Lackey, Brad, Macready, William G., Roy, Aidan · 2016 · Frontiers in ICT
Cited by 87

The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.

Abstract

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 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 \emph{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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.3389/fict.2016.00014

Cites

8 of 8 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

  • Quantum annealing in the transverse Ising model

    Kadowaki, T., & Nishimori, H. (1998) · Physical Review E · doi:10.1103/physreve.58.5355 · Cited by 2,339 · cited 1×

    “Quantum annealing (QA) is an optimization heuristic sharing much in common with simulated annealing, but which utilizes quantum, rather than thermal, fluctuations to foster exploration through a search space (Finilla et al., 1994; Kadowaki and Nishimori, 1998; Farhi et al., 2000).”
    Background
  • Quantum annealing with manufactured spins

    Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891 · cited 1×

    “]. 1 arXiv:1603.03111v1 [quant-ph] 10 Mar 2016 QA hardware relies on an equivalence between a physical quantum model and a useful computational problem. The low energy physics of the D-Wave QA device [2,10,20,22] is well captured by a time-dependent Hamiltonian of the form H(t) = A(t)H 0 + B(t)H P where H 0 = P i2V(G)…”
    Background
  • Pseudo-Boolean optimization

    Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827 · cited 1×

    “Ising models were pre-processed with roof-duality (Boros and Hammer, 2002) and arc-consistency (Mackworth, 1977), allowing certain variables to be fixed in polynomial time.”
    Method
  • Defining and detecting quantum speedup

    Rønnow, T. F., Wang, Z., Job, J., Boixo, S., Isakov, S. V., Wecker, D., Martinis, J. M., Lidar, D. A., & Troyer, M. (2014) · Science · doi:10.1126/science.1252319 · Cited by 601

  • Quantum Computation by Adiabatic Evolution

    Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000) · arXiv · doi:10.48550/arxiv.quant-ph/0001106 · Cited by 536 · cited 1×

    “m annealing (QA) is an optimization heuristic sharing much in common with simulated annealing, but which utilizes quantum, rather than thermal, uctuations to foster exploration through a search space [14,23,12]. 1 arXiv:1603.03111v1 [quant-ph] 10 Mar 2016 QA hardware relies on an equivalence between a physical quantum…”
    Background
  • Quantum Optimization of Fully Connected Spin Glasses

    Venturelli, D., Mandrà, S., Knysh, S., O’Gorman, B., Biswas, R., & Smelyanskiy, V. (2015) · Physical Review X · doi:10.1103/physrevx.5.031040 · Cited by 209 · cited 2×

    “The performance of D-Wave’s hardware in solving an embedded Ising model depends heavily on the size of the chains of variables: shorter chains are more likely to yield better performance [48].”
    Background
  • Experimental demonstration of a robust and scalable flux qubit

    Harris, R., Johansson, J., Berkley, A. J., Johnson, M. W., Lanting, T., Han, S., Bunyk, P., Ladizinsky, E., Oh, T., Perminov, I., et al. (2010) · Physical Review B · doi:10.1103/physrevb.81.134510 · Cited by 177 · cited 1×

    “The low energy physics of the D-Wave QA device [2, 10, 20, 22] is well captured by a time-dependent Hamiltonian of the form H(t) = A(t)H0 + B(t)HP where H0 = ∑ i∈V (G) σ x i includes off-diagonal quantum effects, and where HP = ∑ i∈V (G) hiσ z i + ∑ (i,j)∈E(G) Ji,jσ z i σ z j is used to encode a classical Ising optimi…”
    Method
  • Algorithm engineering for a quantum annealing platform

    King, A. D., & McGeoch, C. C. (2014) · arXiv · doi:10.48550/arxiv.1410.2628 · Cited by 39

Show all 8 references

Cited by

See all 87

Metadata

Authors
Bian, Z., Chudak, F., Israel, R. B., Lackey, B., Macready, W. G., & Roy, A.
Venue
Frontiers in ICT
Published
2016-07-28
Volume
3
ISSN
2297-198X (ISSN-L)
OpenAlex
W2403611064
Cited by
87
References
8
FWCI
8.58
Type
journal article
Language
en
Open access
diamond

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis. https://app.cochat.ai/papers/10.3389/fict.2016.00014
The paper
Bian, Z., Chudak, F., Israel, R. B., Lackey, B., Macready, W. G., & Roy, A. (2016). Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis. Frontiers in ICT. https://doi.org/10.3389/fict.2016.00014

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.