Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models

Elisabeth Wybo; Martin Leib

doi:10.22331/q-2024-12-10-1554

Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models

Elisabeth Wybo and Martin Leib

IQM Quantum Computers, Georg-Brauchle-Ring 23-25, 80992 München, Germany

Published:	2024-12-10, volume 8, page 1554
Eprint:	arXiv:2311.02151v2
Doi:	https://doi.org/10.22331/q-2024-12-10-1554
Citation:	Quantum 8, 1554 (2024).

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

Abstract

The parity mapping provides a geometrically local encoding of the Quantum Approximate Optimization Algorithm (QAOA), at the expense of having a quadratic qubit overhead for all-to-all connected problems. In this work, we benchmark the parity-encoded QAOA on spin-glass models. We address open questions in the scaling of this algorithm. In particular, we show that for fixed number of parity-encoded QAOA layers, the performance or the output energy, vanishes towards zero (the value achieved by random guessing) with problem size $N$ as $N^{-1/2}$. Our results suggest that the parity-encoded QAOA does not have a promising scaling compared to the standard version of QAOA. We perform tensor-network calculations to confirm our results, and comment on the concentration of optimal QAOA parameters over problem instances.

Featured image: Vanilla versus parity-encoded QAOA. Vanilla QAOA aims to solve the all-to-all connected spin-glass problem. Parity-encoded QAOA aims to solve the geometrically local parity-encoded version of the problem. The parity encoding contains quadratically more variables.

Popular summary

Near-term quantum hardware has only limited connectivity as the qubits and interactions are typically arranged in two-dimensional lattices. In this work, we investigate a specific quantum algorithm tailored to such low-connectivity hardware to solve a paradigmatic quadratic optimization problem: finding the ground state of a Sherrington-Kirkpatrick spin glass. The algorithm we investigate is an adaptation of the standard (‘vanilla’) Quantum Approximate Optimization Algorithm (QAOA) to solve the parity-encoded version of the optimization problem. The parity encoded problem contains quadratically more variables but is entirely geometrically local, i.e. the parity-encoded problem Hamiltonian only consists of local lattice interactions.

For such dense spin-glass optimization problems, it is known that the depth of a vanilla QAOA circuit must scale linearly with the problem size in order to find fixed quality solutions, assuming that gates involving the same qubit cannot be executed in parallel. However, can we also get fixed solution quality with a potentially faster, i.e. less deep, and hardware native parity-encoded QAOA that runs on more qubits?

Our work provides for the first time insights into this question — even in the noiseless scenario we provide limitations to such an approach. Our technique is based on constructing bounds from the structure of the light cones of the observables in the Hamiltonian. First, we show that if the number of parity-encoded QAOA layers is kept constant (independent of the problem size $N$), the quality of the algorithm vanishes to the quality of trivial random guessing as $O(N^{-1/2})$. In this scenario, the interactions that generate entanglement, and therefore also the computational power of the algorithm, do asymptotically not play a role and the algorithm becomes entirely trivial. We conclude that the number of parity-encoded layers needs to grow with problem size and provide the minimal scaling exponents to avoid vanishing performance. However, our numerical experiments based on tensor networks indicate that even when the algorithm ‘sees the whole graph’, the performance still appears very limited because the ‘optimized’ QAOA angles found by reasonable optimization routines still do not generate much entanglement.

In conclusion, there is no free lunch: parity-encoded QAOA that seems more feasible on near-term hardware comes with performance limitations. The light-cone techniques proposed in our work allow to quantify such performance limitations.

► BibTeX data

@article{Wybo2024vanishing,
  doi = {10.22331/q-2024-12-10-1554},
  url = {https://doi.org/10.22331/q-2024-12-10-1554},
  title = {Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models},
  author = {Wybo, Elisabeth and Leib, Martin},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1554},
  month = dec,
  year = {2024}
}

► References

[1] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms. Nature Reviews Physics 3, 625-644 (2021), 3 (9): 625–644, aug 2020a. 10.1038/s42254-021-00348-9.
https://doi.org/10.1038/s42254-021-00348-9

[2] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik. Noisy intermediate-scale quantum (nisq) algorithms. Rev. Mod. Phys. 94, 015004 (2022), 94 (1): 015004, feb 2021. 10.1103/revmodphys.94.015004.
https://doi.org/10.1103/revmodphys.94.015004

[3] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. November 2014. 10.48550/ARXIV.1411.4028.
https://doi.org/10.48550/ARXIV.1411.4028

[4] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size. Quantum, 6: 759, July 2022. 10.22331/q-2022-07-07-759. URL https://doi.org/10.22331/q-2022-07-07-759.
https://doi.org/10.22331/q-2022-07-07-759

[5] Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. The quantum approximate optimization algorithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model. In Proceedings of the 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC '22), 7:1–7:21, (2022), October 2021. 10.4230/LIPICS.TQC.2022.7.
https://doi.org/10.4230/LIPICS.TQC.2022.7

