DOI: 10.1073/pnas.0808245105. Polynomial-time quantum algorithm for the simulation of chemical dynamics

Polynomial-time quantum algorithm for the simulation of chemical dynamics

10.1073/pnas.0808245105

Crossref journal-article

Proceedings of the National Academy of Sciences

Proceedings of the National Academy of Sciences (341)

Abstract

The computational cost of exact methods for quantum simulation using classical computers grows exponentially with system size. As a consequence, these techniques can be applied only to small systems. By contrast, we demonstrate that quantum computers could exactly simulate chemical reactions in polynomial time. Our algorithm uses the split-operator approach and explicitly simulates all electron-nuclear and interelectronic interactions in quadratic time. Surprisingly, this treatment is not only more accurate than the Born–Oppenheimer approximation but faster and more efficient as well, for all reactions with more than about four atoms. This is the case even though the entire electronic wave function is propagated on a grid with appropriately short time steps. Although the preparation and measurement of arbitrary states on a quantum computer is inefficient, here we demonstrate how to prepare states of chemical interest efficiently. We also show how to efficiently obtain chemically relevant observables, such as state-to-state transition probabilities and thermal reaction rates. Quantum computers using these techniques could outperform current classical computers with 100 qubits.

Bibliography

Kassal, I., Jordan, S. P., Love, P. J., Mohseni, M., & Aspuru-Guzik, A. (2008). Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proceedings of the National Academy of Sciences, 105(48), 18681â18686.

Authors 5

Ivan Kassal (first)
Stephen P. Jordan (additional)
Peter J. Love (additional)
Masoud Mohseni (additional)
Alán Aspuru-Guzik (additional)

References 42 Referenced 273

10.1063/1.463007
10.1063/1.1560636
10.1063/1.476142
10.1126/science.1104085
10.1063/1.1323746
10.1016/j.jphotochem.2007.05.015
10.1021/jp994174i
10.1146/annurev.physchem.57.032905.104612
10.1088/0953-4075/34/3/103
10.1103/PhysRevLett.94.063002
10.1126/science.286.5449.2474
10.1126/science.1120263
10.1007/BF02650179
10.1126/science.273.5278.1073
10.1098/rspa.1998.0162
S Wiesner Simulations of many-body quantum systems by a quantum computer. arXiv:quant-ph/9603028. (1996).
10.1103/PhysRevE.59.2429
10.1126/science.1113479
AM Steane, How to build a 300 bit, 1 giga-operation quantum computer. Quant Inf Comput 7, 171–183 (2007). / Quant Inf Comput / How to build a 300 bit, 1 giga-operation quantum computer by Steane AM (2007)
10.1016/0021-9991(82)90091-2
10.1016/0021-9991(83)90015-3
D Coppersmith An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph/0201067. (2002).
E Bernstein U Vazirani Quantum complexity theory. (Assoc for Comput Machinery New York) pp. 11–20 (1993). (10.1145/167088.167097)
10.1007/s00220-006-0150-x
DE Knuth Art of Computer Programming, Vol 2: Seminumerical Algorithms (Addison–Wesley, 3rd Ed., Boston, 1997). / Art of Computer Programming, Vol 2: Seminumerical Algorithms by Knuth DE (1997)
MA Nielsen, IL Chuang Quantum Computation and Quantum Information (Cambridge Univ Press, 1st Ed., Cambridge, UK, 2000). / Quantum Computation and Quantum Information by Nielsen MA (2000)
10.1103/PhysRevE.73.036708
10.1063/1.471430
D Aharonov A Ta-Shma Adiabatic quantum state generation and statistical zero knowledge. (Assoc for Comput Machinery New York) pp. 20–29 (2003). (10.1145/780542.780546)
L Grover T Rudolph Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:quant-ph/0208112. (2002).
10.1103/PhysRevLett.79.2586
10.1103/PhysRevLett.83.5162
10.1103/PhysRevLett.97.170501
10.1126/science.1145699
10.1103/PhysRevLett.96.010401
G Brassard P Hoyer M Mosca A Tapp Quantum amplitude amplification and estimation. arXiv:quant-ph/0005055. (2000).
10.1103/PhysRevA.75.012328
DJ Tannor Introduction to Quantum Mechanics: A Time-Dependent Perspective (Univ Sci Books, Mill Valley, CA, 2007). / Introduction to Quantum Mechanics: A Time-Dependent Perspective by Tannor DJ (2007)
10.1063/1.460139
10.1103/RevModPhys.67.279
10.1063/1.2358137
10.1209/0295-5075/80/67008

Dates

Type	When
Created	16 years, 9 months ago (Nov. 24, 2008, 9:56 p.m.)
Deposited	3 years, 4 months ago (April 12, 2022, 5:40 p.m.)
Indexed	4 days, 23 hours ago (Aug. 28, 2025, 8:10 a.m.)
Issued	16 years, 9 months ago (Dec. 2, 2008)
Published	16 years, 9 months ago (Dec. 2, 2008)
Published Online	16 years, 9 months ago (Dec. 2, 2008)
Published Print	16 years, 9 months ago (Dec. 2, 2008)

