A fast algorithm for approximating the ground state energy on a quantum computer
Preprint
Abstract
Estimating the ground state energy of a multiparticle system with relative error $\e$ using deterministic classical algorithms has cost that grows exponentially with the number of particles. The problem depends on a number of state variables $d$ 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 $\e$ using a number of qubits $C^\prime d\log \e^{-1}$ with total cost (number of queries plus other quantum operations) $Cd\e^{-(3+\delta)}$, where $\delta>0$ is arbitrarily small and $C$ and $C^\prime$ are independent of $d$ and $\e$.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- On the efficiency of quantum algorithms for Hamiltonian simulationQuantum Information Processing, 2011
- Towards quantum chemistry on a quantum computerNature Chemistry, 2010
- Polynomial-time quantum algorithm for the simulation of chemical dynamicsProceedings of the National Academy of Sciences, 2008
- Quantum algorithm for obtaining the energy spectrum of molecular systemsPhysical Chemistry Chemical Physics, 2008
- Polynomial-Time Algorithm for Simulation of Weakly Interacting Quantum Spin SystemsCommunications in Mathematical Physics, 2008
- On the complexity of the multivariate Sturm–Liouville eigenvalue problemJournal of Complexity, 2007
- Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum ComputersFoundations of Computational Mathematics, 2003
- General theory of fractal path integrals with applications to many-body theories and statistical physicsJournal of Mathematical Physics, 1991
- Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulationsPhysics Letters A, 1990
- Upper and lower bounds for eigenvalues by finite difference methodsCommunications on Pure and Applied Mathematics, 1956