Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations

Anurag Anshu1 and Tony Metger2

1School of Engineering and Applied Sciences, Harvard University
2Institute for Theoretical Physics, ETH Zurich

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from [16]; (ii) injective matrix product states; (iii) output states of dense Hamiltonian evolution, i.e. states of the form $e^{\iota H^{(p)}} \cdots e^{\iota H^{(1)}} |\psi_0\rangle$ for any $n$-qubit product state $|\psi_0\rangle$, where each $H^{(i)}$ 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 $p = o(\log \log 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].

► BibTeX data

► References

[1] 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–18, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/​3519935.3519962.

[2] Anurag Anshu and Nikolas P. Breuckmann. A construction of combinatorial NLTS. Journal of Mathematical Physics, 63(12), 12 2022. doi:10.1063/​5.0113731.

[3] Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. NLTS hamiltonians from good quantum codes. arXiv preprint arXiv:2206.13228, 2022. URL: https:/​/​​abs/​2206.13228.

[4] Nilin Abrahamsen. Short proof of a spectral chernoff bound for local hamiltonians. arXiv preprint arXiv:2009.04993, 2020. URL: https:/​/​​abs/​2009.04993.

[5] Álvaro M Alhambra. Quantum many-body systems in thermal equilibrium. arXiv preprint arXiv:2204.08349, 2022. URL: https:/​/​​abs/​2204.08349.

[6] 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–6:22, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/​LIPIcs.ITCS.2022.6.

[7] 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.

[8] Fernando GSL Brandao and Marcus Cramer. Equivalence of statistical mechanical ensembles for non-critical quantum systems. arXiv preprint arXiv:1502.03263, 2015. URL: https:/​/​​abs/​1502.03263.

[9] 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–368, 1999. doi:10.1109/​SFFCS.1999.814607.

[10] FGSL Brandao, Marcus Cramer, and Madalin Guta. A berry–esseen theorem for quantum lattice systems and the equivalence of statistical mechanical ensembles. QIP2015 Talk, 2015. URL: http:/​/​​qip2015/​talks/​125-Brandao.pdf.

[11] 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.

[12] 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.

[13] 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 – 1618, 2019. doi:10.1214/​18-AOP1291.

[14] 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–41:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum fur Informatik. doi:10.4230/​LIPIcs.ICALP.2022.41.

[15] 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.

[16] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, 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.

[17] Giacomo De Palma and Cambyse Rouzé. Quantum concentration inequalities. Annales Henri Poincaré, Apr 2022. doi:10.1007/​s00023-022-01181-1.

[18] 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–438, 2017. doi:10.1109/​FOCS.2017.46.

[19] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014. URL: https:/​/​​abs/​1411.4028.

[20] 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:/​/​​abs/​2004.09002.

[21] 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.

[22] Ronald L Graham, Martin Grötschel, and László Lovász. Handbook of Combinatorics, volume 1. Elsevier, 1995.

[23] 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–205, 2021. URL: https:/​/​​1721.1/​145311.

[24] 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–140. IEEE, 2020. doi:10.1109/​FOCS46700.2020.00021.

[25] David Gamarnik and Quan Li. Finding a large submatrix of a gaussian random matrix. The Annals of Statistics, 46(6A):2511–2561, 2018. URL: http:/​/​​1721.1/​120593.

[26] Francesco Guerra and Fabio Lucio Toninelli. The thermodynamic limit in mean field spin glass models. Communications in Mathematical Physics, 230(1):71–79, 2002. doi:10.1007/​s00220-002-0699-y.

[27] D. Goderis and P. Vets. Central limit theorem for mixing quantum systems and the CCR-algebra of fluctuations. Communications in Mathematical Physics, 122:249–265, 1989. doi:10.1007/​BF01257415.

[28] M. B. Hastings. Lieb-schultz-mattis in higher dimensions. Phys. Rev. B, 69:104431, Mar 2004. doi:10.1103/​PhysRevB.69.104431.

[29] Michael Hartmann, Günter Mahler, and Ortwin Hess. Existence of Temperature on the Nanoscale. Phys. Rev. Lett., 93:080402, Aug 2004. doi:10.1103/​PhysRevLett.93.080402.

[30] 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.

[31] Jeff Kahn, Nathan Linial, and Alex Samorodnitsky. Inclusion-exclusion: Exact and approximate. Combinatorica, 16(4):465–477, Dec 1996. doi:10.1007/​BF01271266.

[32] 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.

[33] 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.

[34] 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.

[35] Elliott Lieb, Theodore Schultz, and Daniel Mattis. Two soluble models of an antiferromagnetic chain. Annals of Physics, 16(3):407–466, 1961. doi:10.1016/​0003-4916(61)90115-4.

[36] Anthony Leverrier and Gilles Zémor. Quantum tanner codes. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022. doi:10.1109/​FOCS54457.2022.00117.

[37] D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac. Matrix product state representations. Quantum Info. Comput., 7(5):401–430, jul 2007. URL: https:/​/​​doi/​10.5555/​2011832.2011833.

[38] 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–388, 2022. doi:10.1145/​3519935.3520017.

[39] Sushant Sachdeva and Nisheeth K. Vishnoi. Faster algorithms via approximation theory. Foundations and Trends® in Theoretical Computer Science, 9(2):125–210, 2014. doi:10.1561/​0400000065.

[40] Hal Tasaki. On the local equivalence between the canonical and the microcanonical ensembles for quantum spin systems. Journal of Statistical Physics, 172(4):905–926, Aug 2018. doi:10.1007/​s10955-018-2077-y.

Cited by

[1] Huy Phuc Nguyen Ha, Viet Hung Nguyen, and Anh Son Ta, Lecture Notes in Computer Science 14753 , 246 (2024) ISBN:978-3-031-62911-2.

[2] Sergey Bravyi, David Gosset, and Yinchen Liu, Proceedings of the 56th Annual ACM Symposium on Theory of Computing 561 (2024) ISBN:9798400703836.

[3] Giacomo De Palma, Milad Marvian, Cambyse Rouzé, and Daniel Stilck França, "Limitations of Variational Quantum Algorithms: A Quantum Optimal Transport Approach", PRX Quantum 4 1, 010309 (2023).

[4] Dominik S. Wild and Álvaro M. Alhambra, "Classical Simulation of Short-Time Quantum Dynamics", PRX Quantum 4 2, 020340 (2023).

[5] Antares Chen, Neng Huang, and Kunal Marwaha, "Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs", arXiv:2310.01563, (2023).

[6] Ojas Parekh, "Synergies Between Operations Research and Quantum Information Science", arXiv:2301.05554, (2023).

[7] Lennart Bittel, Sevag Gharibian, and Martin Kliesch, "Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate", arXiv:2211.12519, (2022).

[8] Sergey Bravyi, David Gosset, and Yinchen Liu, "Classical simulation of peaked shallow quantum circuits", arXiv:2309.08405, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-06-21 20:09:57) and SAO/NASA ADS (last updated successfully 2024-06-21 20:09:58). The list may be incomplete as not all publishers provide suitable and complete citation data.