[6] Bryan O'Gorman, William J. Huggins, Eleanor G. Rieffel, and K. Birgitta Whaley. Generalized swap networks for near-term quantum computing. May 2019. 10.48550/ARXIV.1905.05118.
https://doi.org/10.48550/ARXIV.1905.05118

[7] Phillip C. Lotshaw, Thien Nguyen, Anthony Santana, Alexander McCaskey, Rebekah Herrman, James Ostrowski, George Siopsis, and Travis S. Humble. Scaling quantum approximate optimization on near-term hardware. Scientific Reports, 12 (1), jul 2022. 10.1038/s41598-022-14767-w.
https://doi.org/10.1038/s41598-022-14767-w

[8] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Science Advances, 1 (9): e1500838, 2015. 10.1126/sciadv.1500838. URL https://www.science.org/doi/abs/10.1126/sciadv.1500838.
https://doi.org/10.1126/sciadv.1500838

[9] Wolfgang Lechner. Quantum approximate optimization with parallelizable gates. February 2018. 10.48550/ARXIV.1802.01157.
https://doi.org/10.48550/ARXIV.1802.01157

[10] Anita Weidinger, Glen Bigan Mbeng, and Wolfgang Lechner. Error mitigation for quantum approximate optimization. January 2023. 10.48550/ARXIV.2301.05042.
https://doi.org/10.48550/ARXIV.2301.05042

[11] Igor L. Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing, 38 (3): 963–981, 2008. 10.1137/050644756. URL https://doi.org/10.1137/050644756.
https://doi.org/10.1137/050644756

[12] Cupjin Huang, Fang Zhang, Michael Newman, Xiaotong Ni, Dawei Ding, Junjie Cai, Xun Gao, Tenghui Wang, Feng Wu, Gengyan Zhang, Hsiang-Sheng Ku, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, Hui-Hai Zhao, Chunqing Deng, and Jianxin Chen. Efficient parallelization of tensor network contraction for simulating quantum computation. Nature Computational Science, 1 (9): 578–587, September 2021. 10.1038/s43588-021-00119-7. URL https://doi.org/10.1038/s43588-021-00119-7.
https://doi.org/10.1038/s43588-021-00119-7

[13] Johnnie Gray and Stefanos Kourtis. Hyper-optimized tensor network contraction. Quantum 5, 410 (2021), 5: 410, mar 2020. 10.22331/q-2021-03-15-410.
https://doi.org/10.22331/q-2021-03-15-410

[14] Yong Liu, Yaojian Chen, Chu Guo, Jiawei Song, Xinmin Shi, Lin Gan, Wenzhao Wu, Wei Wu, Haohuan Fu, Xin Liu, Dexun Chen, Guangwen Yang, and Jiangang Gao. Validating quantum-supremacy experiments with exact and fast tensor network contraction. December 2022. 10.48550/ARXIV.2212.04749.
https://doi.org/10.48550/ARXIV.2212.04749

[15] Johnnie Gray and Garnet Kin-Lic Chan. Hyper-optimized compressed contraction of tensor networks with arbitrary geometry. June 2022. 10.48550/ARXIV.2206.07044.
https://doi.org/10.48550/ARXIV.2206.07044

[16] Jarrod R. McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New J. Phys. 18 (2016) 023023, 18 (2): 023023, feb 2015. 10.1088/1367-2630/18/2/023023.
https://doi.org/10.1088/1367-2630/18/2/023023

[17] Suguru Endo, Zhenyu Cai, Simon C. Benjamin, and Xiao Yuan. Hybrid quantum-classical algorithms and quantum error mitigation. J. Phys. Soc. Jpn., Vol.90, No.3, Article ID: 032001 (2021), 90 (3): 032001, mar 2020. 10.7566/jpsj.90.032001.
https://doi.org/10.7566/jpsj.90.032001

[18] M. Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J. Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications 12, 1791 (2021), 12 (1), mar 2020b. 10.1038/s41467-021-21728-w.
https://doi.org/10.1038/s41467-021-21728-w

[19] Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances. December 2018. 10.48550/ARXIV.1812.04170.
https://doi.org/10.48550/ARXIV.1812.04170

[20] Michael Streif and Martin Leib. Training the quantum approximate optimization algorithm without access to a quantum processing unit. Quantum Science and Technology, 5 (3): 034008, May 2020. 10.1088/2058-9565/ab8c2b. URL https://doi.org/10.1088/2058-9565/ab8c2b.
https://doi.org/10.1088/2058-9565/ab8c2b

[21] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte. Parameter concentrations in quantum approximate optimization. Phys. Rev. A, 104: L010401, Jul 2021. 10.1103/PhysRevA.104.L010401. URL https://doi.org/10.1103/PhysRevA.104.L010401.
https://doi.org/10.1103/PhysRevA.104.L010401

[22] Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro. Transferability of optimal qaoa parameters between random graphs. June 2021. 10.48550/ARXIV.2106.07531.
https://doi.org/10.48550/ARXIV.2106.07531

