The circuit complexity in preparing the ground state of a Hamiltonian is studied as a function of the spectral gap---the energy difference between the ground and the first excited state---and an optimistic outlook for quantum variational methods is presented.
Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.
Estimating energy gaps, i.e. the energy difference between two different states, in quantum systems is crucial for understanding their properties. Conventionally, spectral gap estimation relies on independently computing the ground-state and first-excited-state energies and then taking their difference. This work introduces an alternative procedure for estimating spectral gaps on digital quantum devices using the Adiabatic Preparation technique to create a specific superposition state. The expectation values of observables measured on such a state exhibit time-dependent fluctuations which, through a fitting process, can be used to estimate the energy gap. We successfully test our method on the 1D and 2D Ising models, and H2 and He2 molecules, implementing relatively shallow circuits both on noiseless and noisy simulators. The robustness of the approach is corroborated by additional experiments on the real IonQ Aria device for the 1D Ising model up to 20 qubits, demonstrating the applicability of the proposed method for currently available digital quantum devices and paving the way for more complex energy gap calculation requiring deeper circuits in the fault-tolerant era to come.
Ground-state preparation, energy estimation, and property estimation are fundamental tasks in quantum simulation. Existing ground-state preparation algorithms achieve near-optimal complexity using block encodings or controlled Hamiltonian evolution, raising a natural question: is controlled Hamiltonian evolution necessary, or can the same scaling be attained in the weaker access model that provides access to only uncontrolled Hamiltonian evolution? We resolve this question by giving two algorithms that access the input Hamiltonian H only through queries to UH and its inverse UH†, where ∥H∥≤αH and τ=Θ(1/αH). Given an input state with ground-state weight at least η and a spectral gap of H of at least γ, our first algorithm uses fresh copies of the input state and requires O(αH/(γη)) queries to UH and UH†, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to O(αH/(γη)). The latter bound matches the known lower bound up to logarithmic factors, showing that algorithms with additional access to controlled Hamiltonian evolution cannot improve the query complexity for ground-state preparation beyond logarithmic factors. Both algorithms are based on a simple mechanism that we call the spectral descent principle, in which the algorithm starts from the input state ∣ψ⟩ and progressively descends through the energy spectrum, moving closer to the ground state until the desired fidelity is reached. We also extend this framework to ground-state property and energy estimation and give explicit complexity guarantees for both tasks.
Abstract Estimating energy gaps, i.e. the energy difference between two different states, in quantum systems is crucial for understanding their properties. Conventionally, spectral gap estimation relies on independently computing the ground-state and first-excited-state energies and then taking their difference. This work introduces an alternative procedure for estimating spectral gaps on digital quantum devices using the adiabatic preparation technique to create a specific superposition state. The expectation values of observables measured on such a state exhibit time-dependent fluctuations which, through a fitting process, can be used to estimate the energy gap. We successfully test our method on the 1D and 2D Ising models, and H 2 and He 2 molecules, implementing relatively shallow circuits both on noiseless and noisy simulators. The robustness of the approach is corroborated by additional experiments on the real IonQ Aria device for the 1D Ising model up to 20 qubits, demonstrating the applicability of the proposed method for currently available digital quantum devices and paving the way for more complex energy gap calculation requiring deeper circuits in the fault-tolerant era to come.
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 [1] has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians, whose query complexity scales as δ−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 α−1H is within δy of -1, where δ is the spectral gap of α−1H and 0≤y≤1 . For this subclass, we describe an algorithm whose dependence on the gap is asymptotically better, scaling as δy/2−1 , and show that this new dependence is optimal up to factors of logδ . 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.
This work introduces a novel NISQ-friendly procedure for estimating spectral gaps in quantum systems. By leveraging Adiabatic Thermalization, we are able to create the Spectral Gap Superposition state, a newly defined quantum state exhibiting observable fluctuations in time that allow for the accurate estimation of any energy gap. Our method is tested by estimating the energy gap between the ground and the first excited state for the 1D and 2D Ising model, the Hydrogen molecule H2 and Helium molecule He2. Despite limiting our circuit design to have at most 40 Trotter steps, our numerical experiments of both noiseless and noisy devices for the presented systems give relative errors in the order of 10−2 and 10−1. Further experiments on the IonQ Aria device lead to spectral gap estimations with a relative error of 10−2 for a 4-site Ising chain, demonstrating the validity of the procedure for NISQ devices and charting a path towards a new way of calculating energy gaps.