Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published March 2017 | Submitted
Journal Article Open

The performance of the quantum adiabatic algorithm on spike Hamiltonians

Abstract

Spike Hamiltonians arise from optimization instances for which the adiabatic algorithm provably out performs classical simulated annealing. In this work, we study the efficiency of the adiabatic algorithm for solving the "the Hamming weight with a spike" problem by analyzing the scaling of the spectral gap at the critical point for various sizes of the barrier. Our main result is a rigorous lower bound on the minimum spectral gap for the adiabatic evolution when the bit-symmetric cost function has a thin but polynomially high barrier, which is based on a comparison argument and an improved variational ansatz for the ground state. We also adapt the discrete WKB method for the case of abruptly changing potentials and compare it with the predictions of the spin coherent instanton method which was previously used by Farhi, Goldstone and Gutmann. Finally, our improved ansatz for the ground state leads to a method for predicting the location of avoided crossings in the excited energy states of the thin spike Hamiltonian, and we use a recursion relation to understand the ordering of some of these avoided crossings as a step towards analyzing the previously observed diabatic cascade phenomenon.

Additional Information

© 2017 World Scientific Publishing. Received: 23 May 2016; Accepted: 28 December 2016; Published: 7 February 2017. We are very grateful to Aram Harrow for guiding us at many points throughout this work. We thank Jeffrey Goldstone for discussing the application of spin coherent states in [11] and for encouraging us to recover the calculation in Appendix B. We also thank David Gosset for suggesting the use of Lemma 2 to lower bound the ground state energy, and we thank Bill Kaminsky for referring us to exposition of coherent spin path integrals in [15]. Linghang Kong acknowledges the Tsinghua-MIT CTCS undergraduate exchange program, through which he visited MIT in Spring 2015 and did the major part of this work. He also thanks the Undergraduate Research Opportunity Program in MIT. Elizabeth Crosson gratefully acknowledges funding provided by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028), and is also grateful for support received while completing a portion of this work at the MIT Center for Theoretical Physics with funding from NSF grant number CCF-1111382.

Attached Files

Submitted - 1511.06991v1.pdf

Files

1511.06991v1.pdf
Files (650.0 kB)
Name Size Download all
md5:938475b3d4281c5ad59ebc9aa2be5487
650.0 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 19, 2023