A fast algorithm for approximating the ground state energy on a quantum computer

A. Papageorgiou, I. Petras, J. F. Traub, C. Zhang

Research output: Contribution to journalArticle

8 Scopus citations

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 languageEnglish (US)
Pages (from-to)2293-2304
Number of pages12
JournalMathematics of Computation
Volume82
Issue number284
DOIs
StatePublished - Jul 31 2013
Externally publishedYes

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