We consider classical and quantum algorithms which have a duality property: roughly, either the algorithm provides some nontrivial improvement over random or there exist many solutions which are significantly worse than random. This enables one to give guarantees that the algorithm will find such a nontrivial improvement: if few solutions exist which are much worse than random, then a nontrivial improvement is guaranteed. The quantum algorithm is based on a sudden $quench$ of a Hamiltonian; while the algorithm is general, we analyze it in the specific context of MAX-$K$-LIN$2$, for both even and odd $K$. The classical algorithm is a ``dequantization of this algorithm", obtaining the same guarantee (indeed, some results which are only conjectured in the quantum case can be proven here); however, the quantum point of view helps in analyzing the performance of the classical algorithm and might in some cases perform better.
 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.
 Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the random assignment on constraint satisfaction problems of bounded degree. APPROX-RANDOM, pages 110-123, 2015. 10.4230/LIPIcs.APPROX-RANDOM.2015.110. arXiv preprint arXiv:1505.03424.
 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.
 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.
 Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem, 2014. arXiv preprint arXiv:1412.6062, 2014.
 Jeongwan Haah, Matthew B Hastings, Robin Kothari, and Guang Hao Low. Quantum algorithm for simulating real time evolution of lattice hamiltonians. arXiv preprint arXiv:1801.03922, 2018.
 Johan Håstad. On bounded occurrence constraint satisfaction. Information Processing Letters, 74 (1-2): 1-6, 2000. 10.1016/S0020-0190(00)00032-6.
 M. B. Hastings. A short path quantum algorithm for exact optimization. Quantum, 2: 78, jul 2018. 10.22331/q-2018-07-26-78. URL https://doi.org/10.22331.
 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.
 David Poulin, Alexei Kitaev, Damian S Steiger, Matthew B Hastings, and Matthias Troyer. Quantum algorithm for spectral measurement with a lower gate count. Physical review letters, 121 (1): 010501, 2018. 10.1103/PhysRevLett.121.010501.
 Isabeau Prémont-Schwarz, Alioscia Hamma, Israel Klich, and Fotini Markopoulou-Kalamara. Lieb-robinson bounds for commutator-bounded operators. Physical Review A, 81 (4): 040102, 2010. 10.1103/PhysRevA.81.040102.
 Salvador Elías Venegas-Andraca. Quantum walks: a comprehensive review. Quantum Information Processing, 11 (5): 1015-1106, 2012. 10.1007/s11128-012-0432-5.
 Adam Callison, Nicholas Chancellor, Florian Mintert, and Viv Kendon, "Finding spin glass ground states using quantum walks", New Journal of Physics 21 12, 123022 (2019).
 M. B. Hastings, "Classical and Quantum Bounded Depth Approximation Algorithms", arXiv:1905.07047.
The above citations are from Crossref's cited-by service (last updated successfully 2020-01-28 10:40:27) and SAO/NASA ADS (last updated successfully 2020-01-28 10:40:28). 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.