CoChat
Sign Up
Cited by 71Quantum Computing Algorithms and ArchitectureAdvanced Chemical Physics StudiesComplexity and Algorithms in Graphs

Computational complexity in electronic structure

Open access
Whitfield, James Daniel, Love, Peter John, Aspuru-Guzik, Alán·2013·Phys. Chem. Chem. Phys.
DOI 10.1039/c2cp42695a
Open this paper in CoChat — free accountOpen PDF

Abstract

In quantum chemistry, the price paid by all known efficient model chemistries is either the truncation of the Hilbert space or uncontrolled approximations. Theoretical computer science suggests that these restrictions are not mere shortcomings of the algorithm designers and programmers but could stem from the inherent difficulty of simulating quantum systems. Extensions of computer science and information processing exploiting quantum mechanics has led to new ways of understanding the ultimate limitations of computational power. Interestingly, this perspective helps us understand widely used model chemistries in a new light. In this article, the fundamentals of computational complexity will be reviewed and motivated from the vantage point of chemistry. Then recent results from the computational complexity literature regarding common model chemistries including Hartree–Fock and density functional theory are discussed.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1039/c2cp42695a

Cites

83 of 83 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The breakdown of truncated coupled cluster can be generalized to any level of truncation of the excitation operator when strong correlation is exhibited by the Hamiltonian.

    “This behavior can be generalized to any level of truncation of the excitation operator when strong correlation is exhibited by the hamiltonian 81 .”

    From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [81]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

2 of the 85 references couldn’t be matched to a known paper.

