CaltechAUTHORS
  A Caltech Library Service

The performance of the quantum adiabatic algorithm on spike Hamiltonians

Kong, Linghang and Crosson, Elizabeth (2017) The performance of the quantum adiabatic algorithm on spike Hamiltonians. International Journal of Quantum Information, 15 (2). Art. No. 1750011. ISSN 0219-7499. http://resolver.caltech.edu/CaltechAUTHORS:20160622-165151480

[img] PDF - Submitted Version
See Usage Policy.

634Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160622-165151480

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1142/S0219749917500113 DOIArticle
http://www.worldscientific.com/doi/abs/10.1142/S0219749917500113PublisherArticle
https://arxiv.org/abs/1511.06991arXivDiscussion Paper
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.
Group:Institute for Quantum Information and Matter, IQIM
Funders:
Funding AgencyGrant Number
NSFPHY-1125565
Gordon and Betty Moore FoundationGBMF-2644
NSFCCF-1111382
Subject Keywords:Quantum adiabatic algorithm; spectral gap; variational method
Record Number:CaltechAUTHORS:20160622-165151480
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20160622-165151480
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:68614
Collection:CaltechAUTHORS
Deposited By: Jacquelyn O'Sullivan
Deposited On:27 Jun 2016 17:07
Last Modified:17 Apr 2017 21:46

Repository Staff Only: item control page