The Short Path Algorithm Applied to a Toy Model

M. B. Hastings

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 numerically investigate the performance of the short path optimization algorithm on a toy problem, with the potential chosen to depend only on the total Hamming weight to allow simulation of larger systems. We consider classes of potentials with multiple minima which cause the adiabatic algorithm to experience difficulties with small gaps. The numerical investigation allows us to consider a broader range of parameters than was studied in previous rigorous work on the short path algorithm, and to show that the algorithm can continue to lead to speedups for more general objective functions than those considered before. We find in many cases a polynomial speedup over Grover search. We present a heuristic analytic treatment of choices of these parameters and of scaling of phase transitions in this model.

► 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] 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

[3] 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

[4] 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

[5] Elizabeth Crosson and Aram W. Harrow. Simulated quantum annealing can be exponentially faster than classical simulated annealing. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, oct 2016. 10.1109/​focs.2016.81. URL https:/​/​doi.org/​10.1109.
https:/​/​doi.org/​10.1109/​focs.2016.81

[6] E. Farhi, J. Goldstone, and S. Gutmann. Quantum adiabatic evolution algorithms versus simulated annealing. arXiv:quant-ph/​0201031, 2002.
arXiv:quant-ph/0201031

[7] M. B. Hastings. A short path quantum algorithm for exact optimization. Quantum, 2: 78, jul 2018a. 10.22331/​q-2018-07-26-78. URL https:/​/​doi.org/​10.22331.
https:/​/​doi.org/​10.22331/​q-2018-07-26-78

[8] M. B. Hastings. Weaker assumptions for the short path optimization algorithm. arXiv:arXiv:1807.03758, 2018b.
arXiv:1807.03758

[9] C.R. Laumann, R. Moessner, A. Scardicchio, and S.L. Sondhi. Quantum annealing: The fastest route to quantum computation? The European Physical Journal Special Topics, 224 (1): 75–88, feb 2015. 10.1140/​epjst/​e2015-02344-2. URL https:/​/​doi.org/​10.1140.
https:/​/​doi.org/​10.1140/​epjst/​e2015-02344-2

[10] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. arXiv:arXiv:1610.06546, 2016.
arXiv:1610.06546

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

[12] Jérémie Roland and Nicolas J Cerf. Quantum search by local adiabatic evolution. Physical Review A, 65 (4): 042308, 2002. 10.1103/​physreva.65.042308.
https:/​/​doi.org/​10.1103/​physreva.65.042308

[13] Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51 (3): 385–463, 2004. 10.1145/​380752.380813.
https:/​/​doi.org/​10.1145/​380752.380813

[14] 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

Cited by

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

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-28 18:12:21) and SAO/NASA ADS (last updated successfully 2024-03-28 18:12:22). The list may be incomplete as not all publishers provide suitable and complete citation data.