Funders 0

None

BibTeX

@article{Kassal_2008, title={Polynomial-time quantum algorithm for the simulation of chemical dynamics}, volume={105}, ISSN={1091-6490}, url={http://dx.doi.org/10.1073/pnas.0808245105}, DOI={10.1073/pnas.0808245105}, number={48}, journal={Proceedings of the National Academy of Sciences}, publisher={Proceedings of the National Academy of Sciences}, author={Kassal, Ivan and Jordan, Stephen P. and Love, Peter J. and Mohseni, Masoud and Aspuru-Guzik, Alán}, year={2008}, month=dec, pages={18681–18686} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        28
      ]
    ],
    "date-time": "2025-08-28T12:10:30Z",
    "timestamp": 1756383030371
  },
  "reference-count": 42,
  "publisher": "Proceedings of the National Academy of Sciences",
  "issue": "48",
  "content-domain": {
    "domain": [
      "www.pnas.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        2008,
        12,
        2
      ]
    ]
  },
  "abstract": "<jats:p>The computational cost of exact methods for quantum simulation using classical computers grows exponentially with system size. As a consequence, these techniques can be applied only to small systems. By contrast, we demonstrate that quantum computers could exactly simulate chemical reactions in polynomial time. Our algorithm uses the split-operator approach and explicitly simulates all electron-nuclear and interelectronic interactions in quadratic time. Surprisingly, this treatment is not only more accurate than the Born\u2013Oppenheimer approximation but faster and more efficient as well, for all reactions with more than about four atoms. This is the case even though the entire electronic wave function is propagated on a grid with appropriately short time steps. Although the preparation and measurement of arbitrary states on a quantum computer is inefficient, here we demonstrate how to prepare states of chemical interest efficiently. We also show how to efficiently obtain chemically relevant observables, such as state-to-state transition probabilities and thermal reaction rates. Quantum computers using these techniques could outperform current classical computers with 100 qubits.</jats:p>",
  "DOI": "10.1073/pnas.0808245105",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2008,
        11,
        25
      ]
    ],
    "date-time": "2008-11-25T02:56:49Z",
    "timestamp": 1227581809000
  },
  "page": "18681-18686",
  "update-policy": "http://dx.doi.org/10.1073/pnas.cm10313",
  "source": "Crossref",
  "is-referenced-by-count": 273,
  "title": "Polynomial-time quantum algorithm for the simulation of chemical dynamics",
  "prefix": "10.1073",
  "volume": "105",
  "author": [
    {
      "given": "Ivan",
      "family": "Kassal",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Department of Chemistry and Chemical Biology, Harvard University, Cambridge, MA 02138;"
        }
      ]
    },
    {
      "given": "Stephen P.",
      "family": "Jordan",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, MA 02139; and"
        }
      ]
    },
    {
      "given": "Peter J.",
      "family": "Love",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Department of Physics, Haverford College, Haverford, PA 19041"
        }
      ]
    },
    {
      "given": "Masoud",
      "family": "Mohseni",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Department of Chemistry and Chemical Biology, Harvard University, Cambridge, MA 02138;"
        }
      ]
    },
    {
      "given": "Al\u00e1n",
      "family": "Aspuru-Guzik",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Department of Chemistry and Chemical Biology, Harvard University, Cambridge, MA 02138;"
        }
      ]
    }
  ],
  "member": "341",
  "published-online": {
    "date-parts": [
      [
        2008,
        12,
        2
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_3_3_1_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1063/1.463007"
    },
    {
      "key": "e_1_3_3_2_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1063/1.1560636"
    },
    {
      "key": "e_1_3_3_3_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1063/1.476142"
    },
    {
      "key": "e_1_3_3_4_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.1104085"
    },
    {
      "key": "e_1_3_3_5_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1063/1.1323746"
    },
    {
      "key": "e_1_3_3_6_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/j.jphotochem.2007.05.015"
    },
    {
      "key": "e_1_3_3_7_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1021/jp994174i"
    },
    {
      "key": "e_1_3_3_8_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1146/annurev.physchem.57.032905.104612"
    },
    {
      "key": "e_1_3_3_9_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1088/0953-4075/34/3/103"
    },
    {
      "key": "e_1_3_3_10_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.94.063002"
    },
    {
      "key": "e_1_3_3_11_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.286.5449.2474"
    },
    {
      "key": "e_1_3_3_12_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.1120263"
    },
    {
      "key": "e_1_3_3_13_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02650179"
    },
    {
      "key": "e_1_3_3_14_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.273.5278.1073"
    },
    {
      "key": "e_1_3_3_15_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1098/rspa.1998.0162"
    },
    {
      "key": "e_1_3_3_16_2",
      "unstructured": "S Wiesner Simulations of many-body quantum systems by a quantum computer. arXiv:quant-ph/9603028. (1996)."
    },
    {
      "key": "e_1_3_3_17_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevE.59.2429"
    },
    {
      "key": "e_1_3_3_18_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.1113479"
    },
    {
      "key": "e_1_3_3_19_2",
      "first-page": "171",
      "article-title": "How to build a 300 bit, 1 giga-operation quantum computer",
      "volume": "7",
      "author": "Steane AM",
      "year": "2007",
      "unstructured": "AM Steane, How to build a 300 bit, 1 giga-operation quantum computer. Quant Inf Comput 7, 171\u2013183 (2007).",
      "journal-title": "Quant Inf Comput"
    },
    {
      "key": "e_1_3_3_20_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0021-9991(82)90091-2"
    },
    {
      "key": "e_1_3_3_21_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0021-9991(83)90015-3"
    },
    {
      "key": "e_1_3_3_22_2",
      "unstructured": "D Coppersmith An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph/0201067. (2002)."
    },
    {
      "key": "e_1_3_3_23_2",
      "doi-asserted-by": "crossref",
      "unstructured": "E Bernstein U Vazirani Quantum complexity theory.  (Assoc for Comput Machinery New York) pp. 11\u201320 (1993).",
      "DOI": "10.1145/167088.167097"
    },
    {
      "key": "e_1_3_3_24_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/s00220-006-0150-x"
    },
    {
      "key": "e_1_3_3_25_2",
      "volume-title": "Art of Computer Programming, Vol 2: Seminumerical Algorithms",
      "author": "Knuth DE",
      "year": "1997",
      "unstructured": "DE Knuth Art of Computer Programming, Vol 2: Seminumerical Algorithms (Addison\u2013Wesley, 3rd Ed., Boston, 1997).",
      "edition": "3"
    },
    {
      "key": "e_1_3_3_26_2",
      "volume-title": "Quantum Computation and Quantum Information",
      "author": "Nielsen MA",
      "year": "2000",
      "unstructured": "MA Nielsen, IL Chuang Quantum Computation and Quantum Information (Cambridge Univ Press, 1st Ed., Cambridge, UK, 2000).",
      "edition": "1"
    },
    {
      "key": "e_1_3_3_27_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevE.73.036708"
    },
    {
      "key": "e_1_3_3_28_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1063/1.471430"
    },
    {
      "key": "e_1_3_3_29_2",
      "doi-asserted-by": "crossref",
      "unstructured": "D Aharonov A Ta-Shma Adiabatic quantum state generation and statistical zero knowledge.  (Assoc for Comput Machinery New York) pp. 20\u201329 (2003).",
      "DOI": "10.1145/780542.780546"
    },
    {
      "key": "e_1_3_3_30_2",
      "unstructured": "L Grover T Rudolph Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:quant-ph/0208112. (2002)."
    },
    {
      "key": "e_1_3_3_31_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.79.2586"
    },
    {
      "key": "e_1_3_3_32_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.83.5162"
    },
    {
      "key": "e_1_3_3_33_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.97.170501"
    },
    {
      "key": "e_1_3_3_34_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1126/science.1145699"
    },
    {
      "key": "e_1_3_3_35_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevLett.96.010401"
    },
    {
      "key": "e_1_3_3_36_2",
      "unstructured": "G Brassard P Hoyer M Mosca A Tapp Quantum amplitude amplification and estimation. arXiv:quant-ph/0005055. (2000)."
    },
    {
      "key": "e_1_3_3_37_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/PhysRevA.75.012328"
    },
    {
      "key": "e_1_3_3_38_2",
      "volume-title": "Introduction to Quantum Mechanics: A Time-Dependent Perspective",
      "author": "Tannor DJ",
      "year": "2007",
      "unstructured": "DJ Tannor Introduction to Quantum Mechanics: A Time-Dependent Perspective (Univ Sci Books, Mill Valley, CA, 2007)."
    },
    {
      "key": "e_1_3_3_39_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1063/1.460139"
    },
    {
      "key": "e_1_3_3_40_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1103/RevModPhys.67.279"
    },
    {
      "key": "e_1_3_3_41_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1063/1.2358137"
    },
    {
      "key": "e_1_3_3_42_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1209/0295-5075/80/67008"
    }
  ],
  "container-title": "Proceedings of the National Academy of Sciences",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://pnas.org/doi/pdf/10.1073/pnas.0808245105",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2022,
        4,
        12
      ]
    ],
    "date-time": "2022-04-12T21:40:27Z",
    "timestamp": 1649799627000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://pnas.org/doi/full/10.1073/pnas.0808245105"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2008,
        12,
        2
      ]
    ]
  },
  "references-count": 42,
  "journal-issue": {
    "issue": "48",
    "published-print": {
      "date-parts": [
        [
          2008,
          12,
          2
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1073/pnas.0808245105"
  ],
  "URL": "http://dx.doi.org/10.1073/pnas.0808245105",
  "relation": {},
  "ISSN": [
    "0027-8424",
    "1091-6490"
  ],
  "subject": [],
  "container-title-short": "Proc. Natl. Acad. Sci. U.S.A.",
  "published": {
    "date-parts": [
      [
        2008,
        12,
        2
      ]
    ]
  },
  "assertion": [
    {
      "value": "2008-08-22",
      "order": 0,
      "name": "received",
      "label": "Received",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    },
    {
      "value": "2008-12-02",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}