Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.19502

Entanglement Scaling and Problem Structure in Quantum Approximate and Adiabatic Optimization Algorithms

Georgios Arapantonis, Paraj Titum, Gregory Quiroz

quant-phSubmitted Jun 17, 2026• Announced Jun 19, 2026• 0 citations• Revised Jun 24, 2026 (v2)
v1 · Jun 17, 2026v2 · Jun 24, 2026
arXivHTMLPDF

Abstract

Entanglement is widely regarded as a key resource underlying the power of quantum algorithms and their potential to achieve quantum advantage. With the emergence of variational quantum algorithms, however, questions have arisen regarding how entanglement relates to problem structure and algorithmic performance in near-term quantum applications. Here, we examine this relationship through the Quantum Approximate Optimization Algorithm (QAOA), a specific class of variational algorithms, applied to the MaxCut problem. We show that suboptimal variational parameter training can significantly modify the observed entanglement profile, obscuring its scaling behavior. By employing a high-performance optimizer, we find empirical evidence that QAOA exhibits entanglement scaling consistent with that of fermionic Gaussian states (up to a scaling factor) across a broad range of MaxCut instances. We further compare these results with adiabatic quantum computation, observing annealing-schedule-dependent entanglement profiles whose scaling behavior differs markedly from that of QAOA. Together, these findings provide new insight into how entanglement manifests in and distinguishes these two algorithmic paradigms, highlighting its connection to both computational performance and problem structure.

Related papers

Entanglement-entropy-based scaling relation in QAOA tensor network simulations for the MAXCUT problem

Goro Miki, 康弘 都倉

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. Furthermore, by analyzing the results of the numerical calculations, we propose a new 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 new insights into the theoretical foundation of the scaling relations presented in previous studies.

arXiv:2505.23256•Physical Review A•Jun 10, 2026•0 citations

Scaling QAOA: transferring optimal adiabatic schedules from small-scale to large-scale variational circuits

Ugo Nzongani, Dylan Laplace Mermoud, Arthur Braida

The Quantum Approximate Optimization Algorithm (QAOA) is a leading approach for combinatorial optimization on near-term quantum devices, yet its scalability is limited by the difficulty of optimizing \(2p\) variational parameters for a large number \(p\) of layers. Recent empirical studies indicate that optimal QAOA angles exhibit concentration and transferability across problem sizes. Leveraging this observation, we propose a schedule-learning framework that transfers spectral-gap-informed adiabatic control strategies from small-scale instances to larger systems. Our method extracts the spectral gap profile of small problems and constructs a continuous schedule governed by \(\partial_t s = κg^q(s)\), where \(g(s)\) is the instantaneous gap and \((κ, q)\) are global hyperparameters. Discretizing this schedule yields closed-form expressions for all QAOA angles, reducing the classical optimization task from \(2p\) parameters to only \(2\), independent of circuit depth. This drastic parameter compression mitigates classical optimization overhead and reduces sensitivity to barren plateau phenomena. Numerical simulations on random QUBO and 3-regular MaxCut instances demonstrate that the learnt schedules transfer effectively to larger systems while achieving competitive approximation ratios. Our results suggest that gap-informed schedule transfers provide a scalable and parameter-efficient strategy for QAOA.

quant-pharXiv:2602.14986•IEEE International Conference on Quantum Control, Computing and Learning (qCCL)•Feb 17, 2026•0 citations

Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

Leo Zhou, Sheng-Tao Wang, Soonwon Choi +2 more

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.

arXiv:1812.01041•Physical Review X•Jun 24, 2020•932 citations

Evaluating Quantum Approximate Optimization Algorithm: A Case Study

Ruslan Shaydulin, Yuri Alexeev

Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum algorithms for the Noisy Intermediate-Scale Quantum (NISQ) era. Quantifying the performance of QAOA in the near-term regime is of utmost importance. We perform a large-scale numerical study of the approximation ratios attainable by QAOA is the low-to medium-depth regime. To find good QAOA parameters we perform 990 million 10-qubit QAOA circuit evaluations. We find that the approximation ratio increases only marginally as the depth is increased, and the gains are offset by the increasing complexity of optimizing variational parameters. We observe a high variation in approximation ratios attained by QAOA, including high variations within the same class of problem instances. We observe that the difference in approximation ratios between problem instances increases as the similarity between instances decreases. We find that optimal QAOA parameters concentrate for instances in out benchmark, confirming the previous findings for a different class of problems.

