Polynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians

Abstract

Much research regarding quantum adiabatic optimization has focused on stoquastic Hamiltonians with Hamming symmetric potentials, such as the well studied "spike" example. Due to the large amount of symmetry in these potentials such problems are readily open to analysis both analytically and computationally. However, more realistic potentials do not have such a high degree of symmetry and may have many local minima. Here we present a somewhat more realistic class of problems consisting of many individually Hamming symmetric potential wells. For two or three such wells we demonstrate that such a problem can be solved exactly in time polynomial in the number of qubits and wells. For greater than three wells, we present a tight binding approach with which to efficiently analyze the performance of such Hamiltonians in an adiabatic computation. We provide several basic examples designed to highlight the usefulness of this toy model and to give insight into using the tight binding approach to examining it, including: (1) adiabatic unstructured search with a transverse field driver and a prior guess to the marked item and (2) a scheme for adiabatically simulating the ground states of small collections of strongly interacting spins, with an explicit demonstration for an Ising model Hamiltonian.

arXiv comment12 pages, 9 figures, v3: update to be consistent with Phys. Rev. A version

References in corpus (14)

• Quantum Search by Local Adiabatic Evolution
• Quantum Computation by Adiabatic Evolution
• Bounds for the adiabatic approximation with applications to quantum computation
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• A note on the switching adiabatic theorem
• Adiabatic optimization versus diffusion Monte Carlo
• Open system quantum annealing in mean field models with exponential degeneracy
• Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
• Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians
• Tunneling through high energy barriers in simulated quantum annealing
• Quantum adiabatic optimization without heuristics

Cited by in corpus (3)

• Fibonacci anyons versus Majorana fermions
• Diagonal Catalysts in Quantum Adiabatic Optimization
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians