Applying quantum algorithms to constraint satisfaction problems

Earl Campbell; Ankur Khurana; Ashley Montanaro

doi:10.22331/q-2019-07-18-167

Applying quantum algorithms to constraint satisfaction problems

Earl Campbell¹, Ankur Khurana^2,3, and Ashley Montanaro⁴

¹Department of Physics and Astronomy, University of Sheffield, Sheffield, UK
²Quantum Engineering Centre for Doctoral Training, University of Bristol, UK
³School of Physics, University of Bristol, UK
⁴School of Mathematics, University of Bristol, UK

Published:	2019-07-18, volume 3, page 167
Eprint:	arXiv:1810.05582v2
Doi:	https://doi.org/10.22331/q-2019-07-18-167
Citation:	Quantum 3, 167 (2019).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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 $10^5$ relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over $10^3$. 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.

► BibTeX data

@article{Campbell2019applyingquantum,
  doi = {10.22331/q-2019-07-18-167},
  url = {https://doi.org/10.22331/q-2019-07-18-167},
  title = {Applying quantum algorithms to constraint satisfaction problems},
  author = {Campbell, Earl and Khurana, Ankur and Montanaro, Ashley},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {3},
  pages = {167},
  month = jul,
  year = {2019}
}

► References

[1] Source code and experimental results. 2019. 10.5523/bris.19va21gun3c7629f291kmd6w37.
https://doi.org/10.5523/bris.19va21gun3c7629f291kmd6w37

[2] 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.
https://doi.org/10.1007/s10479-007-0178-0

[3] 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.
https://doi.org/10.5195/LEDGER.2018.127
arXiv:1710.10377

[4] 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.
https://doi.org/10.1007/s00453-008-9168-0
arXiv:quant-ph/0511096

[5] E. Alkim, L. Ducas, T. Pöppelmann, and P. Schwabe. Post-quantum key exchange – a new hope. In USENIX Security Symposium, pages 327–343, 2016.

[6] 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.
https://doi.org/10.1145/3055399.3055444

[7] 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.
https://doi.org/10.1109/TCAD.2013.2244643
arXiv:1206.0758

[8] 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.
https://doi.org/10.1007/978-3-319-69453-5_18
arXiv:1603.09383

[9] 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.
https://doi.org/10.26421/QIC17.3-4
arXiv:1512.07550

[10] 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.
https://doi.org/10.1103/PhysRevX.8.041015
arXiv:1805.03662

[11] 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.
https://doi.org/10.3233/FI-2010-307
arXiv:1008.0659

[12] 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.
https://doi.org/10.1007/978-0-387-30165-5_30

[13] 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.
https://doi.org/10.1103/PhysRevLett.117.060504
arXiv:1512.04600

[14] T. Balyo, M. Heule, and M. Järvisalo. Proceedings of SAT competition 2017: Solver and benchmark descriptions, 2017.

[15] 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.
https://doi.org/10.1038/nature13171
arXiv:1402.4848

[16] 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.
https://doi.org/10.1109/SFCS.1998.743485
arXiv:quant-ph/9802049

[17] A. Belovs. Quantum walks and electric networks, 2013. arXiv:1302.3143.
arXiv:1302.3143

[18] 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.
https://doi.org/10.1007/978-3-642-39206-1_10

[19] 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.
https://doi.org/10.1137/S0097539796300933
arXiv:quant-ph/9701001

[20] 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.
https://doi.org/10.1007/978-3-642-02882-3_42
arXiv:0804.2429

[21] D. Bernstein and T. Lange (editors). ebacs: Ecrypt benchmarking of cryptographic systems, accessed 27 June 2018. http://bench.cr.yp.to.
http://bench.cr.yp.to

[22] 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.
https://doi.org/10.1103/PhysRevLett.114.080502
arXiv:1404.5320

[23] B. Bollobás. The chromatic number of random graphs. Combinatorica, 8 (1): 49–55, 1988. 10.1007/BF02122551.
https://doi.org/10.1007/BF02122551

[24] M. Boyer, G. Brassard, P. Høyer, and A. Tapp. Tight bounds on quantum searching. Fortschr. Phys., 46 (4–5): 493–505, 1998. 10.1002/3527603093.ch10. quant-ph/9605034.
https://doi.org/10.1002/3527603093.ch10
arXiv:quant-ph/9605034

[25] G. Brassard, P. Høyer, 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.
https://doi.org/10.1090/conm/305/05215
arXiv:quant-ph/0005055

[26] S. Bravyi and J. Haah. Magic-state distillation with low overhead. Physical Review A, 86 (5): 052329, 2012. 10.1103/PhysRevA.86.052329.
https://doi.org/10.1103/PhysRevA.86.052329

[27] 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.
https://doi.org/10.1103/PhysRevA.71.022316
arXiv:quant-ph/0403025

[28] D. Brélaz. New methods to color the vertices of a graph. C. ACM, 22 (4): 251–256, 1979. 10.1145/359094.359101.
https://doi.org/10.1145/359094.359101

[29] C. Brown and P. Purdom, Jr. An average time analysis of backtracking. SIAM J. Comput., 10 (3): 583–593, 1981. 10.1137/0210043.
https://doi.org/10.1137/0210043

[30] 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.
https://doi.org/10.26421/QIC18.1-2
arXiv:1610.00581

[31] 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.
https://doi.org/10.1103/PhysRevA.95.022316

[32] E. Campbell and M. Howard. Unifying gate synthesis and magic state distillation. Physical review letters, 118 (6): 060501, 2017b. 10.1103/PhysRevLett.118.060501.
https://doi.org/10.1103/PhysRevLett.118.060501

[33] E. Campbell and M. Howard. Magic state parity-checker with pre-distilled components. Quantum, 2: 56, 2018. 10.22331/q-2018-03-14-56.
https://doi.org/10.22331/q-2018-03-14-56

[34] 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.
https://doi.org/10.1038/nature23460
arXiv:1612.07330

[35] P. Cheeseman, B. Kanefsky, and W. Taylor. Where the really hard problems are. In Proc. IJCAI '91, pages 331–337, 1991.

[36] 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.
https://doi.org/10.1007/s00220-009-0930-1
arXiv:0810.0312

[37] 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.
https://doi.org/10.1073/pnas.1801723115
arXiv:1711.10980

[38] 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.
https://doi.org/10.1145/88616.88621

[39] 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.
https://doi.org/10.1098/rspa.1998.0164
arXiv:quant-ph/9708016

[40] 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.
https://doi.org/10.1145/2488608.2488698
arXiv:1212.1682

[41] 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.
https://doi.org/10.1007/978-3-642-81952-0_9

[42] 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.
https://doi.org/10.1007/978-3-642-81952-0_16

[43] 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.

[44] N. Delfosse and N. Nickerson. Almost-linear time decoding algorithm for topological codes, 2017. arXiv:1709.06218.
arXiv:1709.06218

[45] 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.
https://doi.org/10.1103/PhysRevB.96.035441
arXiv:1703.03514

[46] 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.
https://doi.org/10.1145/2746539.2746619
arXiv:1411.0650

[47] 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.
https://doi.org/10.26421/QIC6.4-5
arXiv:quant-ph/0406142

[48] B. Eastin. Distilling one-qubit magic states into Toffoli states. Phys. Rev. A, 87: 032321, 2013. 10.1103/PhysRevA.87.032321. arXiv:1212.4872.
https://doi.org/10.1103/PhysRevA.87.032321
arXiv:1212.4872

[49] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm, 2014. arXiv:1411.4028.
arXiv:1411.4028

[50] A. Fowler. Personal communication.

[51] A. Fowler. Time-optimal quantum computation, 2012. arXiv:1210.4626.
arXiv:1210.4626

[52] A. Fowler and C. Gidney. Low overhead quantum computation using lattice surgery, 2018. arXiv:1808.06709.
arXiv:1808.06709

[53] 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.
https://doi.org/10.1103/PhysRevA.86.032324
arXiv:1208.0928

[54] 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.
https://doi.org/10.1016/j.dam.2006.07.016

[55] I. Georgescu, S. Ashhab, and F. Nori. Quantum simulation. Rev. Mod. Phys., 86: 153, 2014. 10.1103/RevModPhys.86.153. arXiv:1308.6253.
https://doi.org/10.1103/RevModPhys.86.153
arXiv:1308.6253

[56] C. Gidney. Halving the cost of quantum addition, 2017. arXiv:1709.06648.
arXiv:1709.06648

[57] 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.
https://doi.org/10.1103/PhysRevLett.79.325
arXiv:quant-ph/9706033

[58] T. Häner, 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.
https://doi.org/10.26421/QIC17.7-8
arXiv:1611.07995

[59] 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.
https://doi.org/10.1088/1367-2630/14/12/123011

[60] 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.
https://doi.org/10.1103/PhysRevA.97.022337
arXiv:1711.05295

[61] 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.
https://doi.org/10.1103/PhysRevA.87.022328
arXiv:1212.5069

[62] S. Jordan. The quantum algorithm zoo. http://math.nist.gov/quantum/zoo/.
http://math.nist.gov/quantum/zoo/

[63] 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.
https://doi.org/10.1038/nature23879
arXiv:1704.05018

[64] 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.
https://doi.org/10.1016/j.artint.2015.03.004

[65] 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.
https://doi.org/10.6028/jres.084.024

[66] 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.
https://doi.org/10.1088/1367-2630/17/2/023037

[67] 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.
https://doi.org/10.22331/q-2019-03-05-128
arXiv:1808.02892

[68] 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.
https://doi.org/10.1111/j.1475-3995.2009.00696.x

[69] S. Mandrà, 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.
https://doi.org/10.1088/1367-2630/18/7/073003

[70] I. Markov, A. Fatima, S. Isakov, and S. Boixo. Quantum supremacy is both closer and farther than it appears, 2018. arXiv:1807.10749.
arXiv:1807.10749

[71] 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.
https://doi.org/10.1287/ijoc.8.4.344

[72] 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.
https://doi.org/10.26421/QIC13.3-4

[73] I. Méndez-Díaz 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.
https://doi.org/10.1016/j.dam.2005.05.022

[74] S. Mertens, M. Mézard, 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.
https://doi.org/10.1002/rsa.20090

[75] 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.
https://doi.org/10.1142/9789812814623_0029
arXiv:quant-ph/0507023

[76] A. Montanaro. Quantum-walk speedup of backtracking algorithms. Theory of Computing, 14 (15): 1–24, 2018. 10.4086/toc.2018.v014a015. arXiv:1509.02374.
https://doi.org/10.4086/toc.2018.v014a015
arXiv:1509.02374

[77] 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.
https://doi.org/10.1103/PhysRevA.95.032323
arXiv:1612.06203

[78] 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.
https://doi.org/10.1103/PhysRevA.95.032338
arXiv:1605.07197

[79] 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.
arXiv:1712.05771

[80] 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.
https://doi.org/10.1016/j.disc.2008.09.019

[81] 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.
https://doi.org/10.1007/978-3-319-44618-9_15

[82] 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.
https://doi.org/10.1007/s10009-004-0183-4

[83] 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.
https://doi.org/10.1109/71.219757

[84] 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.
https://doi.org/10.1073/pnas.1619152114
arXiv:1605.03590

[85] T. Rønnow, 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.
https://doi.org/10.1126/science.1252319
arXiv:1401.2910

[86] M. Rötteler, 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.
https://doi.org/10.1007/978-3-319-70697-9_9
arXiv:1706.06752

[87] V. Schäfer, 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.
https://doi.org/10.1038/nature25737
arXiv:1709.06952

[88] 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.
https://doi.org/10.1016/j.cor.2011.10.008

[89] P. Selinger. Quantum circuits of t-depth one. Phys. Rev. A, 87: 042302, 2013. arXiv:1210.0974.
arXiv:1210.0974

[90] B. Selman and H. Kautz. Planning as satisfiability. In European Conference on Artificial Intelligence, 1992.

[91] 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.
https://doi.org/10.1090/dimacs/026/17

[92] 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.
https://doi.org/10.1109/SFCS.1994.365700
arXiv:quant-ph/9508027

[93] 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.
https://doi.org/10.1016/j.jpdc.2016.12.014

[94] T. Walter, P. Kurpiers, S. Gasparinetti, P. Magnard, A. Potočnik, Y. Salathé, 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.
https://doi.org/10.1103/PhysRevApplied.7.054020
arXiv:1701.06933

[95] 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.
https://doi.org/10.1103/PhysRevA.90.022305
arXiv:1312.1695

[96] 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.
https://doi.org/10.1103/PhysRevA.60.2746
arXiv:quant-ph/9711070

[97] C. Zalka. A Grover-based quantum search of optimal order for an unknown number of marked elements, 1999b. quant-ph/9902049.
arXiv:quant-ph/9902049

Cited by

[1] Sofiene Jerbi, Lea M. Trenkwalder, Hendrik Poulsen Nautrup, Hans J. Briegel, and Vedran Dunjko, "Quantum Enhancements for Deep Reinforcement Learning in Large Spaces", PRX Quantum 2 1, 010328 (2021).

[2] Simon Martiel and Maxime Remaud, Lecture Notes in Computer Science 12011, 597 (2020) ISBN:978-3-030-38918-5.

[3] J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, and J. Bermejo-Vega, "Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics", Physical Review Letters 125 25, 250501 (2020).

[4] Mathias Soeken, Mariia Mykhailova, Vadym Kliuchnikov, Christopher Granade, and Alexander Vaschillo, 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE) 1050 (2021) ISBN:978-3-9819263-5-4.