arXiv:1910.04881•International Green and Sustainable Computing Conference•Oct 1, 2019•55 citations

Entanglement perspective on the quantum approximate optimization algorithm

Maxime Dupont, Nicolas Didier, Mark J. Hodson +2 more

Many quantum algorithms seek to output a specific bitstring solving the problem of interest---or a few if the solution is degenerate. It is the case for the quantum approximate optimization algorithm (QAOA) in the limit of large circuit depth, which aims to solve quadratic unconstrained binary optimization problems. Hence, the expected final state for these algorithms is either a product state or a low-entangled superposition involving a few bitstrings. What happens in between the initial $N$-qubit product state ${|0\ensuremath{\rangle}}^{\ensuremath{\bigotimes}N}$ and the final one regarding entanglement? Here, we consider the QAOA algorithm for solving the paradigmatic MaxCut problem on different types of graphs. We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits and find that there is a volume-law entanglement barrier between the initial and final states. We also investigate the entanglement spectrum in connection with random matrix theory. In addition, we compare the entanglement production with a quantum annealing protocol aiming to solve the same MaxCut problems. Finally, we discuss the implications of our results for the simulation of QAOA circuits with tensor network-based methods relying on low-entanglement for efficiency, such as matrix product states.

arXiv:2206.07024•Physical Review A•Aug 22, 2022•39 citations

Behavior of Analog Quantum Algorithms.

Lucas T. Brady, Lucas Kocia, Przemysław Bienias +2 more

Analog quantum algorithms are formulated in terms of Hamiltonians rather than unitary gates and include quantum adiabatic computing, quantum annealing, and the Quantum Approximate Optimization Algorithm (QAOA).These algorithms are promising candidates for near-term quantum applications, but they often require fine tuning via the annealing schedule or variational parameters.In this work we connect all these algorithms to the optimal analog procedure.Notably, we explore how the optimal procedure approaches a smooth adiabatic procedure but with a superposed oscillatory pattern that can be explained in terms of the interactions between the ground state and first excited state.Furthermore, we provide numeric and analytic evidence that QAOA emulates this optimal procedure with the length of each QAOA layer equal to the period of the oscillatory pattern.Furthermore, the ratios of the QAOA bangs is determined by the smooth, non-oscillatory part of the optimal procedure.We provide arguments for these phenomena in terms of the product formula expansion of the optimal procedure.All of this shows that these analog algorithms are all different limits and approximations of the same optimal quantum protocol.In the appendix, we present a new algorithm for better approximating the optimal protocol using the insights from the main body.

