A fast algorithm for approximating the ground state energy on a quantum computer
- 16 May 2013
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 82 (284) , 2293-2304
Abstract
Estimating the ground state energy of a multiparticle system with relative error <!-- MATH $\varepsilon$ --> using deterministic classical algorithms has cost that grows exponentially with the number of particles. The problem depends on a number of state variables that is proportional to the number of particles and suffers from the curse of dimensionality. Quantum computers can vanquish this curse. In particular, we study a ground state eigenvalue problem and exhibit a quantum algorithm that achieves relative error <!-- MATH $\varepsilon$ --> using a number of qubits <!-- MATH $C^\prime d\log \varepsilon ^{-1}$ --> with total cost (number of queries plus other quantum operations) <!-- MATH $Cd\varepsilon ^{-(3+\delta )}$ --> , where 0$"> is arbitrarily small and and are independent of and <!-- MATH $\varepsilon$ --> .
Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Quantum computing with trapped ionsPhysics Reports, 2008
- From Quantum to Classical Molecular Dynamics: Reduced Models and Numerical Analysis2008
- Polynomial-Time Algorithm for Simulation of Weakly Interacting Quantum Spin SystemsCommunications in Mathematical Physics, 2008
- Finite Difference Methods for Ordinary and Partial Differential Equations2007
- The Complexity of the Local Hamiltonian ProblemSIAM Journal on Computing, 2006
- Quantum Computation and Quantum InformationAmerican Journal of Physics, 2002
- Quantum amplitude amplification and estimation2002
- Quantum Complexity of IntegrationJournal of Complexity, 2001
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- Applied Numerical Linear Algebra1997