[5] Rhea Parekh, Andrea Ricciardi, Ahmed Darwish, and Stephen DiAdamo, 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS) 9 (2021) ISBN:978-1-7281-8674-0.

[6] Karuna Kadian, Sunita Garhwal, and Ajay Kumar, "Quantum walk and its application domains: A systematic review", Computer Science Review 41, 100419 (2021).

[7] Yan Liang and Bingo Wing-Kuen Ling, "Infinite Impulse Response Filter Bank Based Graphic Equalizer Design via Functional Inequality Constrained Optimization and Genetic Algorithm", IEEE Access 9, 65116 (2021).

[8] Iñaki Fernández Pérez, Fernando de la Prieta, Sara Rodríguez-González, Juan M. Corchado, and Javier Prieto, Lecture Notes in Networks and Systems 603, 155 (2023) ISBN:978-3-031-22355-6.

[9] Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven, "Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage", PRX Quantum 2 1, 010103 (2021).

[10] Thomas E. O’Brien, Stefano Polla, Nicholas C. Rubin, William J. Huggins, Sam McArdle, Sergio Boixo, Jarrod R. McClean, and Ryan Babbush, "Error Mitigation via Verified Phase Estimation", PRX Quantum 2 2, 020317 (2021).

[11] John S. Van Dyke, George S. Barron, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou, "Preparing Bethe Ansatz Eigenstates on a Quantum Computer", PRX Quantum 2 4, 040329 (2021).

