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.


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.

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

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

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

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

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

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

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

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

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

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

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

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

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

[17] A. Belovs. Quantum walks and electric networks, 2013. 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.

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

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

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

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

[23] B. Bollobás. The chromatic number of random graphs. Combinatorica, 8 (1): 49–55, 1988. 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.

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

[26] S. Bravyi and J. Haah. Magic-state distillation with low overhead. Physical Review A, 86 (5): 052329, 2012. 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.

[28] D. Brélaz. New methods to color the vertices of a graph. C. ACM, 22 (4): 251–256, 1979. 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[50] A. Fowler. Personal communication.

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

[52] A. Fowler and C. Gidney. Low overhead quantum computation using lattice surgery, 2018. 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.

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

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

[56] C. Gidney. Halving the cost of quantum addition, 2017. 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.

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

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

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

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

[62] S. Jordan. The quantum algorithm zoo. http:/​/​​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.

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

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

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

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

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

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

[70] I. Markov, A. Fatima, S. Isakov, and S. Boixo. Quantum supremacy is both closer and farther than it appears, 2018. 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[89] P. Selinger. Quantum circuits of t-depth one. Phys. Rev. A, 87: 042302, 2013. 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.

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

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

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

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

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

[97] C. Zalka. A Grover-based quantum search of optimal order for an unknown number of marked elements, 1999b. 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] Bibek Pokharel and Daniel A. Lidar, "Better-than-classical Grover search via quantum error detection and suppression", npj Quantum Information 10 1, 23 (2024).

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

[4] 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).

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

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

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

[8] Domenik Eichhorn, Tobias Pett, Tobias Osborne, and Ina Schaefer, Proceedings of the 27th ACM International Systems and Software Product Line Conference - Volume A 1 (2023) ISBN:9798400700910.

[9] Suhas Vittal, Poulami Das, and Moinuddin Qureshi, 56th Annual IEEE/ACM International Symposium on Microarchitecture 509 (2023) ISBN:9798400703294.

[10] 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).

[11] Chris Cade, Marten Folkertsma, Ido Niesen, and Jordi Weggemans, "Quantifying Grover speed-ups beyond asymptotic analysis", Quantum 7, 1133 (2023).

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

[13] 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).

[14] Alexander Mandl, Johanna Barzen, Marvin Bechtold, Frank Leymann, and Karoline Wild, "Amplitude amplification-inspired QAOA: improving the success probability for solving 3SAT", Quantum Science and Technology 9 1, 015028 (2024).

[15] 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).

[16] 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).

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

[18] Ruhan Wang, Philip Richerme, and Fan Chen, "A hybrid quantum–classical neural network for learning transferable visual representation", Quantum Science and Technology 8 4, 045021 (2023).

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

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

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

[22] 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).

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

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

[25] 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).

[26] 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).

[27] 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).

[28] 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).

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

[30] Shuai Yang, Wei Zi, Bujiao Wu, Cheng Guo, Jialin Zhang, and Xiaoming Sun, "Efficient Quantum Circuit Synthesis for SAT-Oracle With Limited Ancillary Qubit", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 43 3, 868 (2024).

[31] Jeremy Côté, Frédéric Sauvage, Martín Larocca, Matías Jonsson, Lukasz Cincio, and Tameem Albash, "Diabatic quantum annealing for the frustrated ring model", Quantum Science and Technology 8 4, 045033 (2023).

[32] Shi Bai, Maya-Iggy van Hoof, Floyd B. Johnson, Tanja Lange, and Tran Ngo, Lecture Notes in Computer Science 14440, 131 (2023) ISBN:978-981-99-8726-9.

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

[34] 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).

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

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

[37] 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).

[38] Suhas Vittal, Poulami Das, and Moinuddin Qureshi, Proceedings of the 50th Annual International Symposium on Computer Architecture 1 (2023) ISBN:9798400700958.

[39] 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).

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

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

[42] 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).

[43] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

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

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

[46] 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).

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

[48] 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).

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

[50] 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).

[51] 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).

[52] Suhas Vittal, Poulami Das, and Moinuddin Qureshi, "ERASER: Towards Adaptive Leakage Suppression for Fault-Tolerant Quantum Computing", arXiv:2309.13143, (2023).

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