Near-optimal ground state preparation

• URL: http://arxiv.org/abs/2002.12508v3
• Date: Sun, 6 Dec 2020 23:48:38 GMT
• Title: Near-optimal ground state preparation
• Authors: Lin Lin and Yu Tong
• Abstract summary: We propose a quantum-classical algorithm to estimate the ground energy of a Hamiltonian. 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. 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.
• Score: 3.7747526957907303
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians [0.39886149789339326]
  We construct classical algorithms computing an approximation of the ground state energy of an arbitrary $k$-local Hamiltonian acting on $n$ qubits. We show that a constant approximation of the ground state energy can be computed classically in $mathrmpolyleft (1/chi,nright)$ time and $mathrmpoly(n)$ space.
  arXiv  Detail & Related papers  (2024-10-29T07:56:38Z)
• Faster ground state energy estimation on early fault-tolerant quantum computers via rejection sampling [0.0]
  We introduce quantum algorithms for ground state energy estimation (GSEE) First estimates ground state energies and has a quadratic improvement on the ground state overlap parameter compared to other methods in this regime. Second certifies that the estimated ground state energy is within a specified error tolerance of the true ground state energy.
  arXiv  Detail & Related papers  (2023-04-19T17:27:26Z)
• Dissipative ground state preparation and the Dissipative Quantum Eigensolver [0.0]
  I construct a local CPT map and stopping condition which converges to the ground state subspace of H. This dissipative quantum eigensolver has a number of interesting characteristics, which give advantages over previous ground state preparation algorithms.
  arXiv  Detail & Related papers  (2023-03-21T15:50:06Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Improved iterative quantum algorithm for ground-state preparation [4.921552273745794]
  We propose an improved iterative quantum algorithm to prepare the ground state of a Hamiltonian system. Our approach has advantages including the higher success probability at each iteration, the measurement precision-independent sampling complexity, the lower gate complexity, and only quantum resources are required when the ancillary state is well prepared.
  arXiv  Detail & Related papers  (2022-10-16T05:57:43Z)
• Exploring the role of parameters in variational quantum algorithms [59.20947681019466]
  We introduce a quantum-control-inspired method for the characterization of variational quantum circuits using the rank of the dynamical Lie algebra. A promising connection is found between the Lie rank, the accuracy of calculated energies, and the requisite depth to attain target states via a given circuit architecture.
  arXiv  Detail & Related papers  (2022-09-28T20:24:53Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Reducing the cost of energy estimation in the variational quantum eigensolver algorithm with robust amplitude estimation [50.591267188664666]
  Quantum chemistry and materials is one of the most promising applications of quantum computing. Much work is still to be done in matching industry-relevant problems in these areas with quantum algorithms that can solve them.
  arXiv  Detail & Related papers  (2022-03-14T16:51:36Z)
• Numerical Simulations of Noisy Quantum Circuits for Computational Chemistry [51.827942608832025]
  Near-term quantum computers can calculate the ground-state properties of small molecules. We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
  arXiv  Detail & Related papers  (2021-12-31T16:33:10Z)
• Quantum approximation algorithms for many-body and electronic structure problems [0.0]
  Three algorithms produce approximate ground states for many-body and electronic structure problems. They can be used stand-alone or in conjunction with existing quantum algorithms for ground states.
  arXiv  Detail & Related papers  (2021-11-15T21:30:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.