[12] Christopher Chamberland and Earl T. Campbell, "Universal Quantum Computing with Twist-Free and Temporally Encoded Lattice Surgery", PRX Quantum 3 1, 010331 (2022).

[13] Kyle E. C. Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield, and Eleanor Rieffel, "Quantum-accelerated constraint programming", Quantum 5, 550 (2021).

[14] Mathys Rennela, Sebastiaan Brand, Alfons Laarman, and Vedran Dunjko, "Hybrid divide-and-conquer approach for tree search algorithms", Quantum 7, 959 (2023).

[15] Kyle E. C. Booth, Bryan O’Gorman, Jeffrey Marshall, Stuart Hadfield, and Eleanor Rieffel, Lecture Notes in Computer Science 12333, 72 (2020) ISBN:978-3-030-58474-0.

[16] Yuval R. Sanders, Dominic W. Berry, Pedro C.S. Costa, Louis W. Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven, and Ryan Babbush, "Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization", PRX Quantum 1 2, 020312 (2020).

[17] Ashley Montanaro, "Quantum speedup of branch-and-bound algorithms", Physical Review Research 2 1, 013056 (2020).

[18] James R. Wootton, 2020 IEEE Conference on Games (CoG) 73 (2020) ISBN:978-1-7281-4533-4.

