Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, USA
Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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.
► BibTeX data
► References
[1] 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
[2] 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.
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.110
arXiv:1505.03424
[3] 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
[4] 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
[5] 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
[6] Aline Bonami. Étude des coefficients de fourier des fonctions de $l^p(g)$. In Annales de l’institut Fourier, volume 20, pages 335-402, 1970. 10.5802/aif.357.
https://doi.org/10.5802/aif.357
[7] Adam Callison, Nicholas Chancellor, Florian Mintert, and Viv Kendon. Finding spin-glass ground states using quantum walks. arXiv preprint arXiv:1903.05003, 2019.
arXiv:1903.05003
[8] Andrew M Childs and Jeffrey Goldstone. Spatial search by quantum walk. Physical Review A, 70 (2): 022314, 2004. 10.1103/PhysRevA.70.022314.
https://doi.org/10.1103/PhysRevA.70.022314
[9] 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
[10] 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.
arXiv:1412.6062
[11] 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.
arXiv:1801.03922
[12] Johan Håstad. On bounded occurrence constraint satisfaction. Information Processing Letters, 74 (1-2): 1-6, 2000. 10.1016/S0020-0190(00)00032-6.
https://doi.org/10.1016/S0020-0190(00)00032-6
[13] Johan Håstad and Srinivasan Venkatesh. On the advantage over a random assignment. Random Structures & Algorithms, 25 (2): 117-149, 2004. 10.1002/rsa.20031.
https://doi.org/10.1002/rsa.20031
[14] 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.
https://doi.org/10.22331/q-2018-07-26-78
[15] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. 2016. newblock 10.22331/q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163
[16] 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
[17] Ryan O’Donnell. Analysis of boolean functions. Cambridge University Press, 2014. 10.1017/cbo9781139814782.002.
https://doi.org/10.1017/cbo9781139814782.002
[18] 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.
https://doi.org/10.1103/PhysRevLett.121.010501
[19] 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.
https://doi.org/10.1103/PhysRevA.81.040102
[20] Salvador Elías Venegas-Andraca. Quantum walks: a comprehensive review. Quantum Information Processing, 11 (5): 1015-1106, 2012. 10.1007/s11128-012-0432-5.
https://doi.org/10.1007/s11128-012-0432-5
Cited by
[1] 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).
[2] 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-22 22:24:09) and SAO/NASA ADS (last updated successfully 2020-01-22 22:24:10). 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.
Source: https://quantum-journal.org/papers/q-2019-11-11-201/
