Nearly-frustration-free ground state preparation

Abstract

Solving for quantum ground states is important for understanding the properties of quantum many-body systems, and quantum computers are potentially well-suited for solving for quantum ground states. Recent work has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians, whose query complexity scales as ${\delta }^{-1}$, i.e. inversely with their normalized gap. Here we consider instead the ground state preparation problem restricted to a special subset of Hamiltonians, which includes those which we term "nearly-frustration-free": the class of Hamiltonians for which the ground state energy of their block-encoded and hence normalized Hamiltonian ${\alpha }^{-1}H$ is within ${\delta }^y$ of -1, where $\delta$ is the spectral gap of ${\alpha }^{-1}H$ and $0\le y\le 1$. For this subclass, we describe an algorithm whose dependence on the gap is asymptotically better, scaling as ${\delta }^{y/2-1}$, and show that this new dependence is optimal up to factors of $\log \delta$. In addition, we give examples of physically motivated Hamiltonians which live in this subclass. Finally, we describe an extension of this method which allows the preparation of excited states both for generic Hamiltonians as well as, at a similar speedup as the ground state case, for those which are nearly frustration-free.

arXiv comment13 pages, 1 figure

References in corpus (15)

• Interface-Induced Phenomena in Magnetism
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum measurements and the Abelian Stabilizer Problem
• Studying Two Dimensional Systems With the Density Matrix Renormalization Group
• Pinning the order: the nature of quantum criticality in the Hubbard model on honeycomb lattice
• Near-optimal ground state preparation
• Efficient phase-factor evaluation in quantum signal processing
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Spectral Gap Amplification
• Hamiltonian Simulation by Uniform Spectral Amplification
• Variational Numerical Renormalization Group: Bridging the gap between NRG and Density Matrix Renormalization Group

Cited by in corpus (3)

• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Hamiltonian simulation for low-energy states with optimal time dependence
• Models of interacting bosons with exact ground states: a unified approach