Applying quantum algorithms to constraint satisfaction problems
Open accessThe DOI matches its Crossref record; 29 of the 29 references it cites were found in a registry or an index.
Abstract
Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few cases where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. Here we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. We compare the performance of optimised versions of these algorithms, when applied to random problem instances, against leading classical algorithms. Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. In the most optimistic parameter regime we consider, this could be a factor of over 105 relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over 103. However, the number of physical qubits used is extremely large, and improved fault-tolerance methods will likely be needed to make these results practical. In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques.
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
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059 · cited 4×
“hodology used to calculate the cost of a quantum computation. 1.1 Timing and cost model Here we outline our resource methdology, which follows a model developed by several previous works in this area [3,8,10,53,78]. The model assumes that the quantum computation is encoded using the surface code [53], a quantum error-…”
BackgroundMethodInfluentialHardware-efficient variational quantum eigensolver for small molecules and quantum magnets
Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M., & Gambetta, J. M. (2017) · Nature · doi:10.1038/nature23879 · Cited by 2,982
Georgescu, I. M., Ashhab, S., & Nori, F. (2014) · Reviews of Modern Physics · doi:10.1103/revmodphys.86.153 · Cited by 2,932
Superconducting quantum circuits at the surface code threshold for fault tolerance
Barends, R., Kelly, J., Megrant, A., Veitia, A., Sank, D., Jeffrey, E., White, T. C., Mutus, J., Fowler, A. G., Campbell, B., et al. (2014) · Nature · doi:10.1038/nature13171 · Cited by 1,733
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680
Universal quantum computation with ideal Clifford gates and noisy ancillas
Bravyi, S., & Kitaev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.022316 · Cited by 1,525 · cited 2×
“Toffoli and T gates can be implemented faulttolerantly using a state injection technique where a special state is prepared offline (a Toffoli state [48, 61] or T state [27]), and then used to implement the corresponding gate.”
MethodStrengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · cited 1×
“This is close to optimal, as even under the promise that S = 1, Ω( √ N) evaluations of f are required to find the unique x such that f(x) = 1 with high probability [19, 96].”
BackgroundHigh-Fidelity Quantum Logic Gates Using Trapped-Ion Hyperfine Qubits
Ballance, C. J., Harty, T. P., Linke, N. M., Sepiol, M. A., & Lucas, D. M. (2016) · Physical Review Letters · doi:10.1103/physrevlett.117.060504 · Cited by 777
Elucidating reaction mechanisms on quantum computers
Reiher, M., Wiebe, N., Svore, K. M., Wecker, D., & Troyer, M. (2017) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1619152114 · Cited by 745 · cited 2×
“Examples include simulating the chemical processes involved in biological nitrogen fixation [84]; breaking cryptosystems based on integer factorisation [58, 75] and elliptic curves [86]; quantum simulation of spin systems [37] and electronic structure Hamiltonians [10].”
BackgroundMethodQuantum lower bounds by polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2001) · Journal of the ACM · doi:10.1145/502090.502097 · Cited by 639
Grover’s quantum searching algorithm is optimal
Zalka, C. (1999) · Physical Review A · doi:10.1103/physreva.60.2746 · Cited by 635
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 · cited 1×
“[85]) or the quantum approximate optimisation algorithm [49].”
BackgroundSurface code quantum computing by lattice surgery
Horsman, D., Fowler, A. G., Devitt, S., & Meter, R. V. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/12/123011 · Cited by 598 · cited 1×
“There is potential to cut these numbers in half by using the rotated surface code [59] but it is currently unknown whether the error suppression still obeys ∼ d (100 p g ) ( d +1) / 2 so we instead opt for a conservative, well-supported estimate.”
BackgroundRoads towards fault-tolerant universal quantum computation
Campbell, E. T., Terhal, B. M., & Vuillot, C. (2017) · Nature · doi:10.1038/nature23460 · Cited by 596
Self-citationToward the first quantum simulation with quantum speedup
Childs, A. M., Maslov, D., Nam, Y., Ross, N. J., & Su, Y. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801723115 · Cited by 551
A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits
Amy, M., Maslov, D., Mosca, M., & Roetteler, M. (2013) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2013.2244643 · Cited by 549 · cited 2×
“xistence). Preliminary calculations suggest that replacing controlled operations with uncontrolled ones could reduce the runtime by up to ∼20%. An automated circuit optimisation tool, such as T-par [7], could be used to reduce the complexity of the quantum circuits developed, and to check correctness. It is not obviou…”
BackgroundMethodOn the Relationship Between Continuous- and Discrete-Time Quantum Walk
Childs, A. M. (2010) · Communications in Mathematical Physics · doi:10.1007/s00220-009-0930-1 · Cited by 411 · cited 1×
“Note that the “optimal” variant of phase estimation where a different input state is used (rather than | + (cid:105) ⊗ m ) does not seem to achieve a significantly better bound when m is close to its minimal value (see e.g. the analysis in [36]).”
BackgroundEncoding Electronic Spectra in Quantum Circuits with Linear T Complexity
Babbush, R., Gidney, C., Berry, D. W., Wiebe, N., McClean, J., Paler, A., Fowler, A., & Neven, H. (2018) · Physical Review X · doi:10.1103/physrevx.8.041015 · Cited by 383 · cited 4×
“Examples include simulating the chemical processes involved in biological nitrogen fixation [84]; breaking cryptosystems based on integer factorisation [58, 75] and elliptic curves [86]; quantum simulation of spin systems [37] and electronic structure Hamiltonians [10].”
BackgroundMethodInfluentialGate-count estimates for performing quantum chemistry on small quantum computers
Wecker, D., Bauer, B., Clark, B. K., Hastings, M. B., & Troyer, M. (2014) · Physical Review A · doi:10.1103/physreva.90.022305 · Cited by 296
Halving the cost of quantum addition
Gidney, C. (2018) · Quantum · doi:10.22331/q-2018-06-18-74 · Cited by 279 · cited 1×
“However, almost half of these gates can be replaced with classically controlled Clifford gates using the “uncompute AND” operation described in [56], to give a circuit containing c−1 Toffoli gates.”
MethodA survey of recent advances in SAT-based formal verification
Prasad, M. R., Biere, A., & Gupta, A. (2005) · International Journal on Software Tools for Technology Transfer · doi:10.1007/s10009-004-0183-4 · Cited by 279
Quantum Attacks on Bitcoin, and How to Protect Against Them
Aggarwal, D., Brennen, G., Lee, T., Santha, M., & Tomamichel, M. (2018) · Ledger · doi:10.5195/ledger.2018.127 · Cited by 231
Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms
Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-70697-9_9 · Cited by 212 · cited 1×
“Examples include simulating the chemical processes involved in biological nitrogen fixation [84]; breaking cryptosystems based on integer factorisation [58, 75] and elliptic curves [86]; quantum simulation of spin systems [37] and electronic structure Hamiltonians [10].”
MethodQuantum computation with realistic magic-state factories
O'Gorman, J., & Campbell, E. T. (2017) · Physical Review A · doi:10.1103/physreva.95.032338 · Cited by 158
Self-citationEfficient Synthesis of Universal Repeat-Until-Success Quantum Circuits
Bocharov, A., Roetteler, M., & Svore, K. M. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.080502 · Cited by 142 · cited 2×
“2), and the complexity of a circuit synthesis step used in the algorithm is also problem-dependent [22] (see Section 4.”
BackgroundMethodEstimating the Cost of Generic Quantum Pre-image Attacks on SHA-2 and SHA-3
Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., & Schanck, J. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-69453-5_18 · Cited by 128 · cited 4×
“For reasonable graph sizes (e.g. n ∈ { 100 , . . . , 200 } ) it is less than 4 × 10 6 , and hence not substantially greater than the overhead of the SHA-256 hash function implemented in [8].”
BackgroundMethodInfluentialTime-optimal quantum computation
Fowler, A. G. (2012) · arXiv · doi:10.48550/arxiv.1210.4626 · Cited by 45
Cited by
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830
Quantum computing for finance: Overview and prospects
Orús, R., Mugel, S., & Lizaso, E. (2019) · Reviews in Physics · doi:10.1016/j.revip.2019.100028 · Cited by 668
Exponential suppression of bit or phase errors with cyclic error correction
Google Quantum, A. I., Chen, Z., Satzinger, K. J., Atalaya, J., Korotkov, A. N., Dunsworth, A., Sank, D., Quintana, C., McEwen, M., Barends, R., et al. (2021) · Nature · doi:10.1038/s41586-021-03588-y · Cited by 393
Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes
Chamberland, C., Noh, K., Arrangoiz-Arriola, P., Campbell, E. T., Hann, C. T., Iverson, J., Putterman, H., Bohdanowicz, T. C., Flammia, S. T., Keller, A., et al. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010329 · Cited by 281
Self-citationFocus beyond Quadratic Speedups for Error-Corrected Quantum Advantage
Babbush, R., McClean, J. R., Newman, M., Gidney, C., Boixo, S., & Neven, H. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.010103 · Cited by 148
“Campbell et al.[7] were the first to detail poor prospects for error correcting an algorithm achieving”
Background
Metadata
- Authors
- Campbell, E., Khurana, A., & Montanaro, A.
- Venue
- Quantum
- Published
- 2019-07-18
- Volume
- 3
- Pages
- 167
- ISSN
- 2521-327X (ISSN-L)
- OpenAlex
- W2897906876
- Cited by
- 76
- References
- 29
- FWCI
- 4.14
- Type
- journal article
- Language
- en
- Open access
- gold
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.