{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T21:19:24Z","timestamp":1781644764837,"version":"3.54.5"},"reference-count":42,"publisher":"National Academy of Sciences","issue":"38","license":[{"start":{"date-parts":[[2019,3,6]],"date-time":"2019-03-06T00:00:00Z","timestamp":1551830400000},"content-version":"vor","delay-in-days":181,"URL":"http:\/\/www.pnas.org\/site\/aboutpnas\/licenses.xhtml"}],"funder":[{"DOI":"10.13039\/100000183","name":"DOD | United States Army | RDECOM | Army Research Office","doi-asserted-by":"publisher","award":["W911NF-16-1-0349"],"award-info":[{"award-number":["W911NF-16-1-0349"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007631","name":"Canadian Institute for Advanced Research","doi-asserted-by":"publisher","award":["none"],"award-info":[{"award-number":["none"]}],"id":[{"id":"10.13039\/100007631","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1526380"],"award-info":[{"award-number":["1526380"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.pnas.org"],"crossmark-restriction":true},"short-container-title":["Proc. Natl. Acad. Sci. U.S.A."],"published-print":{"date-parts":[[2018,9,18]]},"abstract":"<jats:p>With quantum computers of significant size now on the horizon, we should understand how to best exploit their initially limited abilities. To this end, we aim to identify a practical problem that is beyond the reach of current classical computers, but that requires the fewest resources for a quantum computer. We consider quantum simulation of spin systems, which could be applied to understand condensed matter phenomena. We synthesize explicit circuits for three leading quantum simulation algorithms, using diverse techniques to tighten error bounds and optimize circuit implementations. Quantum signal processing appears to be preferred among algorithms with rigorous performance guarantees, whereas higher-order product formulas prevail if empirical error estimates suffice. Our circuits are orders of magnitude smaller than those for the simplest classically infeasible instances of factoring and quantum chemistry, bringing practical quantum computation closer to reality.<\/jats:p>","DOI":"10.1073\/pnas.1801723115","type":"journal-article","created":{"date-parts":[[2018,9,6]],"date-time":"2018-09-06T15:26:09Z","timestamp":1536247569000},"page":"9456-9461","update-policy":"https:\/\/doi.org\/10.1073\/pnas.cm10313","source":"Crossref","is-referenced-by-count":453,"title":["Toward the first quantum simulation with quantum speedup"],"prefix":"10.1073","volume":"115","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9903-837X","authenticated-orcid":false,"given":"Andrew M.","family":"Childs","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD 20742;"},{"name":"Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742;"},{"name":"Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7381-4556","authenticated-orcid":false,"given":"Dmitri","family":"Maslov","sequence":"additional","affiliation":[{"name":"Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742;"},{"name":"Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742;"},{"name":"Division of Computing and Communication Foundations, National Science Foundation, Alexandria, VA 22314;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yunseong","family":"Nam","sequence":"additional","affiliation":[{"name":"Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742;"},{"name":"Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742;"},{"name":"IonQ, Inc., College Park, MD 20740;"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Neil J.","family":"Ross","sequence":"additional","affiliation":[{"name":"Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742;"},{"name":"Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742;"},{"name":"Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 4R2, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuan","family":"Su","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD 20742;"},{"name":"Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742;"},{"name":"Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, MD 20742;"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"341","published-online":{"date-parts":[[2018,9,6]]},"reference":[{"key":"e_1_3_4_1_2","doi-asserted-by":"crossref","first-page":"220502","DOI":"10.1103\/PhysRevLett.113.220502","article-title":"Qubit architecture with high coherence and fast tunable coupling","volume":"113","author":"Chen Y","year":"2014","unstructured":"Y Chen, , Qubit architecture with high coherence and fast tunable coupling. Phys Rev Lett 113, 220502 (2014).","journal-title":"Phys Rev Lett"},{"key":"e_1_3_4_2_2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1038\/nature18648","article-title":"Demonstration of a small programmable quantum computer with atomic qubits","volume":"536","author":"Debnath S","year":"2016","unstructured":"S Debnath, , Demonstration of a small programmable quantum computer with atomic qubits. Nature 536, 63\u201366 (2016).","journal-title":"Nature"},{"key":"e_1_3_4_3_2","doi-asserted-by":"crossref","first-page":"180511","DOI":"10.1103\/PhysRevLett.119.180511","article-title":"10-qubit entanglement and parallel logic operations with a superconducting circuit","volume":"119","author":"Song C","year":"2017","unstructured":"C Song, , 10-qubit entanglement and parallel logic operations with a superconducting circuit. Phys Rev Lett 119, 180511 (2017).","journal-title":"Phys Rev Lett"},{"key":"e_1_3_4_4_2","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1038\/nature24622","article-title":"Probing many-body dynamics on a 51-atom quantum simulator","volume":"551","author":"Bernien H","year":"2017","unstructured":"H Bernien, , Probing many-body dynamics on a 51-atom quantum simulator. Nature 551, 579\u2013584 (2017).","journal-title":"Nature"},{"key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1038\/nature24654","article-title":"Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator","volume":"551","author":"Zhang J","year":"2017","unstructured":"J Zhang, , Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator. Nature 551, 601\u2013604 (2017).","journal-title":"Nature"},{"key":"e_1_3_4_6_2","doi-asserted-by":"crossref","first-page":"3305","DOI":"10.1073\/pnas.1618020114","article-title":"Experimental comparison of two quantum computing architectures","volume":"114","author":"Linke NM","year":"2017","unstructured":"NM Linke, , Experimental comparison of two quantum computing architectures. Proc Natl Acad Sci USA 114, 3305\u20133310 (2017).","journal-title":"Proc Natl Acad Sci USA"},{"key":"e_1_3_4_7_2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1038\/nature23458","article-title":"Quantum computational supremacy","volume":"549","author":"Harrow AW","year":"2017","unstructured":"AW Harrow, A Montanaro, Quantum computational supremacy. Nature 549, 203\u2013209 (2017).","journal-title":"Nature"},{"key":"e_1_3_4_8_2","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02650179","article-title":"Simulating physics with computers","volume":"21","author":"Feynman RP","year":"1982","unstructured":"RP Feynman, Simulating physics with computers. Int J Theor Phys 21, 467\u2013488 (1982).","journal-title":"Int J Theor Phys"},{"key":"e_1_3_4_9_2","doi-asserted-by":"crossref","first-page":"062318","DOI":"10.1103\/PhysRevA.92.062318","article-title":"Solving strongly correlated electron models on a quantum computer","volume":"92","author":"Wecker D","year":"2015","unstructured":"D Wecker, , Solving strongly correlated electron models on a quantum computer. Phys Rev A 92, 062318 (2015).","journal-title":"Phys Rev A"},{"key":"e_1_3_4_10_2","doi-asserted-by":"crossref","first-page":"022305","DOI":"10.1103\/PhysRevA.90.022305","article-title":"Gate count estimates for performing quantum chemistry on small quantum computers","volume":"90","author":"Wecker D","year":"2014","unstructured":"D Wecker, B Bauer, BK Clark, MB Hastings, M Troyer, Gate count estimates for performing quantum chemistry on small quantum computers. Phys Rev A 90, 022305 (2014).","journal-title":"Phys Rev A"},{"key":"e_1_3_4_11_2","doi-asserted-by":"crossref","first-page":"1130","DOI":"10.1126\/science.1217069","article-title":"Quantum algorithms for quantum field theories","volume":"336","author":"Jordan SP","year":"2012","unstructured":"SP Jordan, KSM Lee, J Preskill, Quantum algorithms for quantum field theories. Science 336, 1130\u20131133 (2012).","journal-title":"Science"},{"key":"e_1_3_4_12_2","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1126\/science.273.5278.1073","article-title":"Universal quantum simulators","volume":"273","author":"Lloyd S","year":"1996","unstructured":"S Lloyd, Universal quantum simulators. Science 273, 1073\u20131078 (1996).","journal-title":"Science"},{"key":"e_1_3_4_13_2","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/s00220-006-0150-x","article-title":"Efficient quantum algorithms for simulating sparse Hamiltonians","volume":"270","author":"Berry DW","year":"2007","unstructured":"DW Berry, G Ahokas, R Cleve, BC Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians. Commun Math Phys 270, 359\u2013371 (2007).","journal-title":"Commun Math Phys"},{"key":"e_1_3_4_14_2","first-page":"29","article-title":"Black-box Hamiltonian simulation and unitary implementation","volume":"12","author":"Berry DW","year":"2012","unstructured":"DW Berry, AM Childs, Black-box Hamiltonian simulation and unitary implementation. Quantum Inf Comput 12, 29\u201362 (2012).","journal-title":"Quantum Inf Comput"},{"key":"e_1_3_4_15_2","doi-asserted-by":"crossref","first-page":"090502","DOI":"10.1103\/PhysRevLett.114.090502","article-title":"Simulating Hamiltonian dynamics with a truncated Taylor series","volume":"114","author":"Berry DW","year":"2015","unstructured":"DW Berry, AM Childs, R Cleve, R Kothari, RD Somma, Simulating Hamiltonian dynamics with a truncated Taylor series. Phys Rev Lett 114, 090502 (2015).","journal-title":"Phys Rev Lett"},{"key":"e_1_3_4_16_2","unstructured":"GH Low IL Chuang Hamiltonian simulation by qubitization. arXiv:1610.06546. (2016)."},{"key":"e_1_3_4_17_2","doi-asserted-by":"crossref","first-page":"010501","DOI":"10.1103\/PhysRevLett.118.010501","article-title":"Optimal Hamiltonian simulation by quantum signal processing","volume":"118","author":"Low GH","year":"2017","unstructured":"GH Low, IL Chuang, Optimal Hamiltonian simulation by quantum signal processing. Phys Rev Lett 118, 010501 (2017).","journal-title":"Phys Rev Lett"},{"key":"e_1_3_4_18_2","doi-asserted-by":"crossref","first-page":"081103","DOI":"10.1103\/PhysRevB.91.081103","article-title":"Many-body localization edge in the random-field Heisenberg chain","volume":"91","author":"Luitz DJ","year":"2015","unstructured":"DJ Luitz, N Laflorencie, F Alet, Many-body localization edge in the random-field Heisenberg chain. Phys Rev B 91, 081103 (2015).","journal-title":"Phys Rev B"},{"key":"e_1_3_4_19_2","doi-asserted-by":"crossref","first-page":"147204","DOI":"10.1103\/PhysRevLett.113.147204","article-title":"Interferometric probes of many-body localization","volume":"113","author":"Serbyn M","year":"2014","unstructured":"M Serbyn, , Interferometric probes of many-body localization. Phys Rev Lett 113, 147204 (2014).","journal-title":"Phys Rev Lett"},{"key":"e_1_3_4_20_2","doi-asserted-by":"crossref","first-page":"842","DOI":"10.1126\/science.aaa7432","article-title":"Observation of many-body localization of interacting fermions in a quasirandom optical lattice","volume":"349","author":"Schreiber M","year":"2015","unstructured":"M Schreiber, , Observation of many-body localization of interacting fermions in a quasirandom optical lattice. Science 349, 842\u2013845 (2015).","journal-title":"Science"},{"key":"e_1_3_4_21_2","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1038\/nphys3783","article-title":"Many-body localization in a quantum simulator with programmable random disorder","volume":"12","author":"Smith J","year":"2016","unstructured":"J Smith, , Many-body localization in a quantum simulator with programmable random disorder. Nat Phys 12, 907\u2013911 (2016).","journal-title":"Nat Phys"},{"key":"e_1_3_4_22_2","first-page":"283","volume-title":"Proceedings of the 46th ACM Symposium on Theory of Computing","author":"Berry DW","year":"2014","unstructured":"DW Berry, AM Childs, R Cleve, R Kothari, RD Somma, Exponential improvement in precision for simulating sparse Hamiltonians. Proceedings of the 46th ACM Symposium on Theory of Computing (Assoc Comput Machinery, New York), pp. 283\u2013292 (2014)."},{"key":"e_1_3_4_23_2","first-page":"792","volume-title":"Proceedings of the 56th IEEE Symposium on Foundations of Computer Science","author":"Berry DW","year":"2015","unstructured":"DW Berry, AM Childs, R Kothari, Hamiltonian simulation with nearly optimal dependence on all parameters. Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (Inst Electr Electron Eng, New York), pp. 792\u2013809 (2015)."},{"key":"e_1_3_4_24_2","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/2499370.2462177","article-title":"Quipper: A scalable quantum programming language","volume":"48","author":"Green AS","year":"2013","unstructured":"AS Green, PL Lumsdaine, NJ Ross, P Selinger, B Valiron, Quipper: A scalable quantum programming language. ACM SIGPLAN Notices 48, 333\u2013342 (2013).","journal-title":"ACM SIGPLAN Notices"},{"key":"e_1_3_4_25_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1038\/s41534-018-0072-4","article-title":"Automated optimization of large-scale quantum circuits with continuous parameters","volume":"4","author":"Nam Y","year":"2018","unstructured":"Y Nam, NJ Ross, Y Su, AM Childs, D Maslov, Automated optimization of large-scale quantum circuits with continuous parameters. npj Quantum Inf 4, 23 (2018).","journal-title":"npj Quantum Inf"},{"key":"e_1_3_4_26_2","first-page":"901","article-title":"Optimal ancilla-free Clifford+T approximation of z-rotations","volume":"16","author":"Ross NJ","year":"2016","unstructured":"NJ Ross, P Selinger, Optimal ancilla-free Clifford+T approximation of z-rotations. Quantum Inf Comput 16, 901\u2013953 (2016).","journal-title":"Quantum Inf Comput"},{"key":"e_1_3_4_27_2","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1063\/1.529425","article-title":"General theory of fractal path integrals with applications to many-body theories and statistical physics","volume":"32","author":"Suzuki M","year":"1991","unstructured":"M Suzuki, General theory of fractal path integrals with applications to many-body theories and statistical physics. J Math Phys 32, 400\u2013407 (1991).","journal-title":"J Math Phys"},{"key":"e_1_3_4_28_2","doi-asserted-by":"crossref","first-page":"103017","DOI":"10.1088\/1367-2630\/14\/10\/103017","article-title":"Quantum-circuit design for efficient simulations of many-body quantum dynamics","volume":"14","author":"Raeisi S","year":"2012","unstructured":"S Raeisi, N Wiebe, BC Sanders, Quantum-circuit design for efficient simulations of many-body quantum dynamics. New J Phys 14, 103017 (2012).","journal-title":"New J Phys"},{"key":"e_1_3_4_29_2","doi-asserted-by":"crossref","first-page":"022311","DOI":"10.1103\/PhysRevA.91.022311","article-title":"Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation","volume":"91","author":"Babbush R","year":"2015","unstructured":"R Babbush, J McClean, D Wecker, A Aspuru-Guzik, N Wiebe, Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation. Phys Rev A 91, 022311 (2015).","journal-title":"Phys Rev A"},{"key":"e_1_3_4_30_2","doi-asserted-by":"crossref","first-page":"7555","DOI":"10.1073\/pnas.1619152114","article-title":"Elucidating reaction mechanisms on quantum computers","volume":"114","author":"Reiher M","year":"2017","unstructured":"M Reiher, N Wiebe, KM Svore, D Wecker, M Troyer, Elucidating reaction mechanisms on quantum computers. Proc Natl Acad Sci USA 114, 7555\u20137560 (2017).","journal-title":"Proc Natl Acad Sci USA"},{"key":"e_1_3_4_31_2","first-page":"1096","article-title":"Optimal and asymptotically optimal NCT reversible circuits by the gate types","volume":"16","author":"Maslov D","year":"2016","unstructured":"D Maslov, Optimal and asymptotically optimal NCT reversible circuits by the gate types. Quantum Inf Comput 16, 1096\u20131112 (2016).","journal-title":"Quantum Inf Comput"},{"key":"e_1_3_4_32_2","first-page":"361","article-title":"The Trotter step size required for accurate quantum simulation of quantum chemistry","volume":"15","author":"Poulin D","year":"2015","unstructured":"D Poulin, , The Trotter step size required for accurate quantum simulation of quantum chemistry. Quantum Inf Comput 15, 361\u2013384 (2015).","journal-title":"Quantum Inf Comput"},{"key":"e_1_3_4_33_2","first-page":"33","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis","author":"H\u00e4ner T","year":"2017","unstructured":"T H\u00e4ner, DS Steiger, 0.5 petabyte simulation of a 45-qubit quantum circuit. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (Assoc Comput Machinery, New York), pp. 33 (2017)."},{"key":"e_1_3_4_34_2","unstructured":"E Pednault Breaking the 49-qubit barrier in the simulation of quantum circuits. arXiv:1710.05867. (2017)."},{"key":"e_1_3_4_35_2","unstructured":"SA Kutin Shor\u2019s algorithm on a nearest-neighbor machine. arXiv:quant-ph\/0609001. (2006)."},{"key":"e_1_3_4_36_2","first-page":"333","volume-title":"Proceedings of the 30th Annual Cryptology Conference (CRYPTO)","author":"Kleinjung T","year":"2010","unstructured":"T Kleinjung, , Factorization of a 768-bit RSA modulus. Proceedings of the 30th Annual Cryptology Conference (CRYPTO) (Springer, Berlin), pp. 333\u2013350 (2010)."},{"key":"e_1_3_4_37_2","first-page":"241","volume-title":"Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information (ASIACRYPT 2017)","author":"Roetteler M","year":"2017","unstructured":"M Roetteler, M Naehrig, KM Svore, K Lauter, Quantum resource estimates for computing elliptic curve discrete logarithms. Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information (ASIACRYPT 2017) (Springer, New York), pp. 241\u2013270 (2017)."},{"key":"e_1_3_4_38_2","doi-asserted-by":"crossref","first-page":"050504","DOI":"10.1103\/PhysRevLett.97.050504","article-title":"Limitations of quantum simulation examined by simulating a pairing Hamiltonian using nuclear magnetic resonance","volume":"97","author":"Brown KR","year":"2006","unstructured":"KR Brown, RJ Clark, IL Chuang, Limitations of quantum simulation examined by simulating a pairing Hamiltonian using nuclear magnetic resonance. Phys Rev Lett 97, 050504, arXiv:quant-ph\/0601021. (2006).","journal-title":"Phys Rev Lett"},{"key":"e_1_3_4_39_2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1126\/science.1208001","article-title":"Universal digital quantum simulation with trapped ions","volume":"334","author":"Lanyon BP","year":"2011","unstructured":"BP Lanyon, , Universal digital quantum simulation with trapped ions. Science 334, 57\u201361 (2011).","journal-title":"Science"},{"key":"e_1_3_4_40_2","doi-asserted-by":"crossref","first-page":"7654","DOI":"10.1038\/ncomms8654","article-title":"Digital quantum simulation of fermionic models with a superconducting circuit","volume":"6","author":"Barends R","year":"2015","unstructured":"R Barends, , Digital quantum simulation of fermionic models with a superconducting circuit. Nat Commun 6, 7654 (2015).","journal-title":"Nat Commun"},{"key":"e_1_3_4_41_2","first-page":"031007","article-title":"Scalable quantum simulation of molecular energies","volume":"6","author":"O\u2019Malley PJJ","year":"2016","unstructured":"PJJ O\u2019Malley, , Scalable quantum simulation of molecular energies. Phys Rev X 6, 031007 (2016).","journal-title":"Phys Rev X"},{"key":"e_1_3_4_42_2","doi-asserted-by":"crossref","unstructured":"J Haah MB Hastings R Kothari GH Low Quantum algorithm for simulating real time evolution of lattice Hamiltonians. arXiv:1801.03922. (2018).","DOI":"10.1109\/FOCS.2018.00041"}],"container-title":["Proceedings of the National Academy of Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.pnas.org\/syndication\/doi\/10.1073\/pnas.1801723115","content-type":"unspecified","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/pnas.org\/doi\/pdf\/10.1073\/pnas.1801723115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,7]],"date-time":"2022-06-07T14:40:25Z","timestamp":1654612825000},"score":1,"resource":{"primary":{"URL":"https:\/\/pnas.org\/doi\/full\/10.1073\/pnas.1801723115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,6]]},"references-count":42,"journal-issue":{"issue":"38","published-print":{"date-parts":[[2018,9,18]]}},"alternative-id":["10.1073\/pnas.1801723115"],"URL":"https:\/\/doi.org\/10.1073\/pnas.1801723115","relation":{},"ISSN":["0027-8424","1091-6490"],"issn-type":[{"value":"0027-8424","type":"print"},{"value":"1091-6490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,6]]},"assertion":[{"value":"2018-09-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}