{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,23]],"date-time":"2026-03-23T17:52:54Z","timestamp":1774288374016,"version":"3.50.1"},"reference-count":78,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,3,20]],"date-time":"2025-03-20T00:00:00Z","timestamp":1742428800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DFG","award":["FOR 2724"],"award-info":[{"award-number":["FOR 2724"]}]},{"name":"DFG","award":["CRC 183"],"award-info":[{"award-number":["CRC 183"]}]},{"DOI":"10.13039\/100021130","name":"BMWK","doi-asserted-by":"crossref","award":["EniQmA"],"award-info":[{"award-number":["EniQmA"]}],"id":[{"id":"10.13039\/100021130","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Cluster of Excellence","award":["MATH+"],"award-info":[{"award-number":["MATH+"]}]},{"name":"BMBF","award":["MuniQC-Atoms"],"award-info":[{"award-number":["MuniQC-Atoms"]}]},{"name":"BMBF","award":["FermiQP"],"award-info":[{"award-number":["FermiQP"]}]},{"name":"ERC","award":["DebuQC"],"award-info":[{"award-number":["DebuQC"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Free-fermionic states, also known as matchgates or Gaussian states, are a fundamental class of quantum states due to their efficient classical simulability and their crucial role across various domains of Physics. With the advent of quantum devices, experiments now yield data from quantum states, including estimates of expectation values. We establish that deciding whether a given dataset, formed by a few Majorana correlation functions estimates, can be consistent with a free-fermionic state is an NP-complete problem. Our result also extends to datasets formed by estimates of Pauli expectation values. This is in stark contrast to the case of stabilizer states, where the analogous problem can be efficiently solved. Moreover, our results directly imply that free-fermionic states are computationally hard to properly PAC-learn, where PAC-learning of quantum states is a learning framework introduced by Aaronson. Remarkably, this is the first class of classically simulable quantum states shown to have this property.<\/jats:p>","DOI":"10.22331\/q-2025-03-20-1665","type":"journal-article","created":{"date-parts":[[2025,3,20]],"date-time":"2025-03-20T13:58:43Z","timestamp":1742479123000},"page":"1665","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["PAC-learning of free-fermionic states is NP-hard"],"prefix":"10.22331","volume":"9","author":[{"given":"Lennart","family":"Bittel","sequence":"first","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio A.","family":"Mele","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Eisert","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lorenzo","family":"Leone","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, 14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2025,3,20]]},"reference":[{"key":"0","unstructured":"Anurag Anshu and Srinivasan Arunachalam. A survey on the complexity of learning quantum states, 2023, 2305.20069."},{"key":"1","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. The learnability of quantum states. Proc. Roy. Soc. A, 463:3089\u20133114, sep 2007. 10.1098\/rspa.2007.0113.","DOI":"10.1098\/rspa.2007.0113"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. Shadow tomography of quantum states. SIAM Journal on Computing, 49(5):STOC18\u2013368\u2013STOC18\u2013394, 2020. 10.1137\/18M120275X.","DOI":"10.1137\/18M120275X"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora and Boaz Barak. Computational complexity: A modern approach. Cambridge University Press, 2009. 10.1017\/CBO9780511804090.","DOI":"10.1017\/CBO9780511804090"},{"key":"4","unstructured":"Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal algorithms for learning quantum phase states. 2023, 2208.07851."},{"key":"5","unstructured":"Scott Aaronson and Sabee Grewal. Efficient tomography of non-interacting fermion states, 2023, 2102.10458."},{"key":"6","doi-asserted-by":"publisher","unstructured":"Rodney J. Baxter. Exactly solved models in statistical mechanics. Academic Press, 1982. 10.1142\/9789814415255_0002.","DOI":"10.1142\/9789814415255_0002"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. Simulation of quantum circuits by low-rank stabilizer decompositions. Quantum, 3:181, September 2019. 10.22331\/q-2019-09-02-181.","DOI":"10.22331\/q-2019-09-02-181"},{"key":"8","doi-asserted-by":"crossref","unstructured":"Tomislav Begu\u0161i\u0107 and Garnet Kin-Lic Chan. Fast classical simulation of evidence for the utility of quantum computing before fault tolerance, 2023, 2306.16372.","DOI":"10.1126\/sciadv.adk4321"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Dolev Bluvstein, Simon J. Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong, Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuleti\u0107, and Mikhail D. Lukin. Logical quantum processor based on reconfigurable atom arrays. Nature, 626(7997):58\u201365, 2024. 10.1038\/s41586-023-06927-3.","DOI":"10.1038\/s41586-023-06927-3"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi and David Gosset. Improved classical simulation of quantum circuits dominated by Clifford gates. Phys. Rev. Lett., 116:250501, June 2016. 10.1103\/physrevlett.116.250501.","DOI":"10.1103\/physrevlett.116.250501"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Tomislav Begu\u0161i\u0107, Johnnie Gray, and Garget K.-L. Chan. Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance. Science Adv., 10(3):eadk4321, 2024. 10.1126\/sciadv.adk4321.","DOI":"10.1126\/sciadv.adk4321"},{"key":"12","unstructured":"Lennart Bittel, Antonio Anna Mele, Jens Eisert, and Lorenzo Leone. Optimal trace-distance bounds for free-fermionic states: Testing and improved tomography, 2024, 2409.17953. URL https:\/\/arxiv.org\/abs\/2409.17953."},{"key":"13","unstructured":"Sergey Bravyi. Lagrangian representation for fermionic linear optics. 2004, quant-ph\/0404180."},{"key":"14","doi-asserted-by":"publisher","unstructured":"Matthias C. Caro and Ishaun Datta. Pseudo-dimension of quantum circuits. Quantum Machine Intelligence, 2:14, nov 2020. 10.1007\/s42484-020-00027-5.","DOI":"10.1007\/s42484-020-00027-5"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. Efficient quantum state tomography. Nature Comm., 1(1):149, 2010. 10.1038\/ncomms1147.","DOI":"10.1038\/ncomms1147"},{"key":"16","doi-asserted-by":"publisher","unstructured":"J. Ignacio Cirac, David P\u00e9rez-Garc\u00eda, Norbert Schuch, and Frank Verstraete. Matrix product states and projected entangled pair states: Concepts, symmetries, theorems. Reviews of Modern Physics, 93:045003, 2021. 10.1103\/revmodphys.93.045003.","DOI":"10.1103\/revmodphys.93.045003"},{"key":"17","unstructured":"Joshua Cudby and Sergii Strelchuk. Gaussian decomposition of magic states for matchgate computations, 2023, 2307.12654."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Janek Denzler, Antonio Anna Mele, Ellen Derbyshire, Tommaso Guaita, and Jens Eisert. Learning fermionic correlations by evolving with random translationally invariant hamiltonians. Phys. Rev. Lett., 133:240604, Dec 2024. 10.1103\/PhysRevLett.133.240604.","DOI":"10.1103\/PhysRevLett.133.240604"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Pablo Echenique and J. L. Alonso. A mathematical and computational review of Hartree\u2013Fock SCF methods in quantum chemistry. Molecular Physics, 105(23\u201324):3057\u20133098, 2007. 10.1080\/00268970701757875.","DOI":"10.1080\/00268970701757875"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking. Nature Rev. Phys., 2:382\u2013390, June 2020. 10.1038\/s42254-020-0186-4.","DOI":"10.1038\/s42254-020-0186-4"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Jens Eisert. Computational difficulty of global variations in the density matrix renormalization group. Phys. Rev. Lett., 97:260501, 2006. 10.1103\/PhysRevLett.97.260501.","DOI":"10.1103\/PhysRevLett.97.260501"},{"key":"22","unstructured":"Marco Fanizza, Niklas Galke, Josep Lumbreras, Cambyse Rouz\u00e9, and Andreas Winter. Learning finitely correlated states: stability of the spectral reconstruction, 2023, 2312.07516."},{"key":"23","unstructured":"Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Efficient learning of quantum states prepared with few non-Clifford gates, 2023, 2305.13409."},{"key":"24","doi-asserted-by":"publisher","unstructured":"Marek Gluza, Martin Kliesch, Jens Eisert, and Leandro Aolita. Fidelity witnesses for fermionic quantum simulations. Phys. Rev. Lett., 120:190501, May 2018. 10.1103\/physrevlett.120.190501.","DOI":"10.1103\/physrevlett.120.190501"},{"key":"25","unstructured":"Daniel Gottesman. The Heisenberg representation of quantum computers, 1998, quant-ph\/9807006."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Gabriele Giuliani and Giovanni Vignale. Quantum theory of the electron liquid. Cambridge University Press, 2008. 10.1017\/CBO9780511619915.","DOI":"10.1017\/CBO9780511619915"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Dominik Hangleiter and Michael J. Gullans. Bell sampling from quantum circuits, 2024, 2306.00083. 10.1103\/PhysRevLett.133.020601.","DOI":"10.1103\/PhysRevLett.133.020601"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. Sample-optimal tomography of quantum states. IEEE Trans. Inf. Th., page 1\u20131, 2017. 10.1109\/tit.2017.2719044.","DOI":"10.1109\/tit.2017.2719044"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Marcel Hinsche, Marios Ioannou, Alex Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, Jean-Pierre Seifert, Jens Eisert, and Ryan Sweke. One T-gate makes distribution learning hard. Phys. Rev. Lett., 130:240602, 2023. 10.1103\/physrevlett.130.240602.","DOI":"10.1103\/physrevlett.130.240602"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Phys., 16(10):1050\u20131057, 2020. 10.1038\/s41567-020-0932-7.","DOI":"10.1038\/s41567-020-0932-7"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean. Learning shallow quantum circuits, 2024, 2401.10095. 10.1145\/3618260.364972.","DOI":"10.1145\/3618260.364972"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Richard Jozsa and Akimasa Miyake. Matchgates and classical simulation of quantum circuits. Proc. Roy. Soc. A, 464:3089\u20133106, 2008. 10.1098\/rspa.2008.0189.","DOI":"10.1098\/rspa.2008.0189"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Robert O. Jones. Density functional theory: Its origins, rise to prominence, and future. Rev. Mod. Phys., 87:897\u2013923, 2015. 10.1103\/RevModPhys.87.897.","DOI":"10.1103\/RevModPhys.87.897"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Youngseok Kim, Andrew Eddins, Sajant Anand, Ken Xuan Wei, Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, and Abhinav Kandala. Evidence for the utility of quantum computing before fault tolerance. Nature, 618(7965):500\u2013505, 2023. 10.1038\/s41586-023-06096-3.","DOI":"10.1038\/s41586-023-06096-3"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Martin Kliesch, David Gross, and Jens Eisert. Matrix-product operators and states: NP-hardness and undecidability. Phys. Rev. Lett., 113:160503, 2014. 10.1103\/PhysRevLett.113.160503.","DOI":"10.1103\/PhysRevLett.113.160503"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Alexei Kitaev. Anyons in an exactly solved model and beyond. Annals of Physics, 321(1):2\u2013111, 2006. 10.1016\/j.aop.2005.10.005.","DOI":"10.1016\/j.aop.2005.10.005"},{"key":"37","unstructured":"Emmanuel Knill. Fermionic linear optics and matchgates, 2001, quant-ph\/0108033."},{"key":"38","doi-asserted-by":"publisher","unstructured":"Martin Kliesch and Ingo Roth. Theory of quantum system certification. PRX Quantum, 2:010201, Jan 2021. 10.1103\/PRXQuantum.2.010201.","DOI":"10.1103\/PRXQuantum.2.010201"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Martin Kliesch and Ingo Roth. Theory of quantum system certification. PRX Quantum, 2:010201, 2021. 10.1103\/prxquantum.2.010201.","DOI":"10.1103\/prxquantum.2.010201"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. J. ACM, 41(1):67\u201395, January 1994. 10.1145\/174644.174647.","DOI":"10.1145\/174644.174647"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Daniel Liang. Clifford circuits can be properly PAC learned if and only if RP=NP. Quantum, 7:1036, jun 2023. 10.22331\/q-2023-06-07-1036.","DOI":"10.22331\/q-2023-06-07-1036"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Ben P. Lanyon, Christiane Maier, Tillmann Baumgratz Milan Holz\u00e4pfel, Cornelius Hempel, Petar Jurcevic, Ish Dhand, Anton S. Buyskikh, Andew J. Daley, Marcus Cramer, Martin B. Plenio, Rainer Blatt, and Christian F. Roos. Efficient tomography of a quantum many-body system. Nature Phys., 13:1158\u20131162, December 2017. 10.1038\/nphys4244.","DOI":"10.1038\/nphys4244"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. Learning t-doped stabilizer states. Quantum, 8:1361, May 2024. 10.22331\/q-2024-05-27-1361.","DOI":"10.22331\/q-2024-05-27-1361"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma. Learning efficient decoders for quasichaotic quantum scramblers. Phys. Rev. A, 109:022429, Feb 2024. 10.1103\/PhysRevA.109.022429.","DOI":"10.1103\/PhysRevA.109.022429"},{"key":"45","unstructured":"Guang Hao Low. Classical shadows of fermions with particle number symmetry. 2022, 2208.08964."},{"key":"46","unstructured":"Hai-Jun Liao, Kang Wang, Zong-Sheng Zhou, Pan Zhang, and Tao Xiang. Simulation of IBM&apos;s kicked Ising experiment with projected entangled pair operator. 2023, 2308.03082."},{"key":"47","doi-asserted-by":"publisher","unstructured":"Richard M. Martin. Electronic structure: Basic theory and practical methods. Cambridge University Press, 2004. 10.1017\/9781108555586.","DOI":"10.1017\/9781108555586"},{"key":"48","unstructured":"Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing, 2018, 1310.2035. URL https:\/\/arxiv.org\/abs\/1310.2035."},{"key":"49","doi-asserted-by":"publisher","unstructured":"Antonio Anna Mele and Yaroslav Herasymenko. Efficient learning of quantum states prepared with few fermionic non-gaussian gates. PRX Quantum, 6(1), January 2025. 10.1103\/prxquantum.6.010319.","DOI":"10.1103\/prxquantum.6.010319"},{"key":"50","unstructured":"Ashley Montanaro. Learning stabilizer states by Bell sampling, 2017, 1707.04012."},{"key":"51","doi-asserted-by":"publisher","unstructured":"Piero Naldesi, Andreas Elben, Anna Minguzzi, David Cl\u00e9ment, Peter Zoller, and Beno\u00eet Vermersch. Fermionic correlation functions from randomized measurements in programmable atomic quantum devices. Phys. Rev. Lett., 131(6), August 2023. 10.1103\/physrevlett.131.060601.","DOI":"10.1103\/physrevlett.131.060601"},{"key":"52","unstructured":"Alexander Nietner. Free fermion distributions are hard to learn. 2023, 2306.04731."},{"key":"53","unstructured":"Bryan O&apos;Gorman. Fermionic tomography and learning, 2022, 2207.14787. arXiv:2207.14787."},{"key":"54","doi-asserted-by":"publisher","unstructured":"Salvatore F. E. Oliviero, Lorenzo Leone, Alioscia Hamma, and Seth Lloyd. Measuring magic on a quantum processor. npj Quantum Information, 8:148, 2022. 10.1038\/s41534-022-00666-5.","DOI":"10.1038\/s41534-022-00666-5"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Salvatore F. E. Oliviero, Lorenzo Leone, Seth Lloyd, and Alioscia Hamma. Unscrambling quantum information with clifford decoders. Phys. Rev. Lett., 132:080402, Feb 2024. 10.1103\/PhysRevLett.132.080402.","DOI":"10.1103\/PhysRevLett.132.080402"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Matthias Ohliger, Vincent Nesme, and Jens Eisert. Efficient and feasible state tomography of quantum many-body systems. New Journal of Physics, 15:015024, 2013. 10.1088\/1367-2630\/15\/1\/015024.","DOI":"10.1088\/1367-2630\/15\/1\/015024"},{"key":"57","unstructured":"Ryan O&apos;Donnell and John Wright. Quantum spectrum testing, 2015, 1501.05028."},{"key":"58","doi-asserted-by":"publisher","unstructured":"Siddhartha Patra, Saeed S. Jahromi, Sukhbinder Singh, and Roman Orus. Efficient tensor network simulation of IBM&apos;s largest quantum processors. 2023, 2309.15642. 10.1103\/PhysRevResearch.6.013326.","DOI":"10.1103\/PhysRevResearch.6.013326"},{"key":"59","doi-asserted-by":"publisher","unstructured":"Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. J. ACM, 35(4):965\u2013984, October 1988. 10.1145\/48014.63140.","DOI":"10.1145\/48014.63140"},{"key":"60","doi-asserted-by":"publisher","unstructured":"Andrea Rocchetto, Scott Aaronson, Simone Severini, Gonzalo Carvacho, Davide Poderini, Iris Agresti, Marco Bentivegna, and Fabio Sciarrino. Experimental learning of quantum states. Science Advances, 5:eaau1946, 2019. 10.1126\/sciadv.aau1946.","DOI":"10.1126\/sciadv.aau1946"},{"key":"61","doi-asserted-by":"publisher","unstructured":"Cambyse Rouz\u00e9 and Daniel Stilck Fran\u00e7a. Learning quantum many-body systems from a few copies, 2023, 2107.03333. 10.22331\/q-2024-04-30-1319.","DOI":"10.22331\/q-2024-04-30-1319"},{"key":"62","unstructured":"Manuel S. Rudolph, Enrico Fontana, Zo\u00eb Holmes, and Lukasz Cincio. Classical surrogate simulation of quantum systems with lowesa. 2023, 2308.09109."},{"key":"63","doi-asserted-by":"publisher","unstructured":"Massimiliano Rossi, Marcus Huber, Dagmar Bru\u00df, and Chiara Macchiavello. Quantum hypergraph states. New Journal of Physics, 15:113022, November 2013. 10.1088\/1367-2630\/15\/11\/113022.","DOI":"10.1088\/1367-2630\/15\/11\/113022"},{"key":"64","unstructured":"Andrea Rocchetto. Stabiliser states are efficiently PAC-learnable. 2018, 1705.00345."},{"key":"65","doi-asserted-by":"publisher","unstructured":"J. Robert Schrieffer. Theory of superconductivity. CRC press, 2018. 10.1201\/9780429495700.","DOI":"10.1201\/9780429495700"},{"key":"66","doi-asserted-by":"publisher","unstructured":"Norbert Schuch, Ignacio Cirac, and Frank Verstraete. Computational difficulty of finding matrix product ground states. Phys. Rev. Lett., 100:250501, 2008. 10.1103\/PhysRevLett.100.250501.","DOI":"10.1103\/PhysRevLett.100.250501"},{"key":"67","doi-asserted-by":"publisher","unstructured":"Jacopo Surace and Luca Tagliacozzo. Fermionic Gaussian states: an introduction to numerical approaches. SciPost Phys. Lect. Notes, page 54, may 2022. 10.21468\/scipostphyslectnotes.54.","DOI":"10.21468\/scipostphyslectnotes.54"},{"key":"68","doi-asserted-by":"publisher","unstructured":"Norbert Schuch and Frank Verstraete. Computational complexity of interacting electrons and fundamental limitations of density functional theory. Nature Phys., 5:732, 2009. 10.1038\/nphys1370.","DOI":"10.1038\/nphys1370"},{"key":"69","doi-asserted-by":"publisher","unstructured":"Norbert Schuch, Michael M. Wolf, Frank Verstraete, and J. Ignacio Cirac. Computational complexity of projected entangled pair states. Phys. Rev. Lett., 98:140506, 2007. 10.1103\/PhysRevLett.98.140506.","DOI":"10.1103\/PhysRevLett.98.140506"},{"key":"70","doi-asserted-by":"publisher","unstructured":"Barbara M. Terhal and David P. DiVincenzo. Classical simulation of noninteracting-fermion quantum circuits. Phys. Rev. A, 65:032325, March 2002. 10.1103\/physreva.65.032325.","DOI":"10.1103\/physreva.65.032325"},{"key":"71","doi-asserted-by":"publisher","unstructured":"Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8:85\u201389, 1984. https:\/\/doi.org\/10.1016\/0166-218X(84)90081-7.","DOI":"10.1016\/0166-218X(84)90081-7"},{"key":"72","unstructured":"STOC &apos;01: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, New York, NY, USA, 2001. Association for Computing Machinery."},{"key":"73","doi-asserted-by":"publisher","unstructured":"Kianna Wan, William J. Huggins, Joonho Lee, and Ryan Babbush. Matchgate shadows for fermionic quantum simulation. 2023, 2207.13723. https:\/\/doi.org\/10.1007\/s00220-023-04844-0.","DOI":"10.1007\/s00220-023-04844-0"},{"key":"74","doi-asserted-by":"publisher","unstructured":"Bennet Windt, Alexander Jahn, Jens Eisert, and Lucas Hackl. Local optimization on pure Gaussian state manifolds. SciPost Phys., 10:066, mar 2021. 10.21468\/scipostphys.10.3.066.","DOI":"10.21468\/scipostphys.10.3.066"},{"key":"75","doi-asserted-by":"publisher","unstructured":"James Daniel Whitfield and Zolt\u00e1n Zimbor\u00e1s. On the NP-completeness of the Hartree-Fock method for translationally invariant systems. The Journal of Chemical Physics, 141:234103, 2014. 10.1063\/1.4903453.","DOI":"10.1063\/1.4903453"},{"key":"76","unstructured":"Mithuna Yoganathan. A condition under which classical simulability implies efficient state learnability. 2019, 1907.08163."},{"key":"77","doi-asserted-by":"publisher","unstructured":"Andrew Zhao, Nicholas C. Rubin, and Akimasa Miyake. Fermionic partial tomography via classical shadows. Phys. Rev. Lett., 127(11):110504, 2021. 10.1103\/physrevlett.127.110504.","DOI":"10.1103\/physrevlett.127.110504"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-03-20-1665\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,3,20]],"date-time":"2025-03-20T13:58:54Z","timestamp":1742479134000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-03-20-1665\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,20]]},"references-count":78,"URL":"https:\/\/doi.org\/10.22331\/q-2025-03-20-1665","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,20]]},"article-number":"1665"}}