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:2609.15738

Disentangling QAOA: From Weakly Entangled Circuits to a Classical QUBO Solver

Boris I. Bantysh, Andrey Yu. Chernyavskiy, Denis A. Kulikov, Maksim A. Gavreev, Evgeniy O. Kiktenko

quant-phSubmitted Sep 14, 2026• Announced Sep 15, 2026• 0 citations
arXivHTMLPDF

Abstract

The role of entanglement in quantum optimization remains actively debated. To address this question, we focus on the fixed-parameter expanding-depth regime of the quantum approximate optimization algorithm (QAOA), where a compact two-parameter schedule is trained once on small instances and then applied as the problem size and circuit depth increase. To probe this regime beyond full state-vector simulation, we perform approximate matrix product state simulations for up to 50 qubits and 100 layers and quantify entanglement by the bond dimension. We observe an entangle--disentangle profile, with the peak bond dimension decreasing with depth and eventually saturating. This observation motivates an extreme approximation: projecting the state onto the product-state manifold (bond dimension one) after every two-qubit interaction. Based on this approximation, we introduce BOND-1, a quantum-inspired classical solver. Despite the drastic simplification, BOND-1 achieves cut ratios above 0.95 relative to the best known values on standard GSet MaxCut benchmarks with up to 20000 variables, and in some cases it matches those values. It achieves these results without per-instance optimization and has linear memory cost, while per-instance tuning can provide further improvement. These results show that, in this regime, a substantial fraction of the optimization power of QAOA survives even in the complete absence of entanglement. Our conclusions, however, are specific to this setting and do not imply that entanglement is unnecessary for quantum optimization in general.

Related papers

The Quantum Approximate Optimization Algorithm performance with low entanglement and high circuit depth

Rishi Sreedhar, Pontus Vikstål, Marika Svensson +3 more

Variational quantum algorithms constitute one of the most widespread methods for using current noisy quantum computers. However, it is unknown if these heuristic algorithms provide any quantum-computational speedup, although we cannot simulate them classically for intermediate sizes. Since entanglement lies at the core of quantum computing power, we investigate its role in these heuristic methods for solving optimization problems. In particular, we use matrix product states to simulate the quantum approximate optimization algorithm with reduced bond dimensions $D$, a parameter bounding the system entanglement. Moreover, we restrict the simulation further by deterministically sampling solutions. We conclude that entanglement plays a minor role in the MaxCut and Exact Cover 3 problems studied here since the simulated algorithm analysis, with up to $60$ qubits and $p=100$ algorithm layers, shows that it provides solutions for bond dimension $D \approx 10$ and depth $p \approx 30$. Additionally, we study the classical optimization loop in the approximated algorithm simulation with $12$ qubits and depth up to $p=4$ and show that the approximated optimal parameters with low entanglement approach the exact ones.

arXiv:2207.03404•Jul 7, 2022•8 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

Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm

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

The trading of fidelity for scale enables approximate classical simulators such as matrix product states (MPSs) to run quantum circuits beyond exact methods.A control parameter, the so-called bond dimension χ for MPSs, governs the allocated computational resources and the output fidelity.Here, we characterize the fidelity for the quantum approximate optimization algorithm by the expectation value of the cost function that it seeks to minimize and find that it follows a scaling law F ln χ N , where N is the number of qubits.With ln χ amounting to the entanglement that a MPS can encode, we show that the relevant variable for investigating the fidelity is the entanglement per qubit.Importantly, our results calibrate the classical computational power required to achieve the desired fidelity and benchmark the performance of quantum hardware in a realistic setup.For instance, we quantify the hardness of performing better classically than a noisy superconducting quantum processor by readily matching its output to the scaling function.Moreover, we relate the global fidelity to that of individual operations and establish its relationship with χ and N .We sharpen the requirements for noisy quantum computers to outperform classical techniques at running a quantum optimization algorithm in speed, size, and fidelity.

arXiv:2206.06348•PRX Quantum•Dec 30, 2022•13 citations

How Much Entanglement Do Quantum Optimization Algorithms Require?

Yanzhu Chen, Zhu, Linghua, Chenxu Liu +3 more

Many classical optimization problems can be mapped to finding the ground states of diagonal Ising Hamiltonians, for which variational quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) provide heuristic methods. Because the solutions of such classical optimization problems are necessarily product states, it is unclear how entanglement affects their performance. An Adaptive Derivative-Assembled Problem-Tailored (ADAPT) variation of QAOA improves the convergence rate by allowing entangling operations in the mixer layers whereas it requires fewer CNOT gates in the entire circuit. In this work, we study the entanglement generated during the execution of ADAPT-QAOA. Through simulations of the weighted Max-Cut problem, we show that ADAPT-QAOA exhibits substantial flexibility in entangling and disentangling qubits. By incrementally restricting this flexibility, we find that a larger amount of entanglement entropy at earlier stages coincides with faster convergence at later stages. In contrast, while the standard QAOA quickly generates entanglement within a few layers, it cannot remove excess entanglement efficiently. Our results demonstrate that the role of entanglement in quantum optimization is subtle and provide guidance for building favorable features into quantum optimization algorithms.

