{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T09:39:31Z","timestamp":1784367571483,"version":"3.55.0"},"reference-count":97,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2019,7,18]],"date-time":"2019-07-18T00:00:00Z","timestamp":1563408000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mn>10<\/mml:mn><mml:mn>5<\/mml:mn><\/mml:msup><\/mml:math> relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mn>10<\/mml:mn><mml:mn>3<\/mml:mn><\/mml:msup><\/mml:math>. 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.<\/jats:p>","DOI":"10.22331\/q-2019-07-18-167","type":"journal-article","created":{"date-parts":[[2019,7,18]],"date-time":"2019-07-18T09:12:54Z","timestamp":1563441174000},"page":"167","source":"Crossref","is-referenced-by-count":66,"title":["Applying quantum algorithms to constraint satisfaction problems"],"prefix":"10.22331","volume":"3","author":[{"given":"Earl","family":"Campbell","sequence":"first","affiliation":[{"name":"Department of Physics and Astronomy, University of Sheffield, Sheffield, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ankur","family":"Khurana","sequence":"additional","affiliation":[{"name":"Quantum Engineering Centre for Doctoral Training, University of Bristol, UK"},{"name":"School of Physics, University of Bristol, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashley","family":"Montanaro","sequence":"additional","affiliation":[{"name":"School of Mathematics, University of Bristol, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2019,7,18]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Source code and experimental results. 2019. 10.5523\/bris.19va21gun3c7629f291kmd6w37.","DOI":"10.5523\/bris.19va21gun3c7629f291kmd6w37"},{"key":"1","doi-asserted-by":"publisher","unstructured":"K. Aardal, S. van Hoesel, A. Koster, C. Mannino, and A. Sassano. Models and solution techniques for frequency assignment problems. Annals of Operations Research, 153 (1): 79-129, 2007. 10.1007\/s10479-007-0178-0.","DOI":"10.1007\/s10479-007-0178-0"},{"key":"2","doi-asserted-by":"publisher","unstructured":"D. Aggarwal, G. Brennen, T. Lee, M. Santha, and M. Tomamichel. Quantum attacks on Bitcoin, and how to protect against them. Ledger, 3: 68-90, 2017. 10.5195\/LEDGER.2018.127. arXiv:1710.10377.","DOI":"10.5195\/LEDGER.2018.127"},{"key":"3","doi-asserted-by":"publisher","unstructured":"D. Aharonov, V. Jones, and Z. Landau. A polynomial quantum algorithm for approximating the Jones polynomial. In Proc. 38th Annual ACM Symp. Theory of Computing, pages 427-436, 2006. 10.1007\/s00453-008-9168-0. quant-ph\/0511096.","DOI":"10.1007\/s00453-008-9168-0"},{"key":"4","unstructured":"E. Alkim, L. Ducas, T. P\u00f6ppelmann, and P. Schwabe. Post-quantum key exchange - a new hope. In USENIX Security Symposium, pages 327-343, 2016."},{"key":"5","doi-asserted-by":"publisher","unstructured":"A. Ambainis and M. Kokainis. Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games. In Proc. 49th Annual ACM Symp. Theory of Computing, pages 989-1002, 2017. 10.1145\/3055399.3055444.","DOI":"10.1145\/3055399.3055444"},{"key":"6","doi-asserted-by":"publisher","unstructured":"M. Amy, D. Maslov, M. Mosca, and M. Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32 (6): 818-830, 2013. 10.1109\/TCAD.2013.2244643. arXiv:1206.0758.","DOI":"10.1109\/TCAD.2013.2244643"},{"key":"7","doi-asserted-by":"publisher","unstructured":"M. Amy, O. Di Matteo, V. Gheorghiu, M. Mosca, A. Parent, and J. Schanck. Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. In Selected Areas of Cryptography (SAC) 2016, pages 317-337, 2016. 10.1007\/978-3-319-69453-5_18. arXiv:1603.09383.","DOI":"10.1007\/978-3-319-69453-5_18"},{"key":"8","doi-asserted-by":"publisher","unstructured":"S. Arunachalam and R. de Wolf. Optimizing the number of gates in quantum search. Quantum Inf. Comput., 17 (3&4): 251-261, 2017. 10.26421\/QIC17.3-4. arXiv:1512.07550.","DOI":"10.26421\/QIC17.3-4"},{"key":"9","doi-asserted-by":"publisher","unstructured":"R. Babbush, C. Gidney, D. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven. Encoding electronic spectra in quantum circuits with linear T complexity. Phys. Rev. X, 8: 041015, 2018. 10.1103\/PhysRevX.8.041015. arXiv:1805.03662.","DOI":"10.1103\/PhysRevX.8.041015"},{"key":"10","doi-asserted-by":"publisher","unstructured":"T. Balafoutis and K. Stergiou. Evaluating and improving modern variable and revision ordering strategies in CSPs. Fundamenta Informaticae, 102 (3\/4): 229-261, 2010. 10.3233\/FI-2010-307. arXiv:1008.0659.","DOI":"10.3233\/FI-2010-307"},{"key":"11","doi-asserted-by":"publisher","unstructured":"B. Balasundaram and S. Butenko. Graph domination, coloring and cliques in telecommunications. In Handbook of Optimization in Telecommunications. Springer, 2006. 10.1007\/978-0-387-30165-5_30.","DOI":"10.1007\/978-0-387-30165-5_30"},{"key":"12","doi-asserted-by":"publisher","unstructured":"C. Ballance, T. Harty, N. Linke, M. Sepiol, and D. Lucas. High-fidelity quantum logic gates using trapped-ion hyperfine qubits. Phys. Rev. Lett., 117, 2016. 10.1103\/PhysRevLett.117.060504. arXiv:1512.04600.","DOI":"10.1103\/PhysRevLett.117.060504"},{"key":"13","unstructured":"T. Balyo, M. Heule, and M. J\u00e4rvisalo. Proceedings of SAT competition 2017: Solver and benchmark descriptions, 2017."},{"key":"14","doi-asserted-by":"publisher","unstructured":"R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O'Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and J. M. Martinis. Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature, 508: 500-503, 2014. 10.1038\/nature13171. arXiv:1402.4848.","DOI":"10.1038\/nature13171"},{"key":"15","doi-asserted-by":"publisher","unstructured":"R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. J. ACM, 48 (4): 778-797, 2001. 10.1109\/SFCS.1998.743485. quant-ph\/9802049.","DOI":"10.1109\/SFCS.1998.743485"},{"key":"16","unstructured":"A. Belovs. Quantum walks and electric networks, 2013. arXiv:1302.3143."},{"key":"17","doi-asserted-by":"publisher","unstructured":"A. Belovs, A. Childs, S. Jeffery, R. Kothari, and F. Magniez. Time-efficient quantum walks for 3-distinctness. In Proc. 40th International Conference on Automata, Languages and Programming (ICALP'13), pages 105-122, 2013. 10.1007\/978-3-642-39206-1_10.","DOI":"10.1007\/978-3-642-39206-1_10"},{"key":"18","doi-asserted-by":"publisher","unstructured":"C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM J. Comput., 26 (5): 1510-1523, 1997. 10.1137\/S0097539796300933. quant-ph\/9701001.","DOI":"10.1137\/S0097539796300933"},{"key":"19","doi-asserted-by":"publisher","unstructured":"D. Bera, S. Fenner, F. Green, and S. Homer. Efficient universal quantum circuits. Quantum Inf. Comput., 10 (1): 16-28, 2010. 10.1007\/978-3-642-02882-3_42. arXiv:0804.2429.","DOI":"10.1007\/978-3-642-02882-3_42"},{"key":"20","unstructured":"D. Bernstein and T. Lange (editors). ebacs: Ecrypt benchmarking of cryptographic systems, accessed 27 June 2018. http:\/\/bench.cr.yp.to."},{"key":"21","doi-asserted-by":"publisher","unstructured":"A. Bocharov, M. Roetteler, and K. Svore. Efficient synthesis of universal repeat-until-success quantum circuits. Phys. Rev. Lett., 114: 080502, 2015. 10.1103\/PhysRevLett.114.080502. arXiv:1404.5320.","DOI":"10.1103\/PhysRevLett.114.080502"},{"key":"22","doi-asserted-by":"publisher","unstructured":"B. Bollob\u00e1s. The chromatic number of random graphs. Combinatorica, 8 (1): 49-55, 1988. 10.1007\/BF02122551.","DOI":"10.1007\/BF02122551"},{"key":"23","doi-asserted-by":"publisher","unstructured":"M. Boyer, G. Brassard, P. H\u00f8yer, and A. Tapp. Tight bounds on quantum searching. Fortschr. Phys., 46 (4-5): 493-505, 1998. 10.1002\/3527603093.ch10. quant-ph\/9605034.","DOI":"10.1002\/3527603093.ch10"},{"key":"24","doi-asserted-by":"publisher","unstructured":"G. Brassard, P. H\u00f8yer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Quantum Computation and Quantum Information: A Millennium Volume, pages 53-74, 2002. 10.1090\/conm\/305\/05215. quant-ph\/0005055.","DOI":"10.1090\/conm\/305\/05215"},{"key":"25","doi-asserted-by":"publisher","unstructured":"S. Bravyi and J. Haah. Magic-state distillation with low overhead. Physical Review A, 86 (5): 052329, 2012. 10.1103\/PhysRevA.86.052329.","DOI":"10.1103\/PhysRevA.86.052329"},{"key":"26","doi-asserted-by":"publisher","unstructured":"S. Bravyi and A. Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A, 71: 022316, 2005. 10.1103\/PhysRevA.71.022316. quant-ph\/0403025.","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"27","doi-asserted-by":"publisher","unstructured":"D. Br\u00e9laz. New methods to color the vertices of a graph. C. ACM, 22 (4): 251-256, 1979. 10.1145\/359094.359101.","DOI":"10.1145\/359094.359101"},{"key":"28","doi-asserted-by":"publisher","unstructured":"C. Brown and P. Purdom, Jr. An average time analysis of backtracking. SIAM J. Comput., 10 (3): 583-593, 1981. 10.1137\/0210043.","DOI":"10.1137\/0210043"},{"key":"29","doi-asserted-by":"publisher","unstructured":"C. Cade, A. Montanaro, and A. Belovs. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. Quantum Inf. Comput., 18 (1&2): 18-50, 2018. 10.26421\/QIC18.1-2. arXiv:1610.00581.","DOI":"10.26421\/QIC18.1-2"},{"key":"30","doi-asserted-by":"publisher","unstructured":"E. Campbell and M. Howard. Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost. Physical Review A, 95 (2): 022316, 2017a. 10.1103\/PhysRevA.95.022316.","DOI":"10.1103\/PhysRevA.95.022316"},{"key":"31","doi-asserted-by":"publisher","unstructured":"E. Campbell and M. Howard. Unifying gate synthesis and magic state distillation. Physical review letters, 118 (6): 060501, 2017b. 10.1103\/PhysRevLett.118.060501.","DOI":"10.1103\/PhysRevLett.118.060501"},{"key":"32","doi-asserted-by":"publisher","unstructured":"E. Campbell and M. Howard. Magic state parity-checker with pre-distilled components. Quantum, 2: 56, 2018. 10.22331\/q-2018-03-14-56.","DOI":"10.22331\/q-2018-03-14-56"},{"key":"33","doi-asserted-by":"publisher","unstructured":"E. Campbell, B. Terhal, and C. Vuillot. Roads towards robust and universal quantum computation. Nature, 549: 172-179, 2017. 10.1038\/nature23460. arXiv:1612.07330.","DOI":"10.1038\/nature23460"},{"key":"34","unstructured":"P. Cheeseman, B. Kanefsky, and W. Taylor. Where the really hard problems are. In Proc. IJCAI '91, pages 331-337, 1991."},{"key":"35","doi-asserted-by":"publisher","unstructured":"A. Childs. On the relationship between continuous- and discrete-time quantum walk. Comm. Math. Phys., 294: 581-603, 2010. 10.1007\/s00220-009-0930-1. arXiv:0810.0312.","DOI":"10.1007\/s00220-009-0930-1"},{"key":"36","doi-asserted-by":"publisher","unstructured":"A. Childs, D. Maslov, Y. Nam, N. Ross, and Y. Su. Toward the first quantum simulation with quantum speedup. Proc. Natl. Acad. Sci., 115 (38): 9456-9461, 2018. 10.1073\/pnas.1801723115. arXiv:1711.10980.","DOI":"10.1073\/pnas.1801723115"},{"key":"37","doi-asserted-by":"publisher","unstructured":"F. Chow and J. Hennessy. The priority-based coloring approach to register allocation. ACM Transactions on Programming Languages and Systems, 12 (4): 501-536, 1990. 10.1145\/88616.88621.","DOI":"10.1145\/88616.88621"},{"key":"38","doi-asserted-by":"publisher","unstructured":"R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proc. R. Soc. Lond. A, 454 (1969): 339-354, 1998. 10.1098\/rspa.1998.0164. quant-ph\/9708016.","DOI":"10.1098\/rspa.1998.0164"},{"key":"39","doi-asserted-by":"publisher","unstructured":"A. Coja-Oghlan and K. Panagiotou. Going after the k-SAT threshold. In Proc. 45th Annual ACM Symp. Theory of Computing, pages 705-714, 2013. 10.1145\/2488608.2488698. arXiv:1212.1682.","DOI":"10.1145\/2488608.2488698"},{"key":"40","doi-asserted-by":"publisher","unstructured":"M. Davis and H. Putnam. A computing procedure for quantification theory. J. ACM, 7 (3): 201-215, 1960. 10.1007\/978-3-642-81952-0_9.","DOI":"10.1007\/978-3-642-81952-0_9"},{"key":"41","doi-asserted-by":"publisher","unstructured":"M. Davis, G. Logemann, and D. Loveland. A machine program for theorem proving. C. ACM, 5 (7): 394-397, 1962. 10.1007\/978-3-642-81952-0_16.","DOI":"10.1007\/978-3-642-81952-0_16"},{"key":"42","unstructured":"R. Dechter and I. Meiri. Experimental evaluation of preprocessing techniques in constraint satisfaction problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-1989), pages 271-277, 1989."},{"key":"43","unstructured":"N. Delfosse and N. Nickerson. Almost-linear time decoding algorithm for topological codes, 2017. arXiv:1709.06218."},{"key":"44","doi-asserted-by":"publisher","unstructured":"X.-H. Deng, E. Barnes, and S. Economou. Robustness of error-suppressing entangling gates in cavity-coupled transmon qubits. Phys. Rev. B, 96 (035441), 2017. 10.1103\/PhysRevB.96.035441. arXiv:1703.03514.","DOI":"10.1103\/PhysRevB.96.035441"},{"key":"45","doi-asserted-by":"publisher","unstructured":"J. Ding, A. Sly, and N. Sun. Proof of the satisfiability conjecture for large k. In Proc. 47th Annual ACM Symp. Theory of Computing, pages 59-68, 2015. 10.1145\/2746539.2746619. arXiv:1411.0650.","DOI":"10.1145\/2746539.2746619"},{"key":"46","doi-asserted-by":"publisher","unstructured":"T. Draper, S. Kutin, E. Rains, and K. Svore. A logarithmic-depth quantum carry-lookahead adder. Quantum Inf. Comput., 6 (4-5): 351-369, 2006. 10.26421\/QIC6.4-5. quant-ph\/0406142.","DOI":"10.26421\/QIC6.4-5"},{"key":"47","doi-asserted-by":"publisher","unstructured":"B. Eastin. Distilling one-qubit magic states into Toffoli states. Phys. Rev. A, 87: 032321, 2013. 10.1103\/PhysRevA.87.032321. arXiv:1212.4872.","DOI":"10.1103\/PhysRevA.87.032321"},{"key":"48","unstructured":"E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm, 2014. arXiv:1411.4028."},{"key":"49","unstructured":"A. Fowler. Personal communication."},{"key":"50","unstructured":"A. Fowler. Time-optimal quantum computation, 2012. arXiv:1210.4626."},{"key":"51","unstructured":"A. Fowler and C. Gidney. Low overhead quantum computation using lattice surgery, 2018. arXiv:1808.06709."},{"key":"52","doi-asserted-by":"publisher","unstructured":"A. Fowler, M. Mariantoni, J. Martinis, and A. Cleland. Surface codes: Towards practical large-scale quantum computation. Phys. Rev. A, 86: 032324, 2012. 10.1103\/PhysRevA.86.032324. arXiv:1208.0928.","DOI":"10.1103\/PhysRevA.86.032324"},{"key":"53","doi-asserted-by":"publisher","unstructured":"A. Van Gelder. Another look at graph coloring via propositional satisfiability. Discrete Applied Mathematics, 156: 230-243, 2008. 10.1016\/j.dam.2006.07.016.","DOI":"10.1016\/j.dam.2006.07.016"},{"key":"54","doi-asserted-by":"publisher","unstructured":"I. Georgescu, S. Ashhab, and F. Nori. Quantum simulation. Rev. Mod. Phys., 86: 153, 2014. 10.1103\/RevModPhys.86.153. arXiv:1308.6253.","DOI":"10.1103\/RevModPhys.86.153"},{"key":"55","doi-asserted-by":"crossref","unstructured":"C. Gidney. Halving the cost of quantum addition, 2017. arXiv:1709.06648.","DOI":"10.22331\/q-2018-06-18-74"},{"key":"56","doi-asserted-by":"publisher","unstructured":"L. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79 (2): 325-328, 1997. 10.1103\/PhysRevLett.79.325. quant-ph\/9706033.","DOI":"10.1103\/PhysRevLett.79.325"},{"key":"57","doi-asserted-by":"publisher","unstructured":"T. H\u00e4ner, M. Roetteler, and K. Svore. Factoring using $2n+2$ qubits with Toffoli based modular multiplication. Quantum Inf. Comput., 18 (7&8), 2017. 10.26421\/QIC17.7-8. arXiv:1611.07995.","DOI":"10.26421\/QIC17.7-8"},{"key":"58","doi-asserted-by":"publisher","unstructured":"C. Horsman, A. Fowler, S. Devitt, and R. Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14 (12): 123011, 2012. 10.1088\/1367-2630\/14\/12\/123011.","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"59","doi-asserted-by":"publisher","unstructured":"M. Jarret and K. Wan. Improved quantum backtracking algorithms using effective resistance estimates. Phys. Rev. A, 97: 022337, 2018. 10.1103\/PhysRevA.97.022337. arXiv:1711.05295.","DOI":"10.1103\/PhysRevA.97.022337"},{"key":"60","doi-asserted-by":"publisher","unstructured":"C. Jones. Low-overhead constructions for the fault-tolerant Toffoli gate. Phys. Rev. A, 87: 022328, 2013. 10.1103\/PhysRevA.87.022328. arXiv:1212.5069.","DOI":"10.1103\/PhysRevA.87.022328"},{"key":"61","unstructured":"S. Jordan. The quantum algorithm zoo. http:\/\/math.nist.gov\/quantum\/zoo\/."},{"key":"62","doi-asserted-by":"publisher","unstructured":"A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. Chow, and J. Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549: 242-246, 2017. 10.1038\/nature23879. arXiv:1704.05018.","DOI":"10.1038\/nature23879"},{"key":"63","doi-asserted-by":"publisher","unstructured":"B. Konev and A. Lisitsa. Computer-aided proof of Erd\\Hos discrepancy properties. Artificial Intelligence, 224: 103-118, 2015. 10.1016\/j.artint.2015.03.004.","DOI":"10.1016\/j.artint.2015.03.004"},{"key":"64","doi-asserted-by":"publisher","unstructured":"F. Leighton. A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards, 84 (6): 489-503, 1979. 10.6028\/jres.084.024.","DOI":"10.6028\/jres.084.024"},{"key":"65","doi-asserted-by":"publisher","unstructured":"Y. Li. A magic state's fidelity can be superior to the operations that created it. New Journal of Physics, 17 (2): 023037, 2015. 10.1088\/1367-2630\/17\/2\/023037.","DOI":"10.1088\/1367-2630\/17\/2\/023037"},{"key":"66","doi-asserted-by":"publisher","unstructured":"D. Litinski. A game of surface codes: Large-scale quantum computing with lattice surgery. Quantum, 3: 128, 2018. 10.22331\/q-2019-03-05-128. arXiv:1808.02892.","DOI":"10.22331\/q-2019-03-05-128"},{"key":"67","doi-asserted-by":"publisher","unstructured":"E. Malaguti and P. Toth. A survey on vertex coloring problems. Intl. Trans. in Op. Res., 17: 1-34, 2010. 10.1111\/j.1475-3995.2009.00696.x.","DOI":"10.1111\/j.1475-3995.2009.00696.x"},{"key":"68","doi-asserted-by":"publisher","unstructured":"S. Mandr\u00e0, Gian Giacomo Guerreschi, and A. Aspuru-Guzik. Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems. New J. Phys., 18 (7): 073003, 2016. 10.1088\/1367-2630\/18\/7\/073003.","DOI":"10.1088\/1367-2630\/18\/7\/073003"},{"key":"69","unstructured":"I. Markov, A. Fatima, S. Isakov, and S. Boixo. Quantum supremacy is both closer and farther than it appears, 2018. arXiv:1807.10749."},{"key":"70","doi-asserted-by":"publisher","unstructured":"A. Mehrotra and M. Trick. A column generation approach for graph coloring. INFORMS Journal on Computing, 8 (4): 344-354, 1996. 10.1287\/ijoc.8.4.344.","DOI":"10.1287\/ijoc.8.4.344"},{"key":"71","doi-asserted-by":"publisher","unstructured":"A. Meier, B. Eastin, and E. Knill. Magic-state distillation with the four-qubit code. Quant. Inf. and Comp., 13: 195, 2013. 10.26421\/QIC13.3-4.","DOI":"10.26421\/QIC13.3-4"},{"key":"72","doi-asserted-by":"publisher","unstructured":"I. M\u00e9ndez-D\u00edaz and P. Zabala. A branch-and-cut algorithm for graph coloring. Discrete Applied Mathematics, 154: 826-847, 2006. 10.1016\/j.dam.2005.05.022.","DOI":"10.1016\/j.dam.2005.05.022"},{"key":"73","doi-asserted-by":"publisher","unstructured":"S. Mertens, M. M\u00e9zard, and R. Zecchina. Threshold values of random K-SAT from the cavity method. Random Structures and Algorithms, 28 (3): 340-373, 2006. 10.1002\/rsa.20090. cs\/0309020.","DOI":"10.1002\/rsa.20090"},{"key":"74","doi-asserted-by":"publisher","unstructured":"R. Van Meter, K. Itoh, and T. Ladd. Architecture-dependent execution time of Shor's algorithm. In Proc. Mesoscopic Superconductivity + Spintronics 2006, 2006. 10.1142\/9789812814623_0029. quant-ph\/0507023.","DOI":"10.1142\/9789812814623_0029"},{"key":"75","doi-asserted-by":"publisher","unstructured":"A. Montanaro. Quantum-walk speedup of backtracking algorithms. Theory of Computing, 14 (15): 1-24, 2018. 10.4086\/toc.2018.v014a015. arXiv:1509.02374.","DOI":"10.4086\/toc.2018.v014a015"},{"key":"76","doi-asserted-by":"publisher","unstructured":"D. Moylett, N. Linden, and A. Montanaro. Quantum speedup of the traveling-salesman problem for bounded-degree graphs. Phys. Rev. A, 95 (032323), 2017. 10.1103\/PhysRevA.95.032323. arXiv:1612.06203.","DOI":"10.1103\/PhysRevA.95.032323"},{"key":"77","doi-asserted-by":"publisher","unstructured":"J. O'Gorman and E. Campbell. Quantum computation with realistic magic-state factories. Phys. Rev. A, 95: 032338, 2017. 10.1103\/PhysRevA.95.032338. arXiv:1605.07197.","DOI":"10.1103\/PhysRevA.95.032338"},{"key":"78","unstructured":"J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. Schuyler Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, C. A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, R. S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, B. R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti. Unsupervised machine learning on a hybrid quantum computer, 2017. arXiv:1712.05771."},{"key":"79","doi-asserted-by":"publisher","unstructured":"K. Panagiotou and A. Steger. A note on the chromatic number of a dense random graph. Discrete Mathematics, 309: 3420-3423, 2009. 10.1016\/j.disc.2008.09.019.","DOI":"10.1016\/j.disc.2008.09.019"},{"key":"80","doi-asserted-by":"publisher","unstructured":"R. Del Pino, V. Lyubashevsky, and D. Pointcheval. The whole is less than the sum of its parts: Constructing more efficient lattice-based AKEs. In Proc. SCN 2016 - 10th International Conference Security and Cryptography for Networks, pages 273 - 291, 2016. 10.1007\/978-3-319-44618-9_15.","DOI":"10.1007\/978-3-319-44618-9_15"},{"key":"81","doi-asserted-by":"publisher","unstructured":"M. Prasad, A. Biere, and A. Gupta. A survey of recent advances in SAT-based formal verification. International Journal on Software Tools for Technology Transfer, 7 (2): 156-173, 2005. 10.1007\/s10009-004-0183-4.","DOI":"10.1007\/s10009-004-0183-4"},{"key":"82","doi-asserted-by":"publisher","unstructured":"V. Rao and V. Kumar. On the efficiency of parallel backtracking. IEEE Transactions on Parallel and Distributed Systems, 4 (4): 427-437, 1993. 10.1109\/71.219757.","DOI":"10.1109\/71.219757"},{"key":"83","doi-asserted-by":"publisher","unstructured":"M. Reiher, N. Wiebe, K. Svore, D. Wecker, and M. Troyer. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences, 114 (29): 7555-7560, 2017. 10.1073\/pnas.1619152114. arXiv:1605.03590.","DOI":"10.1073\/pnas.1619152114"},{"key":"84","doi-asserted-by":"publisher","unstructured":"T. R\u00f8nnow, Z. Wang, J. Job, S. Boixo, S. Isakov, D. Wecker, J. Martinis, D. Lidar, and M. Troyer. Defining and detecting quantum speedup. Science, 345 (6195): 420-424, 2014. 10.1126\/science.1252319. arXiv:1401.2910.","DOI":"10.1126\/science.1252319"},{"key":"85","doi-asserted-by":"publisher","unstructured":"M. R\u00f6tteler, M. Naehrig, K. Svore, and K. Lauder. Quantum resource estimates for computing elliptic curve discrete logarithms. In Proc. ASIACRYPT'17, pages 241-270, 2017. 10.1007\/978-3-319-70697-9_9. arXiv:1706.06752.","DOI":"10.1007\/978-3-319-70697-9_9"},{"key":"86","doi-asserted-by":"publisher","unstructured":"V. Sch\u00e4fer, C. Ballance, K. Thirumalai, L. Stephenson, T. Ballance, A. Steane, and D. Lucas. Fast quantum logic gates with trapped-ion qubits. Nature, 555: 75-78, 2018. 10.1038\/nature25737. arXiv:1709.06952.","DOI":"10.1038\/nature25737"},{"key":"87","doi-asserted-by":"publisher","unstructured":"P. San Segundo. A new DSATUR-based algorithm for exact vertex coloring. Computers and Operations Research, 39 (7): 1724-1733, 2012. 10.1016\/j.cor.2011.10.008.","DOI":"10.1016\/j.cor.2011.10.008"},{"key":"88","doi-asserted-by":"crossref","unstructured":"P. Selinger. Quantum circuits of t-depth one. Phys. Rev. A, 87: 042302, 2013. arXiv:1210.0974.","DOI":"10.1103\/PhysRevA.87.042302"},{"key":"89","unstructured":"B. Selman and H. Kautz. Planning as satisfiability. In European Conference on Artificial Intelligence, 1992."},{"key":"90","doi-asserted-by":"publisher","unstructured":"E. Sewell. An improved algorithm for exact graph coloring. In Cliques, coloring, and satisfiability. Proceedings of the second DIMACS implementation challenge, volume 26, pages 359-73. American Mathematical Society, 1996. 10.1090\/dimacs\/026\/17.","DOI":"10.1090\/dimacs\/026\/17"},{"key":"91","doi-asserted-by":"publisher","unstructured":"P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proc. 35th Annual Symp. Foundations of Computer Science, pages 124-134, 1994. 10.1109\/SFCS.1994.365700. quant-ph\/9508027.","DOI":"10.1109\/SFCS.1994.365700"},{"key":"92","doi-asserted-by":"publisher","unstructured":"A. Sohanghpurwala, M. Hassan, and P. Athanas. Hardware accelerated SAT solvers - a survey. J. Parallel Distrib. Comput., 106: 170-184, 2017. 10.1016\/j.jpdc.2016.12.014.","DOI":"10.1016\/j.jpdc.2016.12.014"},{"key":"93","doi-asserted-by":"publisher","unstructured":"T. Walter, P. Kurpiers, S. Gasparinetti, P. Magnard, A. Poto\u010dnik, Y. Salath\u00e9, M. Pechal, M. Mondal, M. Oppliger, C. Eichler, and A. Wallraff. Rapid high-fidelity single-shot dispersive readout of superconducting qubits. Phys. Rev. Applied, 7: 054020, 2017. 10.1103\/PhysRevApplied.7.054020. arXiv:1701.06933.","DOI":"10.1103\/PhysRevApplied.7.054020"},{"key":"94","doi-asserted-by":"publisher","unstructured":"D. Wecker, B. Bauer, B. Clark, M. Hastings, and M. Troyer. Gate count estimates for performing quantum chemistry on small quantum computers. Phys. Rev. A, 90: 022305, 2014. 10.1103\/PhysRevA.90.022305. arXiv:1312.1695.","DOI":"10.1103\/PhysRevA.90.022305"},{"key":"95","doi-asserted-by":"publisher","unstructured":"C. Zalka. Grover's quantum searching algorithm is optimal. Phys. Rev. A, 60 (4): 2746-2751, 1999a. 10.1103\/PhysRevA.60.2746. quant-ph\/9711070.","DOI":"10.1103\/PhysRevA.60.2746"},{"key":"96","unstructured":"C. Zalka. A Grover-based quantum search of optimal order for an unknown number of marked elements, 1999b. quant-ph\/9902049."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2019-07-18-167\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,7,21]],"date-time":"2019-07-21T15:07:09Z","timestamp":1563721629000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2019-07-18-167\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,18]]},"references-count":97,"URL":"https:\/\/doi.org\/10.22331\/q-2019-07-18-167","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,18]]},"article-number":"167"}}