# 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

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

### ► 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] M. B. Hastings, "The Short Path Algorithm Applied to a Toy Model", Quantum 3, 145 (2019).

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

[3] M. B. Hastings, "Weaker Assumptions for the Short Path Optimization Algorithm", arXiv:1807.03758.

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