Applying quantum algorithms to constraint satisfaction problems

Earl Campbell1, Ankur Khurana2,3, and Ashley Montanaro4

1Department of Physics and Astronomy, University of Sheffield, Sheffield, UK
2Quantum Engineering Centre for Doctoral Training, University of Bristol, UK
3School of Physics, University of Bristol, UK
4School of Mathematics, University of Bristol, UK

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

► 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] Hendrik Poulsen Nautrup, Nicolas Delfosse, Vedran Dunjko, Hans J. Briegel, and Nicolai Friis, "Optimizing Quantum Error Correction Codes with Reinforcement Learning", arXiv:1812.08451.

[2] Roman Orus, Samuel Mugel, and Enrique Lizaso, "Quantum computing for finance: overview and prospects", arXiv:1807.03890.

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

[4] Craig Gidney, "Windowed quantum arithmetic", arXiv:1905.07682.

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

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

[7] Yimin Ge and Vedran Dunjko, "A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles", arXiv:1907.01258.

[8] Ashley Montanaro, "Quantum speedup of branch-and-bound algorithms", arXiv:1906.10375.

[9] Jonas Haferkamp, Dominik Hangleiter, Adam Bouland, Bill Fefferman, Jens Eisert, and Juani Bermejo-Vega, "Closing gaps of a quantum advantage with short-time Hamiltonian dynamics", arXiv:1908.08069.

The above citations are from SAO/NASA ADS (last updated 2019-10-20 17:01:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-10-20 17:01:13).