arXiv:2205.12283•May 24, 2022•1 citation

On the power of the Quantum Approximate Optimization Algorithm

Sami Boulebnane

The main object of study of this work is the Quantum Approximate Optimization Algorithm (QAOA) —the best-known heuristic quantum algorithm for addressing combinatorial optimization problems. Despite its popularity, QAOA poses major challenges. Namely, its performance remains poorly understood, especially in the low depth regime most relevant to near-term quantum computing. Besides, the algorithm is of variational nature, relying on several hyperparameters to be classically trained. In this work, we contribute to addressing these issues by developing techniques to understand the performance of QAOA at low depth, and deducing from these pretrained hyperparameters, thereby eliminating or considerably reducing the need for a classical optimization loop. We first consider applying QAOA to constraint satisfaction problems with the goal of maximizing the algorithm’s approximation ratio (fraction of satisfied constraints). As a particular example, we consider QAOA applied to MAXCUT on non-regular graphs, showing how analytic techniques provide good guess hyperparameters in this setting. Next, we analyze the performance of QAOA on a well-studied constraint satisfaction problem: random k-SAT. In this case, the performance is measured by the probability of finding an assignment satisfying all constraints (“success probability”). To estimate this quantity, we develop new techniques, mapping quantum expectation values of the QAOA circuits to classical spin models. We further show how these techniques can be generalized to a larger family of random constraint satisfaction problems. We conclude the work by two feasibility studies inspired by real-world use cases encountered in collaborations with industrial partners: peptide sampling, and solving flow problems. These problems are naturally phrased by encoding combinatorial variables in qudits, a relatively unexplored setting in the existing literature. We present partial analytic and numerical results for optimal QAOA hyperparameters and the scaling of its success probability in this framework, underlining potential specific difficulties when using QAOA with qudits.

•Nov 28, 2024•0 citations

Benchmarking the recursive quantum approximate optimization algorithm

Paige Frederick, Rich Rines, Frederic T. Chong +1 more

Recent results on the Quantum Approximate Optimization Algorithm (QAOA) have cast pessimism on its potential to exhibit practical quantum speedups. For instance, QAOA’s locality limits its performance on tasks such as coloring bipartite graphs—which is easy for classical methods. Motivated by these limitations, the Recursive QAOA was introduced to overcome the locality and symmetry of QAOA. Despite being more powerful than QAOA, RQAOA is fully classically simulable at level-1 depth (p = 1). We report results on RQAOA in this classically simulable regime, benchmarked on random Quantum Unconstrainted Binary Optimization (QUBO) problems with up to 100 variables. We find that RQAOA generally matches the performance of classical simulated annealing and significantly outperforms ordinary QAOA.

Quantum Computing, Communication, and Simulation•Mar 8, 2023•0 citations
The role of entanglement in quantum optimization remains actively debated. To address this question, we focus on the fixed-parameter expanding-depth regime of the quantum approximate optimization algorithm (QAOA), where a compact two-parameter schedule is trained once on small instances and then applied as the problem size and circuit depth increase. To probe this regime beyond full state-vector simulation, we perform approximate matrix product state simulations for up to 50 qubits and 100 layers and quantify entanglement by the bond dimension. We observe an entangle--disentangle profile, with the peak bond dimension decreasing with depth and eventually saturating. This observation motivates an extreme approximation: projecting the state onto the product-state manifold (bond dimension one) after every two-qubit interaction. Based on this approximation, we introduce BOND-1, a quantum-inspired classical solver. Despite the drastic simplification, BOND-1 achieves cut ratios above 0.95 relative to the best known values on standard GSet MaxCut benchmarks with up to 20000 variables, and in some cases it matches those values. It achieves these results without per-instance optimization and has linear memory cost, while per-instance tuning can provide further improvement. These results show that, in this regime, a substantial fraction of the optimization power of QAOA survives even in the complete absence of entanglement. Our conclusions, however, are specific to this setting and do not imply that entanglement is unnecessary for quantum optimization in general.
Variational quantum algorithms constitute one of the most widespread methods for using current noisy quantum computers. However, it is unknown if these heuristic algorithms provide any quantum-computational speedup, although we cannot simulate them classically for intermediate sizes. Since entanglement lies at the core of quantum computing power, we investigate its role in these heuristic methods for solving optimization problems. In particular, we use matrix product states to simulate the quantum approximate optimization algorithm with reduced bond dimensions DDD, a parameter bounding the system entanglement. Moreover, we restrict the simulation further by deterministically sampling solutions. We conclude that entanglement plays a minor role in the MaxCut and Exact Cover 3 problems studied here since the simulated algorithm analysis, with up to 606060 qubits and p=100p=100p=100 algorithm layers, shows that it provides solutions for bond dimension D≈10D \approx 10D≈10 and depth p≈30p \approx 30p≈30. Additionally, we study the classical optimization loop in the approximated algorithm simulation with 121212 qubits and depth up to p=4p=4p=4 and show that the approximated optimal parameters with low entanglement approach the exact ones.
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.
The trading of fidelity for scale enables approximate classical simulators such as matrix product states (MPSs) to run quantum circuits beyond exact methods.A control parameter, the so-called bond dimension χ for MPSs, governs the allocated computational resources and the output fidelity.Here, we characterize the fidelity for the quantum approximate optimization algorithm by the expectation value of the cost function that it seeks to minimize and find that it follows a scaling law F ln χ N , where N is the number of qubits.With ln χ amounting to the entanglement that a MPS can encode, we show that the relevant variable for investigating the fidelity is the entanglement per qubit.Importantly, our results calibrate the classical computational power required to achieve the desired fidelity and benchmark the performance of quantum hardware in a realistic setup.For instance, we quantify the hardness of performing better classically than a noisy superconducting quantum processor by readily matching its output to the scaling function.Moreover, we relate the global fidelity to that of individual operations and establish its relationship with χ and N .We sharpen the requirements for noisy quantum computers to outperform classical techniques at running a quantum optimization algorithm in speed, size, and fidelity.
Many classical optimization problems can be mapped to finding the ground states of diagonal Ising Hamiltonians, for which variational quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) provide heuristic methods. Because the solutions of such classical optimization problems are necessarily product states, it is unclear how entanglement affects their performance. An Adaptive Derivative-Assembled Problem-Tailored (ADAPT) variation of QAOA improves the convergence rate by allowing entangling operations in the mixer layers whereas it requires fewer CNOT gates in the entire circuit. In this work, we study the entanglement generated during the execution of ADAPT-QAOA. Through simulations of the weighted Max-Cut problem, we show that ADAPT-QAOA exhibits substantial flexibility in entangling and disentangling qubits. By incrementally restricting this flexibility, we find that a larger amount of entanglement entropy at earlier stages coincides with faster convergence at later stages. In contrast, while the standard QAOA quickly generates entanglement within a few layers, it cannot remove excess entanglement efficiently. Our results demonstrate that the role of entanglement in quantum optimization is subtle and provide guidance for building favorable features into quantum optimization algorithms.
The main object of study of this work is the Quantum Approximate Optimization Algorithm (QAOA) —the best-known heuristic quantum algorithm for addressing combinatorial optimization problems. Despite its popularity, QAOA poses major challenges. Namely, its performance remains poorly understood, especially in the low depth regime most relevant to near-term quantum computing. Besides, the algorithm is of variational nature, relying on several hyperparameters to be classically trained. In this work, we contribute to addressing these issues by developing techniques to understand the performance of QAOA at low depth, and deducing from these pretrained hyperparameters, thereby eliminating or considerably reducing the need for a classical optimization loop. We first consider applying QAOA to constraint satisfaction problems with the goal of maximizing the algorithm’s approximation ratio (fraction of satisfied constraints). As a particular example, we consider QAOA applied to MAXCUT on non-regular graphs, showing how analytic techniques provide good guess hyperparameters in this setting. Next, we analyze the performance of QAOA on a well-studied constraint satisfaction problem: random k-SAT. In this case, the performance is measured by the probability of finding an assignment satisfying all constraints (“success probability”). To estimate this quantity, we develop new techniques, mapping quantum expectation values of the QAOA circuits to classical spin models. We further show how these techniques can be generalized to a larger family of random constraint satisfaction problems. We conclude the work by two feasibility studies inspired by real-world use cases encountered in collaborations with industrial partners: peptide sampling, and solving flow problems. These problems are naturally phrased by encoding combinatorial variables in qudits, a relatively unexplored setting in the existing literature. We present partial analytic and numerical results for optimal QAOA hyperparameters and the scaling of its success probability in this framework, underlining potential specific difficulties when using QAOA with qudits.
Recent results on the Quantum Approximate Optimization Algorithm (QAOA) have cast pessimism on its potential to exhibit practical quantum speedups. For instance, QAOA’s locality limits its performance on tasks such as coloring bipartite graphs—which is easy for classical methods. Motivated by these limitations, the Recursive QAOA was introduced to overcome the locality and symmetry of QAOA. Despite being more powerful than QAOA, RQAOA is fully classically simulable at level-1 depth (p = 1). We report results on RQAOA in this classically simulable regime, benchmarked on random Quantum Unconstrainted Binary Optimization (QUBO) problems with up to 100 variables. We find that RQAOA generally matches the performance of classical simulated annealing and significantly outperforms ordinary QAOA.