[23] Stefan H. Sack and Maksym Serbyn. Quantum annealing initialization of the quantum approximate optimization algorithm. Quantum 5, 491 (2021), 5: 491, jul 2021. 10.22331/q-2021-07-01-491.
https://doi.org/10.22331/q-2021-07-01-491

[24] Alexey Galda, Eesh Gupta, Jose Falla, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, and Ilya Safro. Similarity-based parameter transferability in the quantum approximate optimization algorithm. July 2023. 10.48550/ARXIV.2307.05420.
https://doi.org/10.48550/ARXIV.2307.05420

[25] David Sherrington and Scott Kirkpatrick. Solvable model of a spin-glass. Phys. Rev. Lett., 35: 1792–1796, Dec 1975. 10.1103/PhysRevLett.35.1792. URL https://doi.org/10.1103/PhysRevLett.35.1792.
https://doi.org/10.1103/PhysRevLett.35.1792

[26] Michel Talagrand. Mean Field Models for Spin Glasses: Volume I: Basic Examples. Springer Berlin Heidelberg, 2011a. ISBN 9783642152023. 10.1007/978-3-642-15202-3. URL http://dx.doi.org/10.1007/978-3-642-15202-3.
https://doi.org/10.1007/978-3-642-15202-3

[27] Michel Talagrand. Mean Field Models for Spin Glasses: Volume II: Advanced Replica-Symmetry and Low Temperature. Springer Berlin Heidelberg, 2011b. ISBN 9783642222535. 10.1007/978-3-642-22253-5. URL http://dx.doi.org/10.1007/978-3-642-22253-5.
https://doi.org/10.1007/978-3-642-22253-5

[28] Andrea Montanari. Optimization of the sherrington-kirkpatrick hamiltonian. December 2018. 10.48550/ARXIV.1812.10897.
https://doi.org/10.48550/ARXIV.1812.10897

[29] M. Aizenman, J. L. Lebowitz, and D. Ruelle. Some rigorous results on the Sherrington-Kirkpatrick spin glass model. Communications in Mathematical Physics, 112 (1): 3 – 20, March 1987. ISSN 1432-0916. 10.1007/bf01217677.
https://doi.org/10.1007/bf01217677

[30] Andrea Montanari and Subhabrata Sen. Semidefinite programs on sparse random graphs and their application to community detection. April 2015. 10.48550/ARXIV.1504.05910.
https://doi.org/10.48550/ARXIV.1504.05910

[31] Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein. Computational hardness of certifying bounds on constrained pca problems. February 2019. 10.48550/ARXIV.1902.07324.
https://doi.org/10.48550/ARXIV.1902.07324

[32] Aditi Misra-Spieldenner, Tim Bode, Peter K. Schuhmacher, Tobias Stollenwerk, Dmitry Bagrets, and Frank K. Wilhelm. Mean-field approximate optimization algorithm. March 2023. 10.48550/ARXIV.2303.00329.
https://doi.org/10.48550/ARXIV.2303.00329

[33] Maxime Dupont and Bhuvanesh Sundar. Quantum relax-and-round algorithm for combinatorial optimization. July 2023. 10.48550/ARXIV.2307.05821.
https://doi.org/10.48550/ARXIV.2307.05821

[34] P V Sriluckshmy, Vicente Pina-Canelles, Mario Ponce, Manuel G Algaba, Fedor Šimkovic IV, and Martin Leib. Optimal, hardware native decomposition of parameterized multi-qubit pauli gates. Quantum Science and Technology, 8 (4): 045029, sep 2023. 10.1088/2058-9565/acfa20. URL https://dx.doi.org/10.1088/2058-9565/acfa20.
https://doi.org/10.1088/2058-9565/acfa20

[35] Asier Ozaeta, Wim van Dam, and Peter L. McMahon. Expectation values from the single-layer quantum approximate optimization algorithm on ising problems. Quantum Sci. Technol. 7 045036 (2022), 7 (4): 045036, September 2020. ISSN 2058-9565. 10.1088/2058-9565/ac9013.
https://doi.org/10.1088/2058-9565/ac9013

[36] Johnnie Gray. quimb: a python library for quantum information and many-body calculations. Journal of Open Source Software, 3 (29): 819, 2018. 10.21105/joss.00819.
https://doi.org/10.21105/joss.00819

[37] Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples. May 2020a. 10.48550/ARXIV.2005.08747.
https://doi.org/10.48550/ARXIV.2005.08747

[38] Edward Farhi, David Gamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. April 2020b. 10.48550/ARXIV.2004.09002.
https://doi.org/10.48550/ARXIV.2004.09002

Cited by

[1] Anita Weidinger, Glen Bigan Mbeng, Michael Fellner, Davit Khachatryan, and Wolfgang Lechner, "Performance of parity QAOA for the signed Max-Cut problem", New Journal of Physics 28 3, 034514 (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-13 15:50:51). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2026-08-13 15:50:51).

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.