2013

Adiabatic Quantum Simulation of Quantum Chemistry

Babbush, Ryan, Love, Peter J., Aspuru-Guzik, Alán

Understand

We show how to apply the quantum adiabatic algorithm directly to the quantum computation of molecular properties.

We describe a procedure to map electronic structure Hamiltonians to 2-local qubit Hamiltonians with a small set of physically realizable couplings.
By combining the Bravyi-Kitaev construction to map fermions to qubits with perturbative gadgets to reduce the Hamiltonian to 2-local, we obtain precision requirements on the coupling strengths and a number of ancilla qubits that scale polynomially in the problem size.
Hence our mapping is efficient.

Built on

M. Born and V. Fock, “Beweis des Adiabatensatzes,” Zeitschrift für Physik A
1928
Earlier work this paper cites.
P. Jordan and E. Wigner, “über das paulische äquivalenzverbot,” Zeitschrift für Physik
1928
Earlier work this paper cites.
W. H. Freeman, 1979
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness · 1979
Earlier work this paper cites.
F. Barahona, “On the computational complexity of Ising spin glass models,” Journal of Physics A: Mathematical and General
1982
Earlier work this paper cites.
R. P. Feynman, “Simulating physics with computers,” International Journal of Theoretical Physics
1982
Earlier work this paper cites.
L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing
1996
Earlier work this paper cites.
D. A. Meyer, “From quantum cellular automata to quantum lattice gases,” Journal of Statistical Physics
1996
Earlier work this paper cites.
S. Wiesner, “Simulations of many-body quantum systems by a quantum computer,” e-print arXiv:9603028
1996
Earlier work this paper cites.
S. Lloyd, “Universal Quantum Simulators,” Science
1996
Earlier work this paper cites.
E. Bernstein and U. Vazirani, “Quantum complexity theory,” SIAM Journal on Computing
1997
Earlier work this paper cites.
P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing
1997
Earlier work this paper cites.
D. A. Lidar and O. Biham, “Simulating Ising spin glasses on a quantum computer,” Physical Review E (Statistical Physics
1997
Earlier work this paper cites.
B. M. Boghosian and W. Taylor, “Simulating quantum mechanics on a quantum computer,” Physica D-Nonlinear Phenomena
1998
Earlier work this paper cites.
C. Zalka, “Efficient Simulation of Quantum Systems by Quantum Computers,” Fortschritte der Physik
1998
Earlier work this paper cites.
D. S. Abrams and S. Lloyd, “Quantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors,” Physical Review Letters
1999
Earlier work this paper cites.
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, “Quantum Computation by Adiabatic Evolution,” e-print arXiv:0001106
2000
Earlier work this paper cites.
S. Bravyi and A. Kitaev, “Fermionic quantum computation,” Annals of Physics
2000
Earlier work this paper cites.
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, “A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem,” Science
2001
Earlier work this paper cites.
J. Roland and N. J. Cerf, “Quantum search by local adiabatic evolution,” Physical Review A
2002
Earlier work this paper cites.
D. Leibfried, B. Demarco, V. Meyer, M. Rowe, A. Ben-Kish, J. Britton, W. M. Itano, B. Jelenković, C. Langer, T. Rosenband, and D. J. Wineland, “Trapped-Ion Quantum Simulator: Experimental Application to Nonlinear Interferometers,” Physical Review Letters
2002
Earlier work this paper cites.
R. Somma, G. Ortiz, J. Gubernatis, E. Knill, and R. Laflamme, “Simulating physical phenomena by quantum networks,” Physical Review A
2002
Earlier work this paper cites.
T. Hogg, “Adiabatic quantum computing for random satisfiability problems,” Physical Review A
2003
Earlier work this paper cites.
J. Roland and N. J. Cerf, “Adiabatic quantum search algorithm for structured problems,” Physical Review A
2003
Earlier work this paper cites.
A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential algorithmic speedup by a quantum walk,” Proceedings of the thirty-fifth annual ACM symposium on Theory of computing
2003
Earlier work this paper cites.
J. Kempe, A. Kitaev, and O. Regev, “The Complexity of the Local Hamiltonian Problem,” SIAM Journal on Computing
2004
Earlier work this paper cites.
R. Oliveira and B. M. Terhal, “The complexity of quantum spin systems on a two-dimensional square lattice,” Quant Inf Comp
2005
Earlier work this paper cites.
F. Verstraete and J. I. Cirac, “Mapping local Hamiltonians of fermions to local Hamiltonians of spins,” Journal of Statistical Mechanics: Theory and Experiment
2005
Earlier work this paper cites.
A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, “Simulated Quantum Computation of Molecular Energies,” Science
2006
Earlier work this paper cites.
R. Harris, A. J. Berkley, M. W. Johnson, P. Bunyk, S. Govorkov, M. C. Thom, S. Uchaikin, Wilson, AB, J. Chung, and E. Holtham, “Sign-and magnitude-tunable coupler for superconducting flux qubits,” Physical Review Letters
2007
Earlier work this paper cites.
D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, “Efficient Quantum Algorithms for Simulating Sparse Hamiltonians,” Communications In Mathematical Physics
2007
Earlier work this paper cites.
J. D. Biamonte and P. J. Love, “Realizable Hamiltonians for Universal Adiabatic Quantum Computers,” Physical Review A
2007
Earlier work this paper cites.
D. Nagaj and S. Mozes, “New construction for a QMA complete three-local Hamiltonian,” Journal of Mathematical Physics
2007
Earlier work this paper cites.
R. Harris, M. W. Johnson, S. Han, A. J. Berkley, J. Johansson, P. Bunyk, E. Ladizinsky, S. Govorkov, M. C. Thom, S. Uchaikin, B. Bumble, A. Fung, A. Kaul, A. Kleinsasser, M. H. S. Amin, and D. V. Averin, “Probing Noise in Flux Qubits via Macroscopic Resonant Tunneling,” Physical Review Letters
2008
Earlier work this paper cites.

Similar

I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni, and A. Aspuru-Guzik, “Polynomial-time quantum algorithm for the simulation of chemical dynamics,” Proceedings of the National Academy of Sciences
2008
Cited alongside, same era.
N. J. Ward, I. Kassal, and A. Aspuru-Guzik, “Preparation of many-body states for quantum simulation,” Journal Of Chemical Physics
2008
Cited alongside, same era.
A. Friedenauer, H. Schmitz, J. T. Glueckert, D. Porras, and T. Schaetz, “Simulating a quantum magnet with trapped ions,” Nature Physics
2008
Cited alongside, same era.
S. P. Jordan and E. Farhi, “Perturbative Gadgets at Arbitrary Orders,” Physical Review A
2008
Cited alongside, same era.
H. Wang, S. Kais, A. Aspuru-Guzik, and M. R. Hoffmann, “Quantum algorithm for obtaining the energy spectrum of molecular systems.,” Physical chemistry chemical physics : PCCP
2008
Cited alongside, same era.
S. Bravyi, D. P. DiVincenzo, D. Loss, and B. M. Terhal, “Quantum simulation of many-body Hamiltonians using perturbation theory with bounded-strength interactions.,” Physical review letters
2008
Cited alongside, same era.
J. D. Biamonte, “Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins,” Physical Review A
2008
Cited alongside, same era.
S. Bravyi, D. P. DiVincenzo, R. I. Oliveira, and B. M. Terhal, “The Complexity of Stoquastic Local Hamiltonian Problems,” Quantum Information & Computation
Original
2008
Cited alongside, same era.
S. Boixo and R. D. Somma, “Necessary Condition for the Quantum Adiabatic Approximation,” Physical Review A
2009
Cited alongside, same era.
H. Neven, V. S. Denchev, G. Rose, and W. G. Macready, “Training a Large Scale Classifier with the Quantum Adiabatic Algorithm,” e-print arXiv:09120779
2009
Cited alongside, same era.
R. Harris, F. Brito, A. J. Berkley, J. Johansson, M. W. Johnson, T. Lanting, P. Bunyk, E. Ladizinsky, B. Bumble, and A. Fung, “Synchronization of multiple coupled rf-SQUID flux qubits,” New Journal Of Physics
2009
Cited alongside, same era.
R. Harris, T. Lanting, A. J. Berkley, J. Johansson, M. W. Johnson, P. Bunyk, E. Ladizinsky, N. Ladizinsky, T. Oh, and S. Han, “Compound Josephson-junction coupler for flux qubits with minimal crosstalk,” Physical Review B
2009
Cited alongside, same era.

Then

Q.-H. Duan and P.-X. Chen, “Realization of Universal Adiabatic Quantum Computation with Fewer Physical Resources,” Physical Review A
2011
Later among the works it cites.
E. Farhi, D. Gosset, I. Hen, A. Sandvik, A. Young, P. Shor, and F. Zamponi, “Performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs,” Physical Review A
2012
Later among the works it cites.
A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik, “Finding low-energy conformations of lattice protein models by quantum annealing,” Scientific Reports
2012
Later among the works it cites.
R. Babbush, A. Perdomo-ortiz, B. O. Gorman, W. Macready, A. Aspuru-Guzik, and B. O’Gorman, “Construction of Energy Functions for Lattice Heteropolymer Models : A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization,” e-print arXiv:1211.3422
Original
2012
Later among the works it cites.
V. S. Denchev, N. Ding, S. V. N. Vishwanathan, and H. Neven, “Robust Classification with Adiabatic Quantum Optimization,” Proc Int Conf on Machine Learning
2012
Later among the works it cites.
S. Garnerone, P. Zanardi, and D. A. Lidar, “Adiabatic Quantum Algorithm for Search Engine Ranking,” Physical Review Letters
2012
Later among the works it cites.
V. N. Smelyanskiy, E. G. Rieffel, S. I. Knysh, C. P. Williams, M. W. Johnson, M. C. Thom, W. G. Macready, and K. L. Pudenz, “A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration,” Electrical Engineering
2012
Later among the works it cites.
S. Raeisi, N. Wiebe, and B. C. Sanders, “Quantum-circuit design for efficient simulations of many-body quantum dynamics,” New Journal Of Physics
2012
Later among the works it cites.
X.-S. Ma, B. Dakić, S. Kropatsche, W. Naylor, Y.-h. Chan, Z.-x. Gong, L.-m. Duan, A. Zeilinger, and P. Walther, “Photonic quantum simulation of ground state configurations of Heisenberg square and checkerboard lattice spin systems,” e-print arXiv:1205.2801
Original
2012
Later among the works it cites.
N. Cody Jones, J. D. Whitfield, P. L. McMahon, M.-H. Yung, R. V. Meter, A. Aspuru-Guzik, and Y. Yamamoto, “Faster quantum chemistry simulation on fault-tolerant quantum computers,” New Journal of Physics
2012
Later among the works it cites.
J. T. Seeley, M. J. Richard, and P. J. Love, “The Bravyi-Kitaev transformation for quantum computation of electronic structure,” Journal of Chemical Physics
2012
Later among the works it cites.
S. Boixo, T. F. Ronnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, M. Troyer, and I. V. Sergei, “Quantum annealing with more than one hundred qubits,” e-print arxiv:1304.4595
Original
2013
Closest in time.
A. J. Berkley, A. J. Przybysz, T. Lanting, R. Harris, N. Dickson, F. Altomare, M. H. Amin, P. Bunyk, C. Enderud, E. Hoskinson, M. W. Johnson, E. Ladizinsky, R. Neufeld, C. Rich, A. Y. Smirnov, E. Tolkacheva, S. Uchaikin, and A. B. Wilson, “Tunneling spectroscopy using a probe qubit,” Physical Review B
2013
Closest in time.
N. G. Dickson, M. W. Johnson, M. H. Amin, R. Harris, F. Altomare, a. J. Berkley, P. Bunyk, J. Cai, E. M. Chapple, P. Chavez, F. Cioata, T. Cirip, P. Debuen, M. Drew-Brook, C. Enderud, S. Gildert, F. Hamze, J. P. Hilton, E. Hoskinson, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Lanting, T. Mahon, R. Neufeld, T. Oh, I. Perminov, C. Petroff, A. Przybysz, C. Rich, P. Spear, A. Tcaciuc, M. C. Thom, E. Tolkacheva, S. Uchaikin, J. Wang, a. B. Wilson, Z. Merali, and G. Rose, “Thermally assisted quantum annealing of a 16-qubit problem.,” Nature communications
2013
Closest in time.
K. L. Pudenz, T. Albash, and D. A. Lidar, “Error corrected quantum annealing with hundreds of qubits,” e-print arXiv:1307.8190
Original
2013
Closest in time.
Z. Bian, F. Chudak, W. G. Macready, L. Clark, and F. Gaitan, “Experimental Determination of Ramsey Numbers,” Physical Review Letters
2013
Closest in time.
L. Wang, T. F. Ronnow, S. Boixo, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, and M. Troyer, “Comment on: ”Classical signature of quantum annealing”.,” e-print arXiv:1305.5837
Original
2013
Closest in time.
J. A. Smolin and G. Smith, “Classical signatures of quantum annealing,” e-print arXiv:1305.4904
Original
2013
Closest in time.
B. C. Sanders, “Efficient Algorithms for Universal Quantum Simulation,” Lecture Notes in Computer Science
2013
Closest in time.
J. P. Hague, S. Downes, C. MacCormick, and P. E. Kornilovitch, “Cold Rydberg atoms for quantum simulation of exotic condensed matter interactions,” Journal of Superconductivity and Novel Magnetism
2013
Closest in time.
I. Cohen and A. Retzker, “Quantum Simulation of the Haldane Phase Using Trapped Ions,” e-print arXiv:1310.3715
Original
2013
Closest in time.
P. Hauke, D. Marcos, M. Dalmonte, and P. Zoller, “Quantum simulation of a lattice Schwinger model in a chain of trapped ions,” Physical Review X
2013
Closest in time.
P. Richerme, C. Senko, J. Smith, A. Lee, S. Korenblit, and C. Monroe, “Experimental performance of a quantum simulator: Optimizing adiabatic evolution and identifying many-body ground states,” Physical Review A
2013
Closest in time.
D. Wecker, B. Bauer, B. K. Clark, M. B. Hastings, and M. Troyer, “Can quantum chemistry be performed on a small quantum computer?,” e-print arXiv:1312.1695
Original
2013
Closest in time.
B. Toloui and P. J. Love, “Quantum Algorithms for Quantum Chemistry based on the sparsity of the CI-matrix,” e-print arXiv:1312.2579
Original
2013
Closest in time.
A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, “A variational eigenvalue solver on a quantum processor,” e-print 1304.3061
2013
Closest in time.
J. Welch, D. Greenbaum, S. Mostame, and A. Aspuru-Guzik, “Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas,” e-print arXiv:1306.3991
Original
2013
Closest in time.
J. D. Whitfield, “Spin-free quantum computational simulations and symmetry adapted states,” Journal of Chemical Physics
2013
Closest in time.
M. H. Yung, J. Casanova, A. Mezzacapo, J. McClean, L. Lamata, A. Aspuru-Guzik, and E. Solano, “From transistor to trapped-ion computers for quantum chemistry,” e-print arXiv:1307.4326
Original
2013
Closest in time.
Y. Cao, R. Babbush, J. Biamonte, and S. Kais, “Experimentally Realizable Hamiltonian Gadgets,” e-print arXiv:1311.2555
Original
2013
Closest in time.
J. D. Whitfield, P. J. Love, and A. Aspuru-Guzik, “Computational complexity in electronic structure,” Physical Chemistry Chemical Physics
2013
Closest in time.
R. Babbush, B. O’Gorman, and A. A. Aspuru-Guzik, “Resource efficient gadgets for compiling adiabatic quantum optimization problems,” Annalen der Physik
2013
Closest in time.
D. Gosset and D. Nagaj, “Quantum 3-SAT is QMA1-complete,” e-print arXiv:1302.0290
Original
2013
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…