The performance of the quantum adiabatic algorithm on spike Hamiltonians

DOI10.1142/S0219749917500113zbMATH Open1375.81069arXiv1511.06991WikidataQ114072379 ScholiaQ114072379MaRDI QIDQ5370948FDOQ5370948

Authors: Linghang Kong, Elizabeth Crosson 

Publication date: 20 October 2017

Published in: International Journal of Quantum Information (Search for Journal in Brave)

Abstract: Perturbed Hamming weight problems serve as examples of 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 using several methods to compute the scaling of the spectral gap at the critical point, which apply for various ranges of the height and width of the barrier. Our main result is a rigorous polynomial lower bound on the minimum spectral gap for the adiabatic evolution when the bit-symmetric cost function has a thin but polynomially high barrier. This is accomplished by the use of a variational argument with an improved ansatz for the ground state, along with a comparison to the spectrum of the system when no spike term is present. We also give a more detailed treatment of the spin coherent path-integral instanton method which was used by Farhi, Goldstone, and Gutmann in arXiv:quant-ph/0201031, and consider its applicability for estimating the gap for different scalings of barrier height and width. We adapt the discrete WKB method for an abruptly changing potential, and apply it to the construction of approximate wave functions which can be used to estimate the gap. Finally, the improved ansatz for the ground state leads to a method for predicting the location of avoided crossings in the excited states of the energy spectrum of the thin spike Hamiltonian, and we use a recursion relation to determine the ordering of some of these avoided crossings, which may be a useful step towards understanding the diabatic cascade phenomenon which occurs in spike Hamiltonians.

Full work available at URL: https://arxiv.org/abs/1511.06991

Recommendations

• The quantum adiabatic optimization algorithm and local minima
• scientific article; zbMATH DE number 1984609
• Random matrix model of adiabatic quantum computing
• HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
• scientific article; zbMATH DE number 5953558

zbMATH Keywords

variational methodspectral gapquantum adiabatic algorithm

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Variational principles of physics (49S05) Closed and approximate solutions to the Schrödinger, Dirac, Klein-Gordon and other equations of quantum mechanics (81Q05) Semiclassical techniques, including WKB and Maslov methods applied to problems in quantum theory (81Q20)

Cites Work

• Optimization by simulated annealing
• Title not available (Why is that?)
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• The quantum adiabatic optimization algorithm and local minima
• Two Notes on Phase-Integral Methods
• Mean Deviation of the Binomial Distribution
• Unstructured randomness, small gaps and localization
• WKB approximation for abruptly varying potential wells

Cited In (3)

• The effects of the problem Hamiltonian parameters on the minimum spectral gap in adiabatic quantum optimization
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Anti-crossings and spectral gap during quantum adiabatic evolution

This page was built for publication: The performance of the quantum adiabatic algorithm on spike Hamiltonians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5370948)