[19] Cezar-Mihail Alexandru, Ella Bridgett-Tomkinson, Noah Linden, Joseph MacManus, Ashley Montanaro, and Hannah Morris, "Quantum speedups of some general-purpose numerical optimisation algorithms", Quantum Science and Technology 5 4, 045014 (2020).

[20] Hendrik Poulsen Nautrup, Nicolas Delfosse, Vedran Dunjko, Hans J. Briegel, and Nicolai Friis, "Optimizing Quantum Error Correction Codes with Reinforcement Learning", Quantum 3, 215 (2019).

[21] Yimin Ge and Vedran Dunjko, "A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles", Journal of Mathematical Physics 61 1, 012201 (2020).

[22] Shraddha Singh, Andrew S. Darmawan, Benjamin J. Brown, and Shruti Puri, "High-fidelity magic-state preparation with a biased-noise architecture", Physical Review A 105 5, 052410 (2022).

[23] Earl T Campbell, "Early fault-tolerant simulations of the Hubbard model", Quantum Science and Technology 7 1, 015007 (2022).

[24] Furqan Ahmed and Petri Mahonen, 2021 IEEE 32nd Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) 1128 (2021) ISBN:978-1-7281-7586-7.

[25] Christopher Chamberland, Kyungjoo Noh, Patricio Arrangoiz-Arriola, Earl T. Campbell, Connor T. Hann, Joseph Iverson, Harald Putterman, Thomas C. Bohdanowicz, Steven T. Flammia, Andrew Keller, Gil Refael, John Preskill, Liang Jiang, Amir H. Safavi-Naeini, Oskar Painter, and Fernando G.S.L. Brandão, "Building a Fault-Tolerant Quantum Computer Using Concatenated Cat Codes", PRX Quantum 3 1, 010329 (2022).

