Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors

被引:527
作者
Abrams, DS
Lloyd, S
机构
[1] CALTECH, Jet Prop Lab, Pasadena, CA 91109 USA
[2] MIT, Dept Mech Engn, dArbeloff Lab Informat Sci & Technol, Cambridge, MA 02139 USA
关键词
D O I
10.1103/PhysRevLett.83.5162
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
We describe a new polynomial time quantum algorithm that uses the quantum fast Fourier transform to find eigenvalues and eigenvectors of a local Hamiltonian, and that can be applied in cases (commonly found in ab initio physics and chemistry problems) for which all known classical algorithms require exponential time. Applications of the algorithm to specific problems are considered, and we find that classically intractable and interesting problems from atomic physics may be solved with between 50 and 100 quantum bits.
引用
收藏
页码:5162 / 5165
页数:4
相关论文
共 14 条
  • [1] Simulations of many-body Fermi systems on a universal quantum computer
    Abrams, DS
    Lloyd, S
    [J]. PHYSICAL REVIEW LETTERS, 1997, 79 (13) : 2586 - 2589
  • [2] ELEMENTARY GATES FOR QUANTUM COMPUTATION
    BARENCO, A
    BENNETT, CH
    CLEVE, R
    DIVINCENZO, DP
    MARGOLUS, N
    SHOR, P
    SLEATOR, T
    SMOLIN, JA
    WEINFURTER, H
    [J]. PHYSICAL REVIEW A, 1995, 52 (05): : 3457 - 3467
  • [3] Quantum lattice-gas model for the many-particle Schrodinger equation in d dimensions
    Boghosian, BM
    Taylor, W
    [J]. PHYSICAL REVIEW E, 1998, 57 (01) : 54 - 66
  • [4] QUANTUM COMPUTERS, FACTORING, AND DECOHERENCE
    CHUANG, IL
    LAFLAMME, R
    SHOR, PW
    ZUREK, WH
    [J]. SCIENCE, 1995, 270 (5242) : 1633 - 1635
  • [5] Cleve R, 1998, P ROY SOC A-MATH PHY, V454, P339, DOI 10.1002/(SICI)1099-0526(199809/10)4:1<33::AID-CPLX10>3.0.CO
  • [6] 2-U
  • [7] SIMULATING PHYSICS WITH COMPUTERS
    FEYNMAN, RP
    [J]. INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS, 1982, 21 (6-7) : 467 - 488
  • [8] Johnson W. B., COMMUNICATION
  • [9] KITAEV A, QUANTPH9511026
  • [10] Simulating Ising spin glasses on a quantum computer
    Lidar, DA
    Biham, O
    [J]. PHYSICAL REVIEW E, 1997, 56 (03): : 3661 - 3681