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.
Abstract
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_0rangle$ for any $n$-qubit product state $|psi_0rangle$, 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].
[embedded content]
► 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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/2206.13228.
arXiv:2206.13228
[4] 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.
arXiv:2009.04993
[5] Álvaro M Alhambra. Quantum many-body systems in thermal equilibrium. arXiv preprint arXiv:2204.08349, 2022. URL: https://arxiv.org/abs/2204.08349.
arXiv: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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/1502.03263.
arXiv: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.
https://doi.org/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://www.quantum-lab.org/qip2015/talks/125-Brandao.pdf.
http://www.quantum-lab.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://arxiv.org/abs/1411.4028.
arXiv: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://arxiv.org/abs/2004.09002.
arXiv: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.
https://doi.org/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://hdl.handle.net/1721.1/145311.
https://hdl.handle.net/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.
https://doi.org/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://hdl.handle.net/1721.1/120593.
http://hdl.handle.net/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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://dl.acm.org/doi/10.5555/2011832.2011833.
https://dl.acm.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1007/s10955-018-2077-y
Cited by
[1] 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).
[2] Ojas Parekh, “Synergies Between Operations Research and Quantum Information Science”, arXiv:2301.05554, (2023).
[3] Dominik S. Wild and Álvaro M. Alhambra, “Classical simulation of short-time quantum dynamics”, arXiv:2210.11490, (2022).
[4] Lennart Bittel, Sevag Gharibian, and Martin Kliesch, “Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate”, arXiv:2211.12519, (2022).
The above citations are from SAO/NASA ADS (last updated successfully 2023-05-11 10:33:33). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2023-05-11 10:33:31: Could not fetch cited-by data for 10.22331/q-2023-05-11-999 from Crossref. This is normal if the DOI was registered recently.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoAiStream. Web3 Data Intelligence. Knowledge Amplified. Access Here.
- Minting the Future w Adryenn Ashley. Access Here.
- Buy and Sell Shares in PRE-IPO Companies with PREIPO®. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-05-11-999/
