- Access by Xinjiang University
Entanglement-entropy-based scaling relation in QAOA tensor network simulations for the MAXCUT problem
Phys. Rev. A 114, 012610 – Published 9 July, 2026
DOI: https://doi.org/10.1103/vv11-n11b
Abstract
With the rapid development of quantum computers in recent years, the importance of performance evaluation in quantum algorithms has been increasing. One method that has gained attention for performing this evaluation on classical computers is tensor networks. Tensor networks not only reduce the computational cost required for simulations by using approximations but are also deeply connected to entanglement. Entanglement is one of the most important elements for the quantum advantages of quantum algorithms, but the direct relationship between quantum advantages and entanglement remains largely unexplored. Tensor networks are promising as a means to address this question. In this study, we focus on the entanglement in the quantum approximate optimization algorithm (QAOA). This study aims to investigate entanglement in QAOA by examining the relationship between the approximation rates of tensor networks and the performance of QAOA. Specifically, we actually perform tensor network simulations of QAOA on a classical computer and extend the study of the scaling relations presented in previous research. We have discovered that scaling relations hold even when entanglement entropy is used as the vertical axis in QAOA solutions of the MAXCUT problem. Furthermore, by analyzing the results of the numerical calculations, we propose a function for the scaling relation. Additionally, we discovered interesting relationships regarding the behavior of entanglement in QAOA during our analysis. This research is expected to provide insights into the theoretical foundation of the scaling relations presented in previous studies.
Physics Subject Headings (PhySH)
Article Text
References (24)
- R. P. Feynman, Simulating physics with computers, Feynman and Computation (CRC Press, Boca Raton, 2018), pp. 133–153.
- S. K. Sood, and Pooja, Quantum computing review: A decade of research, IEEE Trans. Eng. Manage. 71, 6662 (2023).
- M. A. Shafique, A. Munir, and I. Latif, Quantum computing: Circuits, algorithms, and applications, IEEE Access 12, 22296 (2024).
- A. W. Harrowand and A. Montanaro, Quantum computational supremacy, Nature (London) 549, 203 (2017).
- IBM Quantum, Compute resources, 2025, https://quantum.ibm.com/services/resources.
- D. Gottesman, The Heisenberg representation of quantum computers, arXiv:quant-ph/9807006.
- J. Roffe, Quantum error correction: An introductory guide, Contemp. Phys. 60, 226 (2019).
- , Quantum error correction below the surface code threshold, Nature (London) 638, 920 (2025).
- J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
- L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (ACM, New York, 1996), p. 212.
- M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th ed. (Cambridge University Press, Cambridge, 2012).
- P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997).
- K. Okunishi, T. Nishino, and H. Ueda, Developments in the tensor network—From statistical mechanics to quantum entanglement, J. Phys. Soc. Jpn. 91, 062001 (2022).
- T. L. Patti, J. Kossaifi, A. Anandkumar, and S. F. Yelin, Variational quantum optimization with multibasis encodings, Phys. Rev. Res. 4, 033142 (2022).
- B. A. Martin, T. Ayral, F. Jamet, M. J. Rančić, and P. Simon, Combining matrix product states and noisy quantum computers for quantum simulation, Phys. Rev. A 109, 062437 (2024).
- J. Bisgard, Analysis and Linear Algebra: The Singular Value Decomposition and Applications (AMS, Providence, 2021).
- E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv:1411.4028.
- L. Zhou, S. T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm, performance, mechanism, and implementation on near-term devices, PRX 10, 021067 (2020).
- M. Dupont, N. Didier, M. J. Hodson, J. E. Moore, and M. J. Reagor, Calibrating the classical hardness of the quantum approximate optimization algorithm, PRX Quantum 3, 040339 (2022).
- D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, Matrix product state representations, Quantum Inf. Comput. 7, 401 (2007).
- A. C. Nakhl, T. Quella, and M. Usman, Calibrating the role of entanglement in variational quantum circuits, Phys. Rev. A 109, 032413 (2024).
- H. Abraham et al., Qiskit: An open-source framework for quantum computing, Github, 2019, https://github.com/Qiskit.
- J. Gray, quimb: A Python package for quantum information and many-body calculations, J. Open Source Softw. 3, 819 (2018).
- G. Miki and Y. Tokura, Representative source code for: Entanglement-entropy-based scaling relation in QAOA tensor network simulations for the MAXCUT problem, Zenodo, 2026, https://zenodo.org/records/20792091.