Research works printed but not linked: 58

  1. 5 A. Aspuru-Guzik, A. D. Dutoi, P. Love and M. Head-Gordon, Science , 2005, 309 , 1704.
  2. 6 K. L. Brown, W. J. Munro and V. M. Kendon, Entropy , 2010, 12 , 2268.
  3. 7 I. Kassal ∗ , J. Whitfield ∗ , A. Perdomo-Ortiz, M.-H. Yung and A. AspuruGuzik, Ann. Rev. Phys. Chem. , 2011, 62 , 185-207.
  4. 8 J. D. Whitfield, J. D. Biamonte and A. Aspuru-Guzik, J. Mol. Phys. , 2011, 109 , 735.
  5. 9 M.-H. Yung, J. D. Whitfield, S. Boixo, D. G. Tempel and A. AspuruGuzik, Adv. Chem. Phys. , 2012, In press ,.
  6. 10 R. Feynman, Int. J. Theoretical Phys. , 1982, 21 , 467.
  7. 11 L.-A. Wu, M. S. Byrd and D. A. Lidar, Phys. Rev. Lett. , 2002, 89 , 057904.
  8. 12 I. Kassal, S. P. Jordan, P. J. Love, M. Mohseni and A. Aspuru-Guzik, Proc. Natl. Acad. Sci. , 2008, 105 , 18681.
  9. 13 L. Veis and J. Pittner, J. Chem. Phys. , 2010, 133 , 194106.
  10. 14 J. D. Biamonte, V. Bergholm, J. D. Whitfield, J. Fitzsimons and A. Aspuru-Guzik, AIP Advances , 2011, 1 , 022126.
  11. 15 D. Lu, B. Xu, N. Xu, Z. Li, H. Chen, X. Peng, R. Xu and J. Du, Phys. Chem. Chem. Phys. , 2012, 14 , 9411-9420.
  12. 16 A. Aspuru-Guzik and P. Walther, Nature Phys. , 2012, 8 , 285-291.
  13. 18 P. J. Love, Adv. Chem. Phys. , 2012, In press ,.
  14. 19 T. J. Osborne, Rep. Prog. Phys. , 2012, 75 , 022001.
  15. 20 V. A. Rassolov and S. Garashchuk, Chem. Phys. Lett. , 2008, 464 , 262264.
  16. 21 N. Schuch, M. M. Wolf, F. Verstraete and J. I. Cirac, Phys. Rev. Lett. , 2007, 98 , 140506.
  17. 22 N. Schuch, I. Cirac and F. Verstraete, Phys. Rev. Lett. , 2008, 100 , 250501.
  18. 23 F. Verstraete, V. Murg and J. I. Cirac, Advances in Physics , 2008, 57 , 143-224.
  19. 24 G. K.-L. Chan, J. J. Dorando, D. Ghosh, J. Hachmann, E. Neuscamman, H. Wang and T. Yanai, Prog. Theor. Chem. and Phys. , 2008, 18 , 49.
  20. 25 G. K.-L. Chan and S. Sharma, Ann. Rev. Phys. Chem. , 2011, 62 , 465.
  21. 29 S. Ben-David, B. Chor, O. Goldreich and M. Luby, Journal of Computer and System Sciences , 1992, 44 , 193-219.
  22. 30 A. Bogdanov and L. Trevisan, Found. Trends Theor. Comput. Sci. , 2006, 2 , 1-106.
  23. 32 A. Turing, Proc. London Math. Soc. , 1937, 1 , 230-265.
  24. 33 D. Deutsch, Proc. R. Soc. A , 1985, 400 , 97-117.
  25. 34 E. Bernstein and U. Vazirani, Proc. STOC' 93 , 1993, 11.
  26. 36 W. M. C. Foulkes, L. Mitas, R. J. Needs and G. Rajagopal, Rev. Mod. Phys. , 2001, 73 , 33-83.
  27. 37 W. A. Lester Jr., L. Mitas and B. Hammond, Chem. Phys. Lett. , 2009, 478 , 1-10.
  28. 39 F. Barahona, J. Phys. A: Math. Gen. , 1982, 15 , 3241.
  29. 40 S. Istrail, Proc. 32nd ACM Symp. on Theory of Comp. (STOC '00) , 2000, 87.
  30. 42 L. Onsager, Phys. Rev. , 1944, 65 , 117-149.
  31. 44 R. Oliveira and B. Terhal, Quant. Inf. Comp. , 2008, 8 , 0900.
  32. 45 J. D. Biamonte and P. J. Love, Phys. Rev. A , 2008, 78 , 012352.
  33. 46 C. L. Cleveland and R. Medina A., Am. J. Phys. , 1976, 44 , 44.
  34. 48 Y.-K. Liu, M. Christandl and F. Verstraete, Phys. Rev. Lett. , 2007, 98 , 110503.
  35. 49 N. Schuch and F. Verstraete, Nature Phys. , 2009, 5 , 732. Also see arXiv:0712.0483. · arXiv
  36. 50 T. Wei, M. Mosca and A. Nayak, Phys. Rev. Lett. , 2010, 104 , 040501.
  37. 51 P. Jordan and E. Wigner, Z. Phys. A. , 1928, 47 , 631.
  38. 52 E. Lieb, T. Schultz and D. Mattis, Ann. Phys. , 1961, 16 , 407-466.
  39. 54 S. B. Bravyi and A. Y. Kitaev, Ann. Phys. , 2002, 298 , 210-226.
  40. 55 F. Verstraete and J. I. Cirac, J. Stat. Mech. , 2005, 2005 , P09012.
  41. 56 C. D. Batista and G. Ortiz, Phys. Rev. Lett. , 2001, 86 , 1092-1085.
  42. 57 G. Ortiz, J. Gubernatis, E. Knill and R. Laflamme, Phys. Rev. A , 2001, 64 , 022319.
  43. 58 R. Somma, G. Ortiz, J. E. Gubernatis, E. Knill and R. Laflamme, Phys. Rev. A , 2002, 65 , 042323.
  44. 59 S. Lloyd, Science , 1996, 273 , 1073-8.
  45. 60 D. W. Berry, G. Ahokas, R. Cleve and B. C. Sanders, Commun. Math. Phys. , 2007, 270 , 359-371.
  46. 61 A. Kitaev, arXiv:quant-ph/9511026 , 1995. · arXiv
  47. 63 C. A. Coulson, Rev. Mod. Phys. , 1960, 32 , 170.
  48. 66 D. A. Mazziotti, Phys. Rev. Lett. , 2012, 108 , 263002.
  49. 67 D. A. Mazziotti, Phys. Rev. A , 2012, 85 , 062507.
  50. 70 D. Aharonov and O. Regev, Proc. Annual Symp. on Found. of Comp. Sci., 2003, p. 210.
  51. 71 A. Harrow and A. Montanaro, Proc. of the 2010 IEEE 51st Annual Symp. on Found. of Comp. Sci. (FOCS '10) , 2010, 633-642.
  52. 73 W. Kohn, Rev. Mod. Phys. , 1999, 71 , 1253-1266.
  53. 74 P. Hohenberg and W. Kohn, Phys Rev , 1964, 136 , B864.
  54. 75 B. Brown, S. T. Flammia and N. Schuch, Phys. Rev. Lett. , 2011, 107 , 040501.
  55. 76 M. Troyer and U.-J. Wiese, Phys. Rev. Lett. , 2005, 94 , 170201.
  56. 77 D. Tempel and A. Aspuru-Guzik, Sci. Reports , 2012, 2 , 391.
  57. 78 S. Arora and S. Safra, J. ACM , 1998, 45 , 70-122.
  58. 79 S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, J. ACM , 1998, 45 , 501-555.

Cited by

Sorted by citations

Related

Authors
Whitfield, J. D., Love, P. J., & Aspuru-Guzik, A.
Affiliations
  • Vienna Center for Quantum Science and Technology (AT)
  • Haverford College (US)
Corresponding author
Whitfield, James Daniel
ORCID
Venue
Phys. Chem. Chem. Phys.
Publisher
Royal Society of Chemistry (RSC)
Published
2013
Volume
15
Issue
2
Pages
397-411
ISSN
  • 1463-9076 (ISSN-L)
  • 1463-9084
DOI
10.1039/c2cp42695a
OpenAlex
W3098470619
Cited by
71
References
85
Citations by year
2026: 3 · 2025: 10 · 2024: 5 · 2023: 6 · 2022: 6 · 2021: 6 · 2020: 6 · 2019: 4 · 2018: 4 · 2017: 7 · 2016: 3 · 2015: 1 · 2014: 7 · 2013: 1 · 2012: 1
FWCI
3.15
Type
journal article
Language
en
Open access
Locations
  • Physical Chemistry Chemical Physics (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Digital Access to Scholarship at Harvard (DASH) (Harvard University) (submittedVersion, cc-by)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Advanced Chemical Physics Studies
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
computational complexity, electronic structure, quantum chemistry, Hartree-Fock, density functional theory, Hilbert space truncation, quantum simulation, limits of computation, quantum computing

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review