Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors

Citation
Ds. Abrams et S. Lloyd, Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors, PHYS REV L, 83(24), 1999, pp. 5162-5165
Citations number
13
Categorie Soggetti
Physics
Journal title
PHYSICAL REVIEW LETTERS
ISSN journal
00319007 → ACNP
Volume
83
Issue
24
Year of publication
1999
Pages
5162 - 5165
Database
ISI
SICI code
0031-9007(199912)83:24<5162:QAPESI>2.0.ZU;2-3
Abstract
We describe a new polynomial time quantum algorithm that uses the quantum f ast Fourier transform to find eigenvalues and eigenvectors of a local Hamil tonian, and that can be applied in cases (commonly found in ab initio physi cs and chemistry problems) for which all known classical algorithms require exponential time. Applications of the algorithm to specific problems are c onsidered, and we find that classically intractable and interesting problem s from atomic physics may be solved with between 50 and 100 quantum bits.