A Short Path Quantum Algorithm for Exact Optimization

M. B. Hastings

doi:10.22331/q-2018-07-26-78

A Short Path Quantum Algorithm for Exact Optimization

M. B. Hastings

Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA
Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA

Published:	2018-07-26, volume 2, page 78
Eprint:	arXiv:1802.10124v3
Doi:	https://doi.org/10.22331/q-2018-07-26-78
Citation:	Quantum 2, 78 (2018).

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

Abstract

We give a quantum algorithm to exactly solve certain problems in combinatorial optimization, including weighted MAX-2-SAT as well as problems where the objective function is a weighted sum of products of Ising variables, all terms of the same degree $D$; this problem is called weighted MAX-E$D$-LIN2. We require that the optimal solution be unique for odd $D$ and doubly degenerate for even $D$; however, we expect that the algorithm still works without this condition and we show how to reduce to the case without this assumption at the cost of an additional overhead. While the time required is still exponential, the algorithm provably outperforms Grover's algorithm assuming a mild condition on the number of low energy states of the target Hamiltonian. The detailed analysis of the runtime dependence on a tradeoff between the number of such states and algorithm speed: fewer such states allows a greater speedup. This leads to a natural hybrid algorithm that finds either an exact or approximate solution.

► BibTeX data

@article{Hastings2018shortpathquantum,
  doi = {10.22331/q-2018-07-26-78},
  url = {https://doi.org/10.22331/q-2018-07-26-78},
  title = {A {S}hort {P}ath {Q}uantum {A}lgorithm for {E}xact {O}ptimization},
  author = {Hastings, M. B.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {2},
  pages = {78},
  month = jul,
  year = {2018}
}

► References

[1] Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 307–316. ACM, 2015. 10.1137/15m1050902.
https://doi.org/10.1137/15m1050902

[2] Boris Altshuler, Hari Krovi, and Jérémie Roland. Anderson localization makes adiabatic quantum optimization fail. Proceedings of the National Academy of Sciences, 107 (28): 12446–12450, 2010. 10.1073/pnas.1002116107.
https://doi.org/10.1073/pnas.1002116107

[3] Andris Ambainis and Oded Regev. An elementary proof of the quantum adiabatic theorem. arXiv preprint quant-ph/0411152, 2004.
arXiv:quant-ph/0411152

[4] Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26 (5): 1510–1523, 1997. 10.1137/s0097539796300933.
https://doi.org/10.1137/s0097539796300933

[5] D. W. Berry, A. M. Childs, and R. Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809, Oct 2015a. 10.1109/FOCS.2015.54.
https://doi.org/10.1109/FOCS.2015.54

[6] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. pages 283–292, 2014. 10.1145/2591796.2591854.
https://doi.org/10.1145/2591796.2591854

[7] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Phys. Rev. Lett., 114: 090502, 2015b. 10.1103/PhysRevLett.114.090502.
https://doi.org/10.1103/PhysRevLett.114.090502

[8] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53–74, 2002. 10.1090/conm/305.
https://doi.org/10.1090/conm/305

[9] A Crisanti and T Rizzo. Analysis of the $\infty$-replica symmetry breaking solution of the sherrington-kirkpatrick model. Physical Review E, 65 (4): 046137, 2002. 10.1103/physreve.65.046137.
https://doi.org/10.1103/physreve.65.046137

[10] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science, 292 (5516): 472–475, 2001. 10.1126/science.1057726.
https://doi.org/10.1126/science.1057726

[11] Martin Fürer and Shiva Prasad Kasiviswanathan. Exact max 2-sat: Easier and faster. In International Conference on Current Trends in Theory and Practice of Computer Science, pages 272–283. Springer, 2007. 10.1007/978-3-540-69507-3_22.
https://doi.org/10.1007/978-3-540-69507-3_22

[12] Alexander Golovnev and Konstantin Kutzkov. New exact algorithms for the 2-constraint satisfaction problem. Theoretical Computer Science, 526: 18–27, 2014. 10.1016/j.tcs.2014.01.010.
https://doi.org/10.1016/j.tcs.2014.01.010

[13] Leonard Gross. Logarithmic sobolev inequalities. American Journal of Mathematics, 97 (4): 1061–1083, 1975. 10.2307/2373688.
https://doi.org/10.2307/2373688

[14] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219. ACM, 1996. 10.1145/237814.237866.
https://doi.org/10.1145/237814.237866

[15] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103 (15): 150502, 2009. 10.1103/physrevlett.103.150502.
https://doi.org/10.1103/physrevlett.103.150502

[16] M. B. Hastings. Local maxima and improved exact algorithm for max-2-sat. Chicago Journal of Theoretical Computer Science, 2018. 10.4086/cjtcs.2018.002. arXiv preprint arXiv:1610.07100.
https://doi.org/10.4086/cjtcs.2018.002
arXiv:1610.07100

[17] S Kirkpatrick and D Sherrington. Solvable model of a spin-glass. Phys. Rev. Lett, 35 (26): 1792–1796, 1975. 10.1103/physrevlett.35.1792.
https://doi.org/10.1103/physrevlett.35.1792

[18] A Yu Kitaev. Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/9511026, 1995.
arXiv:quant-ph/9511026

[19] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation, volume 47. American Mathematical Society Providence, 2002. 10.1090/gsm/047.
https://doi.org/10.1090/gsm/047

[20] Sergey Knysh and Vadim Smelyanskiy. On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm. arXiv preprint arXiv:1005.3011, 2010.
arXiv:1005.3011

[21] JM Leinaas and TTS Kuo. Convergence properties of the brillouin-wigner type of perturbation expansion. Annals of Physics, 111 (1): 19–37, 1978. 10.1016/0003-4916(78)90222-1.
https://doi.org/10.1016/0003-4916(78)90222-1

[22] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. 2016.

[23] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118: 010501, 2017. 10.1103/PhysRevLett.118.010501.
https://doi.org/10.1103/PhysRevLett.118.010501

[24] Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. 10.1017/cbo9781139814782.002.
https://doi.org/10.1017/cbo9781139814782.002

[25] Sergey Pankov. Low-temperature solution of the sherrington-kirkpatrick model. Physical review letters, 96 (19): 197204, 2006. 10.1103/physrevlett.96.197204.
https://doi.org/10.1103/physrevlett.96.197204

[26] Giorgio Parisi. Infinite number of order parameters for spin-glasses. Physical Review Letters, 43 (23): 1754, 1979. 10.1103/physrevlett.43.1754.
https://doi.org/10.1103/physrevlett.43.1754

[27] Giorgio Parisi. Order parameter for spin-glasses. Physical Review Letters, 50 (24): 1946, 1983. 10.1103/physrevlett.50.1946.
https://doi.org/10.1103/physrevlett.50.1946

[28] D. Poulin, A Kitaev, D. S. Steiger, M. B. Hastings, and M. Troyer. Fast quantum algorithm for spectral properties. arXiv preprint:arXiv:1711.11025, 2017.
arXiv:1711.11025

[29] Ben W Reichardt. The quantum adiabatic optimization algorithm and local minima. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 502–510. ACM, 2004. 10.1145/1007352.1007428.
https://doi.org/10.1145/1007352.1007428

[30] Alex Samorodnitsky. A modified logarithmic sobolev inequality for the hamming cube and some applications. arXiv preprint arXiv:0807.1679, 2008.
arXiv:0807.1679

[31] Alexander D Scott and Gregory B Sorkin. Linear-programming design and analysis of fast algorithms for max 2-csp. Discrete Optimization, 4 (3-4): 260–287, 2007. 10.1016/j.disopt.2007.08.001.
https://doi.org/10.1016/j.disopt.2007.08.001

[32] RD Somma, S Boixo, Howard Barnum, and E Knill. Quantum simulations of classical annealing processes. Physical review letters, 101 (13): 130504, 2008. 10.1103/physrevlett.101.130504.
https://doi.org/10.1103/physrevlett.101.130504

[33] Dave Wecker, Matthew B Hastings, and Matthias Troyer. Training a quantum optimizer. Physical Review A, 94 (2): 022309, 2016. 10.1103/physreva.94.022309.
https://doi.org/10.1103/physreva.94.022309

[34] Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348 (2-3): 357–365, 2005. 10.1016/j.tcs.2005.09.023.
https://doi.org/10.1016/j.tcs.2005.09.023

Cited by

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

[2] M. B. Hastings, "The Short Path Algorithm Applied to a Toy Model", Quantum 3, 145 (2019).

[3] Maxime Dupont, Tina Oberoi, and Bhuvanesh Sundar, "Optimization via quantum preconditioning", Physical Review Applied 24 4, 044013 (2025).

[4] Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush, "Optimization by decoded quantum interferometry", Nature 646 8086, 831 (2025).

[5] T. Muser, E. Zapusek, V. Belis, and F. Reiter, "Provable advantages of kernel-based quantum learners and quantum preprocessing based on Grover's algorithm", Physical Review A 110 3, 032434 (2024).

[6] Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari, and Ryan Babbush, "Quartic Quantum Speedups for Planted Inference", Physical Review X 15 2, 021077 (2025).

[7] Nicolas PD Sawaya, Albert T Schmitz, and Stuart Hadfield, "Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems", Quantum 7, 1111 (2023).

[8] Ryan Babbush, Robbie King, Sergio Boixo, William Huggins, Tanuj Khattar, Guang Hao Low, Jarrod R. McClean, Thomas O’Brien, and Nicholas C. Rubin, "Grand Challenge of Quantum Applications", PRX Quantum 7 2, 020101 (2026).

[9] Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny, Tanner Mengle, Michael Mills, Steven A. Moses, Brian Neyenhuis, Peter Siegfried, Romina Yalovetzky, and Marco Pistoia, "Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem", Science Advances 10 22, eadm6761 (2024).

[10] Sebastián V. Romero, Anne-Maria Visuri, Alejandro Gomez Cadavid, Anton Simen, Enrique Solano, and Narendra N. Hegade, "Bias-field digitized counterdiabatic quantum algorithm for higher-order binary optimization", Communications Physics 8 1, 348 (2025).

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

[12] Michael A. Perlin, Ruslan Shaydulin, Benjamin Hall, Pierre Minssen, Changhao Li, Kabir Dubey, Rich Rines, Eric Anschuetz, Marco Pistoia, and Pranav Gokhale, "Q-CHOP: Quantum constrained Hamiltonian optimization", ACM Transactions on Quantum Computing 3778864 (2025).

[13] G.D. Varsamis, I.G. Karafyllidis, K.M. Gilkes, U. Arranz, R. Martin-Cuevas, G. Calleja, J. Wong, H.C. Jessen, P. Dimitrakis, P. Kolovos, and R. Sandaltzopoulos, "Quantum algorithm for de novo DNA sequence assembly based on quantum walks on graphs", Biosystems 233, 105037 (2023).

[14] Matthew B. Hastings, "Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad", Quantum 3, 201 (2019).

[15] Matthew B. Hastings, "The Power of Adiabatic Quantum Computation with No Sign Problem", Quantum 5, 597 (2021).

[16] Kazumasa Ueno and Hiroaki Miura, "Quantum Algorithm for a Stochastic Multicloud Model", SOLA 21, 43 (2025).

[17] Dylan Herman, Cody Googin, Xiaoyuan Liu, Yue Sun, Alexey Galda, Ilya Safro, Marco Pistoia, and Yuri Alexeev, "Quantum computing for finance", Nature Reviews Physics 5 8, 450 (2023).

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

[19] Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, and Ryan Babbush, "Optimization by Decoded Quantum Interferometry", arXiv:2408.08292, (2024).

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

[21] M. B. Hastings, "Weaker Assumptions for the Short Path Optimization Algorithm", arXiv:1807.03758, (2018).

[22] Kate V. Marshall, Daniel J. Egger, Michael Garn, Francesca Schiavello, Sebastian Brandhofer, Christa Zoufal, and Stefan Woerner, "Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization", arXiv:2602.06171, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 03:30:24) and SAO/NASA ADS (last updated successfully 2026-08-09 03:30:26). 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.