Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis
Open accessThe 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.
Integrity signals
Registry
Cites
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.
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).”
BackgroundQuantum 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)…”
BackgroundBoros, 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.”
MethodDefining 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…”
BackgroundQuantum 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].”
BackgroundExperimental 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…”
MethodAlgorithm engineering for a quantum annealing platform
King, A. D., & McGeoch, C. C. (2014) · arXiv · doi:10.48550/arxiv.1410.2628 · Cited by 39
Cited by
Quantum annealing for industry applications: introduction and review
Yarkoni, S., Raponi, E., Bäck, T., & Schmitt, S. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac8c54 · Cited by 341
“Furthermore, it has been shown how to design optimal penalty terms for CSPs to minimize the error for quantum annealers [20].”
Benchmarking Quantum Annealing Controls with Portfolio Optimization
Grant, E., Humble, T. S., & Stump, B. (2021) · Physical Review Applied · doi:10.1103/physrevapplied.15.014012 · Cited by 90
“gov Hamiltonian and embedding onto the quantum annealer [22, 23], the annealing controls drive the time-dependent physics of the device and the underlying quantum state [20, 24] while post-processing controls influence the readout and decoding of the observed results [25, 26].”
BackgroundMethodA cross-disciplinary introduction to quantum annealing-based algorithms
Venegas-Andraca, S. E., Cruz-Santos, W., McGeoch, C., & Lanzagorta, M. (2018) · Contemporary Physics · doi:10.1080/00107514.2018.1450720 · Cited by 83
Readiness of Quantum Optimization Machines for Industrial Applications
Perdomo-Ortiz, A., Feldman, A., Ozaeta, A., Isakov, S. V., Zhu, Z., O’Gorman, B., Katzgraber, H. G., Diedrich, A., Neven, H., de Kleer, J., et al. (2019) · Physical Review Applied · doi:10.1103/physrevapplied.12.014004 · Cited by 62
“[29] have also used fault diagnosis as a test bed for benchmarking novel techniques in QA.”
Self-citationReinforcement Quantum Annealing: A Hybrid Quantum Learning Automata
Ayanzadeh, R., Halem, M., & Finin, T. (2020) · Scientific Reports · doi:10.1038/s41598-020-64078-1 · Cited by 57
Hybrid Annealing Method Based on subQUBO Model Extraction With Multiple Solution Instances
Atobe, Y., Tawada, M., & Togawa, N. (2022) · IEEE Transactions on Computers · doi:10.1109/tc.2021.3138629 · Cited by 38
“Note that several studies proposed subQUBO model extraction methods for specific problems, such as the maxi-mum-clique problem in [24], [25], [26], the constraint satisfaction problem in [27], and the maximum constraint satisfaction problem in [28].”
Background
Metadata
- Authors
- Bian, Z., Chudak, F., Israel, R. B., Lackey, B., Macready, W. G., & Roy, A.
- Venue
- Frontiers in ICT
- Publisher
- Frontiers Media SA
- 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
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.