[26] Christoph Roch, Santiago Londono Castillo, and Claudia Linnhoff-Popien, 2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C) 147 (2022) ISBN:978-1-6654-9493-9.

[27] Craig Gidney and Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", Quantum 5, 433 (2021).

[28] Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni, Nicholas C. Rubin, Zhang Jiang, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven, "Low-Depth Mechanisms for Quantum Optimization", PRX Quantum 2 3, 030312 (2021).

[29] Lawrence Z. Cohen, Isaac H. Kim, Stephen D. Bartlett, and Benjamin J. Brown, "Low-overhead fault-tolerant quantum computing using long-range connectivity", Science Advances 8 20, eabn1717 (2022).

[30] E. J. Crosson and D. A. Lidar, "Prospects for quantum enhancement with diabatic quantum annealing", Nature Reviews Physics 3 7, 466 (2021).

[31] Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão, Proceedings of the 55th Annual ACM Symposium on Theory of Computing 1131 (2023) ISBN:9781450399135.

[32] Zijun Chen, Kevin J. Satzinger, Juan Atalaya, Alexander N. Korotkov, Andrew Dunsworth, Daniel Sank, Chris Quintana, Matt McEwen, Rami Barends, Paul V. Klimov, Sabrina Hong, Cody Jones, Andre Petukhov, Dvir Kafri, Sean Demura, Brian Burkett, Craig Gidney, Austin G. Fowler, Alexandru Paler, Harald Putterman, Igor Aleiner, Frank Arute, Kunal Arya, Ryan Babbush, Joseph C. Bardin, Andreas Bengtsson, Alexandre Bourassa, Michael Broughton, Bob B. Buckley, David A. Buell, Nicholas Bushnell, Benjamin Chiaro, Roberto Collins, William Courtney, Alan R. Derk, Daniel Eppens, Catherine Erickson, Edward Farhi, Brooks Foxen, Marissa Giustina, Ami Greene, Jonathan A. Gross, Matthew P. Harrigan, Sean D. Harrington, Jeremy Hilton, Alan Ho, Trent Huang, William J. Huggins, L. B. Ioffe, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Kostyantyn Kechedzhi, Seon Kim, Alexei Kitaev, Fedor Kostritsa, David Landhuis, Pavel Laptev, Erik Lucero, Orion Martin, Jarrod R. McClean, Trevor McCourt, Xiao Mi, Kevin C. Miao, Masoud Mohseni, Shirin Montazeri, Wojciech Mruczkiewicz, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Michael Newman, Murphy Yuezhen Niu, Thomas E. O’Brien, Alex Opremcak, Eric Ostby, Bálint Pató, Nicholas Redd, Pedram Roushan, Nicholas C. Rubin, Vladimir Shvarts, Doug Strain, Marco Szalay, Matthew D. Trevithick, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Juhwan Yoo, Adam Zalcman, Hartmut Neven, Sergio Boixo, Vadim Smelyanskiy, Yu Chen, Anthony Megrant, and Julian Kelly, "Exponential suppression of bit or phase errors with cyclic error correction", Nature 595 7867, 383 (2021).

