Measures of quantum computing speedup
- 12 August 2013
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 88 (2)
Abstract
We introduce the concept of strong quantum speedup. We prove that approximating the ground-state energy of an instance of the time-independent Schr\"odinger equation, with $d$ degrees of freedom and large $d$, enjoys strong exponential quantum speedup. It can be easily solved on a quantum computer. Some researchers in discrete complexity theory believe that quantum computation is not effective for eigenvalue problems. One of our goals in this paper is to explain this dissonance.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Quantum Algorithms for Quantum Field TheoriesScience, 2012
- Simulation of electronic structure Hamiltonians using quantum computersMolecular Physics, 2011
- Quantum algorithm for obtaining the energy spectrum of molecular systemsPhysical Chemistry Chemical Physics, 2008
- Limitations of Quantum Simulation Examined by Simulating a Pairing Hamiltonian Using Nuclear Magnetic ResonancePhysical Review Letters, 2006
- Simulated Quantum Computation of Molecular EnergiesScience, 2005
- PRIMES is in PAnnals of Mathematics, 2004
- Eigenvector Approximation Leading to Exponential Speedup of Quantum Eigenvalue CalculationPhysical Review Letters, 2003
- Quantum amplitude amplification and estimation2002
- Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and EigenvectorsPhysical Review Letters, 1999
- Calculating the thermal rate constant with exponential speedup on a quantum computerPhysical Review E, 1999