arXiv:2107.01218•Mar 1, 2021•14 citations
Entanglement is widely regarded as a key resource underlying the power of quantum algorithms and their potential to achieve quantum advantage. With the emergence of variational quantum algorithms, however, questions have arisen regarding how entanglement relates to problem structure and algorithmic performance in near-term quantum applications. Here, we examine this relationship through the Quantum Approximate Optimization Algorithm (QAOA), a specific class of variational algorithms, applied to the MaxCut problem. We show that suboptimal variational parameter training can significantly modify the observed entanglement profile, obscuring its scaling behavior. By employing a high-performance optimizer, we find empirical evidence that QAOA exhibits entanglement scaling consistent with that of fermionic Gaussian states (up to a scaling factor) across a broad range of MaxCut instances. We further compare these results with adiabatic quantum computation, observing annealing-schedule-dependent entanglement profiles whose scaling behavior differs markedly from that of QAOA. Together, these findings provide new insight into how entanglement manifests in and distinguishes these two algorithmic paradigms, highlighting its connection to both computational performance and problem structure.
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. Furthermore, by analyzing the results of the numerical calculations, we propose a new 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 new insights into the theoretical foundation of the scaling relations presented in previous studies.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading approach for combinatorial optimization on near-term quantum devices, yet its scalability is limited by the difficulty of optimizing 2p2p2p variational parameters for a large number ppp of layers. Recent empirical studies indicate that optimal QAOA angles exhibit concentration and transferability across problem sizes. Leveraging this observation, we propose a schedule-learning framework that transfers spectral-gap-informed adiabatic control strategies from small-scale instances to larger systems. Our method extracts the spectral gap profile of small problems and constructs a continuous schedule governed by ∂ts=κgq(s)\partial_t s = κg^q(s)∂t​s=κgq(s), where g(s)g(s)g(s) is the instantaneous gap and (κ,q)(κ, q)(κ,q) are global hyperparameters. Discretizing this schedule yields closed-form expressions for all QAOA angles, reducing the classical optimization task from 2p2p2p parameters to only 222, independent of circuit depth. This drastic parameter compression mitigates classical optimization overhead and reduces sensitivity to barren plateau phenomena. Numerical simulations on random QUBO and 3-regular MaxCut instances demonstrate that the learnt schedules transfer effectively to larger systems while achieving competitive approximation ratios. Our results suggest that gap-informed schedule transfers provide a scalable and parameter-efficient strategy for QAOA.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.
Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum algorithms for the Noisy Intermediate-Scale Quantum (NISQ) era. Quantifying the performance of QAOA in the near-term regime is of utmost importance. We perform a large-scale numerical study of the approximation ratios attainable by QAOA is the low-to medium-depth regime. To find good QAOA parameters we perform 990 million 10-qubit QAOA circuit evaluations. We find that the approximation ratio increases only marginally as the depth is increased, and the gains are offset by the increasing complexity of optimizing variational parameters. We observe a high variation in approximation ratios attained by QAOA, including high variations within the same class of problem instances. We observe that the difference in approximation ratios between problem instances increases as the similarity between instances decreases. We find that optimal QAOA parameters concentrate for instances in out benchmark, confirming the previous findings for a different class of problems.
Many quantum algorithms seek to output a specific bitstring solving the problem of interest---or a few if the solution is degenerate. It is the case for the quantum approximate optimization algorithm (QAOA) in the limit of large circuit depth, which aims to solve quadratic unconstrained binary optimization problems. Hence, the expected final state for these algorithms is either a product state or a low-entangled superposition involving a few bitstrings. What happens in between the initial NNN-qubit product state ${|0\ensuremath{\rangle}}^{\ensuremath{\bigotimes}N}$ and the final one regarding entanglement? Here, we consider the QAOA algorithm for solving the paradigmatic MaxCut problem on different types of graphs. We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits and find that there is a volume-law entanglement barrier between the initial and final states. We also investigate the entanglement spectrum in connection with random matrix theory. In addition, we compare the entanglement production with a quantum annealing protocol aiming to solve the same MaxCut problems. Finally, we discuss the implications of our results for the simulation of QAOA circuits with tensor network-based methods relying on low-entanglement for efficiency, such as matrix product states.
Analog quantum algorithms are formulated in terms of Hamiltonians rather than unitary gates and include quantum adiabatic computing, quantum annealing, and the Quantum Approximate Optimization Algorithm (QAOA).These algorithms are promising candidates for near-term quantum applications, but they often require fine tuning via the annealing schedule or variational parameters.In this work we connect all these algorithms to the optimal analog procedure.Notably, we explore how the optimal procedure approaches a smooth adiabatic procedure but with a superposed oscillatory pattern that can be explained in terms of the interactions between the ground state and first excited state.Furthermore, we provide numeric and analytic evidence that QAOA emulates this optimal procedure with the length of each QAOA layer equal to the period of the oscillatory pattern.Furthermore, the ratios of the QAOA bangs is determined by the smooth, non-oscillatory part of the optimal procedure.We provide arguments for these phenomena in terms of the product formula expansion of the optimal procedure.All of this shows that these analog algorithms are all different limits and approximations of the same optimal quantum protocol.In the appendix, we present a new algorithm for better approximating the optimal protocol using the insights from the main body.