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'd log e-1 with total cost (number of queries plus other quantum operations) Cde-(3+d), where d > 0 is arbitrarily small and C and C' are independent of d and e.
Original language | English (US) |
---|---|
Pages (from-to) | 2293-2304 |
Number of pages | 12 |
Journal | Mathematics of Computation |
Volume | 82 |
Issue number | 284 |
DOIs | |
State | Published - 2013 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Algebra and Number Theory
- Computational Mathematics
- Applied Mathematics