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.
 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.
 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.
 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.
 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.
 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.
 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.
 Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53-74, 2002. 10.1090/conm/305.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation, volume 47. American Mathematical Society Providence, 2002. 10.1090/gsm/047.
 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.
 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.
 Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. 2016.
 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.
 Sergey Pankov. Low-temperature solution of the sherrington-kirkpatrick model. Physical review letters, 96 (19): 197204, 2006. 10.1103/physrevlett.96.197204.
 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.
 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.
 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.
 Dave Wecker, Matthew B Hastings, and Matthias Troyer. Training a quantum optimizer. Physical Review A, 94 (2): 022309, 2016. 10.1103/physreva.94.022309.
 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.
Crossref's cited-by service has no data on citing works. Unfortunately not all publishers provide suitable 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.