CoChat
Sign Up
PreprintCited by 39Quantum Computing Algorithms and ArchitectureMetaheuristic Optimization Algorithms ResearchDNA and Biological Computing

Algorithm engineering for a quantum annealing platform

Open access
King, Andrew D., McGeoch, Catherine C.·2014·arXiv
DOI 10.48550/arxiv.1410.2628arXiv 1410.2628
Open this paper in CoChat — free accountOpen PDF

Abstract

Recent advances bring within reach the viability of solving combinatorial problems using a quantum annealing algorithm implemented on a purpose-built platform that exploits quantum properties. However, the question of how to tune the algorithm for most effective use in this framework is not well understood. In this paper we describe some operational parameters that drive performance, discuss approaches for mitigating sources of error, and present experimental results from a D-Wave Two quantum annealing processor.

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

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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

Integrity signals

Registry

DataCite · 10.48550/arxiv.1410.2628

Cites

4 of 4 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

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

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The impact of various quantum controls, such as annealing time and number of spin reversals, on the success probability and chain breaks has been studied by Grant et al., yielding a saturation effect for both controls.

    “The impact of various quantum controls, such as annealing time and number of spin reversals [194], on the success probability and chain breaks has been studied by Grant et al. [55], yielding a saturation effect for both controls.”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [194]

Self-check

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

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

Cites

Flagged first, then by citations

Research works printed but not linked: 22

  1. [1][1] D. Achlioptas, A. Chtcherba, G. Istrate, and C. Moore. The phase transition in 1-in-k SAT and NAE 3-SAT. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 721-722. Society for Industrial and Applied Mathematics, 2001. -
  2. [2][2] D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev. Adiabatic quantum computation is equivalent to standard quantum computation. SIAM Journal on Computing , 37(1):166-194, 2007. -
  3. [3][3] T. Albash, S. Boixo, D.A. Lidar, and P. Zanardi. Quantum adiabatic Markovian master equations. New Journal of Physics , 14(12):123016, 2012. -
  4. [4][4] P. Berman and M. Karpinski. On some tighter inapproximability results. In Proceedings of the 26th International Colloquium on Automata, Languages and Programming , pages 200-209. Springer-Verlag, 1999. -
  5. [7][7] P. Bunyk, E. Hoskinson, M. Johnson, E. Tolkacheva, F. Altomare, A. Berkley, R. Harris, J. Hilton, T. Lanting, A. Przybysz, et al. Architectural considerations in the design of a superconducting quantum annealing processor. IEEE Transactions on Applied Superconductivity , 2014. -
  6. [8][8] J. Cai, W.G. Macready, and A. Roy. A practical heuristic for finding graph minors. arXiv preprint arXiv:1406.2741 , 2014. - · arXiv
  7. [9][9] V. Choi. Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Information Processing , 7(5):193-209, 2008. -
  8. [10][10] A. Das and B.K. Chakrabarti. Quantum annealing and related optimization methods , volume 679 of Lecture Notes in Physics . Springer, 2005. -
  9. [13][13] E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda. A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science , 292(5516):472-475, 2001. -
  10. [15][15] S. Istrail. Statistical mechanics, three-dimensionality and NP-completeness: I. Universality of intracatability for the partition function of the Ising model across non-planar surfaces. In Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages 87-96. ACM, 2000. -
  11. [16][16] S.P. Jordan, E. Farhi, and P.W. Shor. Error-correcting codes for adiabatic quantum computation. Physical Review A , 74(5):052322, 2006. -
  12. [18][18] H.G. Katzgraber, F. Hamze, and R.S. Andrist. Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines. Physical Review X , 4(2):021008, 2014. -
  13. [20][20] R. Martoˇ n´ ak, G.E. Santoro, and E. Tosatti. Quantum annealing by the path-integral Monte Carlo method: The two-dimensional random Ising model. Physical Review B , 66(9):094203, 2002. -
  14. [21][21] C.C. McGeoch. A guide to experimental algorithmics . Cambridge University Press, 2012. -
  15. [22][22] C.C. McGeoch. Adiabatic quantum computation and quantum annealing: Theory and practice. Synthesis Lectures on Quantum Computing , 5(2):1-93, 2014. -
  16. [23][23] C.C. McGeoch and C. Wang. Experimental evaluation of an adiabiatic quantum system for combinatorial optimization. In Proceedings of the ACM International Conference on Computing Frontiers , page 23. ACM, 2013. -
  17. [24][24] M. M¨ uller-Hannemann and S. Schirra. Algorithm engineering: bridging the gap between algorithm theory and practice , volume 5971. Springer, 2010. -
  18. [25][25] H. Nishimori, J. Tsuda, and S. Knysh. Comparative study of the performance of quantum annealing and simulated annealing. arXiv preprint arXiv:1409.6386 , 2014. - · arXiv
  19. [27][27] K.L. Pudenz, T. Albash, and D.A. Lidar. Quantum annealing correction for random Ising problems. arXiv preprint arXiv:1408.4382 , 2014. - · arXiv
  20. [29][29] T.F. Rønnow, Z. Wang, J. Job, S. Boixo, S.V. Isakov, D. Wecker, J.M. Martinis, D.A. Lidar, and M. Troyer. Defining and detecting quantum speedup. Science , 345(6195):420-424, 2014. -
  21. [31][31] W. Vinci, T. Albash, A. Mishra, P.A. Warburton, and D.A. Lidar. Distinguishing classical and quantum models for the D-Wave device. arXiv preprint arXiv:1403.4228 , 2014. - · arXiv
  22. [32][32] K.C. Young, R. Blume-Kohout, and D.A. Lidar. Adiabatic quantum optimization with the wrong Hamiltonian. Physical Review A , 88(6):062314, 2013. Figure 7: A single Chimera cell, K 4 , 4 . <!-- image -->

Cited by

Sorted by citations

Authors
King, A. D., & McGeoch, C. C.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2014
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1410.2628
arXiv
1410.2628
OpenAlex
W1507545366
Cited by
39
References
4
Citations by year
2024: 1 · 2023: 4 · 2022: 2 · 2021: 6 · 2020: 2 · 2019: 3 · 2018: 2 · 2017: 2 · 2016: 8 · 2015: 9
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › DNA and Biological Computing
Keywords
quantum annealing, algorithm engineering, combinatorial optimization, error mitigation, performance tuning

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