{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,12]],"date-time":"2026-11-12T11:38:07Z","timestamp":1794483487857,"version":"4.9.1"},"reference-count":40,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T00:00:00Z","timestamp":1683763200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["NSF CAREER Award No. 2238836"],"award-info":[{"award-number":["NSF CAREER Award No. 2238836"]}]},{"name":"National Science Foundation","award":["QCIS-FF: Quantum Computing & Information Science Faculty Fellow at Harvard University (NSF 2013303)"],"award-info":[{"award-number":["QCIS-FF: Quantum Computing & Information Science Faculty Fellow at Harvard University (NSF 2013303)"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>\n                    We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from \\cite{DMRF22}; (ii) injective matrix product states; (iii) output states of dense Hamiltonian evolution, i.e. states of the form\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msup>\n                        <mml:mi>e<\/mml:mi>\n                        <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                          <mml:mi>&amp;#x03B9;<\/mml:mi>\n                          <mml:msup>\n                            <mml:mi>H<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo stretchy=\"false\">(<\/mml:mo>\n                              <mml:mi>p<\/mml:mi>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mo>&amp;#x22EF;<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>e<\/mml:mi>\n                        <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                          <mml:mi>&amp;#x03B9;<\/mml:mi>\n                          <mml:msup>\n                            <mml:mi>H<\/mml:mi>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo stretchy=\"false\">(<\/mml:mo>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo stretchy=\"false\">)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                        <mml:mo stretchy=\"false\">|<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:msub>\n                        <mml:mi>&amp;#x03C8;<\/mml:mi>\n                        <mml:mn>0<\/mml:mn>\n                      <\/mml:msub>\n                      <mml:mo fence=\"false\" stretchy=\"false\">&amp;#x27E9;<\/mml:mo>\n                    <\/mml:math>\n                    for any\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:math>\n                    -qubit product state\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                        <mml:mo stretchy=\"false\">|<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:msub>\n                        <mml:mi>&amp;#x03C8;<\/mml:mi>\n                        <mml:mn>0<\/mml:mn>\n                      <\/mml:msub>\n                      <mml:mo fence=\"false\" stretchy=\"false\">&amp;#x27E9;<\/mml:mo>\n                    <\/mml:math>\n                    , where each\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msup>\n                        <mml:mi>H<\/mml:mi>\n                        <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                          <mml:mo stretchy=\"false\">(<\/mml:mo>\n                          <mml:mi>i<\/mml:mi>\n                          <mml:mo stretchy=\"false\">)<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                    <\/mml:math>\n                    can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits. Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates.An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at super-constant level\n                    <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>p<\/mml:mi>\n                      <mml:mo>=<\/mml:mo>\n                      <mml:mi>o<\/mml:mi>\n                      <mml:mo stretchy=\"false\">(<\/mml:mo>\n                      <mml:mi>log<\/mml:mi>\n                      <mml:mo>&amp;#x2061;<\/mml:mo>\n                      <mml:mi>log<\/mml:mi>\n                      <mml:mo>&amp;#x2061;<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo stretchy=\"false\">)<\/mml:mo>\n                    <\/mml:math>\n                    , assuming a strengthened version of the so-called overlap gap property. This gives the first limitations on the QAOA on dense instances at super-constant level, improving upon the recent result [BGMZ22].\n                  <\/jats:p>","DOI":"10.22331\/q-2023-05-11-999","type":"journal-article","created":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T06:43:41Z","timestamp":1683787421000},"page":"999","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":12,"title":["Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations"],"prefix":"10.22331","volume":"7","author":[{"given":"Anurag","family":"Anshu","sequence":"first","affiliation":[{"name":"School of Engineering and Applied Sciences, Harvard University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tony","family":"Metger","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, ETH Zurich"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2023,5,11]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Anurag Anshu, Itai Arad, and David Gosset. An area law for 2d frustration-free spin systems. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 12\u201318, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145\/3519935.3519962.","DOI":"10.1145\/3519935.3519962"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Anurag Anshu and Nikolas P. Breuckmann. A construction of combinatorial NLTS. Journal of Mathematical Physics, 63(12), 12 2022. doi:10.1063\/5.0113731.","DOI":"10.1063\/5.0113731"},{"key":"2","unstructured":"Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. NLTS hamiltonians from good quantum codes. arXiv preprint arXiv:2206.13228, 2022. URL: https:\/\/arxiv.org\/abs\/2206.13228."},{"key":"3","unstructured":"Nilin Abrahamsen. Short proof of a spectral chernoff bound for local hamiltonians. arXiv preprint arXiv:2009.04993, 2020. URL: https:\/\/arxiv.org\/abs\/2009.04993."},{"key":"4","unstructured":"\u00c1lvaro M Alhambra. Quantum many-body systems in thermal equilibrium. arXiv preprint arXiv:2204.08349, 2022. URL: https:\/\/arxiv.org\/abs\/2204.08349."},{"key":"5","doi-asserted-by":"publisher","unstructured":"Anurag Anshu and Chinmay Nirkhe. Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1\u20136:22, Dagstuhl, Germany, 2022. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik. doi:10.4230\/LIPIcs.ITCS.2022.6.","DOI":"10.4230\/LIPIcs.ITCS.2022.6"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Anurag Anshu. Concentration bounds for quantum states with finite correlation length on quantum spin lattice systems. New Journal of Physics, 18(8):083011, aug 2016. doi:10.1088\/1367-2630\/18\/8\/083011.","DOI":"10.1088\/1367-2630\/18\/8\/083011"},{"key":"7","unstructured":"Fernando GSL Brandao and Marcus Cramer. Equivalence of statistical mechanical ensembles for non-critical quantum systems. arXiv preprint arXiv:1502.03263, 2015. URL: https:\/\/arxiv.org\/abs\/1502.03263."},{"key":"8","doi-asserted-by":"publisher","unstructured":"H. Buhrman, R. Cleve, R. De Wolf, and C. Zalka. Bounds for small-error and zero-error quantum algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 358\u2013368, 1999. doi:10.1109\/SFFCS.1999.814607.","DOI":"10.1109\/SFFCS.1999.814607"},{"key":"9","unstructured":"FGSL Brandao, Marcus Cramer, and Madalin Guta. A berry\u2013esseen theorem for quantum lattice systems and the equivalence of statistical mechanical ensembles. QIP2015 Talk, 2015. URL: http:\/\/www.quantum-lab.org\/qip2015\/talks\/125-Brandao.pdf."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Joao Basso, David Gamarnik, Song Mei, and Leo Zhou. Performance and limitations of the qaoa at constant levels on large sparse hypergraphs and spin glass models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022. doi:10.1109\/FOCS54457.2022.00039.","DOI":"10.1109\/FOCS54457.2022.00039"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett., 125:260505, Dec. doi:10.1103\/PhysRevLett.125.260505.","DOI":"10.1103\/PhysRevLett.125.260505"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman. Suboptimality of local algorithms for a class of max-cut problems. The Annals of Probability, 47(3):1587 \u2013 1618, 2019. doi:10.1214\/18-AOP1291.","DOI":"10.1214\/18-AOP1291"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, and Jonathan Shi. Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1\u201341:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl \u2013 Leibniz-Zentrum fur Informatik. doi:10.4230\/LIPIcs.ICALP.2022.41.","DOI":"10.4230\/LIPIcs.ICALP.2022.41"},{"key":"14","doi-asserted-by":"publisher","unstructured":"J Ignacio Cirac, David Perez-Garcia, Norbert Schuch, and Frank Verstraete. Matrix product states and projected entangled pair states: Concepts, symmetries, theorems. Reviews of Modern Physics, 93(4):045003, 2021. doi:10.1103\/RevModPhys.93.045003.","DOI":"10.1103\/RevModPhys.93.045003"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Giacomo De Palma, Milad Marvian, Cambyse Rouz\u00e9, and Daniel Stilck Franca. Limitations of variational quantum algorithms: A quantum optimal transport approach. PRX Quantum, 4:010309, Jan 2023. doi:10.1103\/PRXQuantum.4.010309.","DOI":"10.1103\/PRXQuantum.4.010309"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Giacomo De Palma and Cambyse Rouz\u00e9. Quantum concentration inequalities. Annales Henri Poincar\u00e9, Apr 2022. doi:10.1007\/s00023-022-01181-1.","DOI":"10.1007\/s00023-022-01181-1"},{"key":"17","doi-asserted-by":"publisher","unstructured":"L. Eldar and A. W. Harrow. Local hamiltonians whose ground states are hard to approximate. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 427\u2013438, 2017. doi:10.1109\/FOCS.2017.46.","DOI":"10.1109\/FOCS.2017.46"},{"key":"18","unstructured":"Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. URL: https:\/\/arxiv.org\/abs\/1411.4028."},{"key":"19","unstructured":"Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv preprint arXiv:2004.09002, 2020. URL: https:\/\/arxiv.org\/abs\/2004.09002."},{"key":"20","doi-asserted-by":"publisher","unstructured":"David Gamarnik. The overlap gap property: A topological barrier to optimizing over random structures. Proceedings of the National Academy of Sciences, 118(41):e2108492118, 2021. doi:10.1073\/pnas.2108492118.","DOI":"10.1073\/pnas.2108492118"},{"key":"21","unstructured":"Ronald L Graham, Martin Gr\u00f6tschel, and L\u00e1szl\u00f3 Lov\u00e1sz. Handbook of Combinatorics, volume 1. Elsevier, 1995."},{"key":"22","doi-asserted-by":"crossref","unstructured":"David Gamarnik and Aukosh Jagannath. The overlap gap property and approximate message passing algorithms for $p$-spin models. The Annals of Probability, 49(1):180\u2013205, 2021. URL: https:\/\/hdl.handle.net\/1721.1\/145311.","DOI":"10.1214\/20-AOP1448"},{"key":"23","doi-asserted-by":"publisher","unstructured":"David Gamarnik, Aukosh Jagannath, and Alexander S Wein. Low-degree hardness of random optimization problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 131\u2013140. IEEE, 2020. doi:10.1109\/FOCS46700.2020.00021.","DOI":"10.1109\/FOCS46700.2020.00021"},{"key":"24","doi-asserted-by":"crossref","unstructured":"David Gamarnik and Quan Li. Finding a large submatrix of a gaussian random matrix. The Annals of Statistics, 46(6A):2511\u20132561, 2018. URL: http:\/\/hdl.handle.net\/1721.1\/120593.","DOI":"10.1214\/17-AOS1628"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Francesco Guerra and Fabio Lucio Toninelli. The thermodynamic limit in mean field spin glass models. Communications in Mathematical Physics, 230(1):71\u201379, 2002. doi:10.1007\/s00220-002-0699-y.","DOI":"10.1007\/s00220-002-0699-y"},{"key":"26","doi-asserted-by":"publisher","unstructured":"D. Goderis and P. Vets. Central limit theorem for mixing quantum systems and the CCR-algebra of fluctuations. Communications in Mathematical Physics, 122:249\u2013265, 1989. doi:10.1007\/BF01257415.","DOI":"10.1007\/BF01257415"},{"key":"27","doi-asserted-by":"publisher","unstructured":"M. B. Hastings. Lieb-schultz-mattis in higher dimensions. Phys. Rev. B, 69:104431, Mar 2004. doi:10.1103\/PhysRevB.69.104431.","DOI":"10.1103\/PhysRevB.69.104431"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Michael Hartmann, G\u00fcnter Mahler, and Ortwin Hess. Existence of Temperature on the Nanoscale. Phys. Rev. Lett., 93:080402, Aug 2004. doi:10.1103\/PhysRevLett.93.080402.","DOI":"10.1103\/PhysRevLett.93.080402"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Tomotaka Kuwahara, Itai Arad, Luigi Amico, and Vlatko Vedral. Local reversibility and entanglement structure of many-body ground states. Quantum Science and Technology, 2(1):015005, 2017. doi:10.1088\/2058-9565\/aa523d.","DOI":"10.1088\/2058-9565\/aa523d"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Jeff Kahn, Nathan Linial, and Alex Samorodnitsky. Inclusion-exclusion: Exact and approximate. Combinatorica, 16(4):465\u2013477, Dec 1996. doi:10.1007\/BF01271266.","DOI":"10.1007\/BF01271266"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Tomotaka Kuwahara and Keiji Saito. Eigenstate thermalization from the clustering property of correlation. Phys. Rev. Lett., 124:200604, May 2020. doi:10.1103\/PhysRevLett.124.200604.","DOI":"10.1103\/PhysRevLett.124.200604"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Tomotaka Kuwahara and Keiji Saito. Gaussian concentration bound and ensemble equivalence in generic quantum many-body systems including long-range interactions. Annals of Physics, 421:168278, 2020. doi:10.1016\/j.aop.2020.168278.","DOI":"10.1016\/j.aop.2020.168278"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Tomotaka Kuwahara. Connecting the probability distributions of different operators and generalization of the chernoff-hoeffding inequality. Journal of Statistical Mechanics: Theory and Experiment, 2016(11):113103, nov 2016. doi:10.1088\/1742-5468\/2016\/11\/113103.","DOI":"10.1088\/1742-5468\/2016\/11\/113103"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Elliott Lieb, Theodore Schultz, and Daniel Mattis. Two soluble models of an antiferromagnetic chain. Annals of Physics, 16(3):407\u2013466, 1961. doi:10.1016\/0003-4916(61)90115-4.","DOI":"10.1016\/0003-4916(61)90115-4"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Anthony Leverrier and Gilles Z\u00e9mor. Quantum tanner codes. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022. doi:10.1109\/FOCS54457.2022.00117.","DOI":"10.1109\/FOCS54457.2022.00117"},{"key":"36","doi-asserted-by":"crossref","unstructured":"D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac. Matrix product state representations. Quantum Info. Comput., 7(5):401\u2013430, jul 2007. URL: https:\/\/dl.acm.org\/doi\/10.5555\/2011832.2011833.","DOI":"10.26421\/QIC7.5-6-1"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Pavel Panteleev and Gleb Kalachev. Asymptotically good quantum and locally testable classical ldpc codes. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 375\u2013388, 2022. doi:10.1145\/3519935.3520017.","DOI":"10.1145\/3519935.3520017"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Sushant Sachdeva and Nisheeth K. Vishnoi. Faster algorithms via approximation theory. Foundations and Trends\u00ae in Theoretical Computer Science, 9(2):125\u2013210, 2014. doi:10.1561\/0400000065.","DOI":"10.1561\/0400000065"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Hal Tasaki. On the local equivalence between the canonical and the microcanonical ensembles for quantum spin systems. Journal of Statistical Physics, 172(4):905\u2013926, Aug 2018. doi:10.1007\/s10955-018-2077-y.","DOI":"10.1007\/s10955-018-2077-y"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-05-11-999\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,11,12]],"date-time":"2026-11-12T11:06:38Z","timestamp":1794481598000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-05-11-999\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,11]]},"references-count":40,"URL":"https:\/\/doi.org\/10.22331\/q-2023-05-11-999","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,11]]},"article-number":"999"}}