### 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 - Jul 31 2013 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Computational Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'A fast algorithm for approximating the ground state energy on a quantum computer'. Together they form a unique fingerprint.

## Cite this

*Mathematics of Computation*,

*82*(284), 2293-2304. https://doi.org/10.1090/S0025-5718-2013-02714-7