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
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.