[33] Earl Campbell, "Random Compiler for Fast Hamiltonian Simulation", Physical Review Letters 123 7, 070503 (2019).

[34] Craig Gidney and Martin Ekerå, "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", arXiv:1905.09749, (2019).

[35] Christopher Chamberland, Kyungjoo Noh, Patricio Arrangoiz-Arriola, Earl T. Campbell, Connor T. Hann, Joseph Iverson, Harald Putterman, Thomas C. Bohdanowicz, Steven T. Flammia, Andrew Keller, Gil Refael, John Preskill, Liang Jiang, Amir H. Safavi-Naeini, Oskar Painter, and Fernando G. S. L. Brandão, "Building a fault-tolerant quantum computer using concatenated cat codes", arXiv:2012.04108, (2020).

[36] Hendrik Poulsen Nautrup, Nicolas Delfosse, Vedran Dunjko, Hans J. Briegel, and Nicolai Friis, "Optimizing Quantum Error Correction Codes with Reinforcement Learning", arXiv:1812.08451, (2018).

[37] Craig Gidney, "Windowed quantum arithmetic", arXiv:1905.07682, (2019).

[38] Sami Boulebnane and Ashley Montanaro, "Solving boolean satisfiability problems with the quantum approximate optimization algorithm", arXiv:2208.06909, (2022).

[39] Chris Cade, Marten Folkertsma, Ido Niesen, and Jordi Weggemans, "Quantifying Grover speed-ups beyond asymptotic analysis", arXiv:2203.04975, (2022).

[40] Sukin Sim, Yudong Cao, Jonathan Romero, Peter D. Johnson, and Alan Aspuru-Guzik, "A framework for algorithm deployment on cloud-based quantum computers", arXiv:1810.10576, (2018).

[41] Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G. S. L. Brandão, "Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end", arXiv:2212.01513, (2022).

[42] Charles Yuan, Agnes Villanyi, and Michael Carbin, "Quantum Control Machine: The Limits of Quantum Programs as Data", arXiv:2304.15000, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-09 04:56:04) and SAO/NASA ADS (last updated successfully 2023-06-09 04:56:05). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.