Beating the natural Grover bound for low-energy estimation and state preparation

• URL: http://arxiv.org/abs/2407.03073v2
• Date: Wed, 05 Feb 2025 07:37:43 GMT
• Title: Beating the natural Grover bound for low-energy estimation and state preparation
• Authors: Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki,
• Abstract summary: Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. We give quantum algorithms which, given any $k$-body Hamiltonian $H$, compute an estimate for the ground state energy.
• Score: 0.23034630097498876
• License:
• Abstract: Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this work, we give quantum algorithms which, given any $k$-body Hamiltonian $H$, compute an estimate for the ground state energy and prepare a quantum state achieving said energy, respectively. Specifically, for any $\varepsilon>0$, our algorithms return, with high probability, an estimate of the ground state energy of $H$ within additive error $\varepsilon M$, or a quantum state with the corresponding energy. Here, $M$ is the total strength of all interaction terms, which in general is extensive in the system size. Our approach makes no assumptions about the geometry or spatial locality of interaction terms of the input Hamiltonian and thus handles even long-range or all-to-all interactions, such as in quantum chemistry, where lattice-based techniques break down. In this fully general setting, the runtime of our algorithms scales as $2^{cn/2}$ for $c<1$, yielding the first quantum algorithms for low-energy estimation breaking a standard square root Grover speedup for unstructured search. The core of our approach is remarkably simple, and relies on showing that an extensive fraction of the interactions can be neglected with a controlled error. What this ultimately implies is that even arbitrary $k$-local Hamiltonians have structure in their low energy space, in the form of an exponential-dimensional low energy subspace.

Related papers

• Robust analog quantum simulators by quantum error-detecting codes [22.034646136056804]
  We provide a recipe for error-resilient Hamiltonian simulations, making use of an excited encoding subspace stabilized by solely $2$-local commuting Hamiltonians. Our method is scalable as it only requires penalty terms that scale to system size.
  arXiv  Detail & Related papers  (2024-12-10T18:58:05Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• 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 can be computed classically in $mathrmpolyleft (1/chi,nright)$ time and $mathrmpoly(n)$ space.
  arXiv  Detail & Related papers  (2024-10-29T07:56:38Z)
• Preparing angular momentum eigenstates using engineered quantum walks [1.0232954388448414]
  We develop a quantum-walk scheme that does not require inputting $O(j)$ nonzero Clebsch-Gordan (CG) coefficients classically. Our scheme prepares angular momentum eigenstates using a sequence of Hamiltonians to move an initial state deterministically to desired final states. We test our state preparation scheme on classical computers, reproducing CG coefficients, and implement small test problems on current quantum hardware.
  arXiv  Detail & Related papers  (2024-08-26T23:20:00Z)
• Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
  The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions. We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
  arXiv  Detail & Related papers  (2023-09-19T22:53:17Z)
• Measuring the Loschmidt amplitude for finite-energy properties of the Fermi-Hubbard model on an ion-trap quantum computer [27.84599956781646]
  We study the operation of a quantum-classical time-series algorithm on a present-day quantum computer. Specifically, we measure the Loschmidt amplitude for the Fermi-Hubbard model on a $16$-site ladder geometry (32 orbitals) on the Quantinuum H2-1 trapped-ion device. We numerically analyze the influence of noise on the full operation of the quantum-classical algorithm by measuring expectation values of local observables at finite energies.
  arXiv  Detail & Related papers  (2023-09-19T11:59:36Z)
• 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)
• Estimating gate complexities for the site-by-site preparation of fermionic vacua [0.0]
  We study the ground state overlap as a function of the number of sites for a range of quadratic fermionic Hamiltonians. For one-dimensional systems, we find that two $N/2$-site ground states also share a large overlap with the $N$-site ground state everywhere except a region near the phase boundary.
  arXiv  Detail & Related papers  (2022-07-04T19:45:14Z)
• Nearly-frustration-free ground state preparation [0.0]
  Solving for quantum ground states is important for understanding the properties of quantum many-body systems. Recent work has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians.
  arXiv  Detail & Related papers  (2021-08-06T18:00:04Z)
• Quantum-inspired search method for low-energy states of classical Ising Hamiltonians [0.0]
  We develop a quantum-inspired numerical procedure for searching low-energy states of a classical Hamiltonian composed of two-body fully-connected random Ising interactions. We consider 120 instances of the random coupling realizations for the random Ising Hamiltonian with $N$ up to 600 and search the 120 lowest-energy states for each instance.
  arXiv  Detail & Related papers  (2020-10-01T02:29:31Z)
• Hamiltonian operator approximation for energy measurement and ground state preparation [23.87373187143897]
  We show how to approximate the Hamiltonian operator as a sum of propagators using a differential representation. The proposed approach, named Hamiltonian operator approximation (HOA), is designed to benefit analog quantum simulators.
  arXiv  Detail & Related papers  (2020-09-07T18:11:00Z)

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.