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

Resource Analysis of Quantum Optimization Algorithms via Variational Methods

Vitor Dallabona, Lucas Friedrich, Jonas Maziero

quant-phSubmitted Oct 21, 2026• Announced Oct 22, 2026• 0 citations
arXivHTMLPDF

Abstract

Variational Quantum Algorithms (VQAs) are promising approaches for solving combinatorial optimization problems on near-term quantum devices. However, the role played by quantum resources such as entanglement and coherence during the optimization process remains poorly understood. In this work, we investigate the evolution of these resources in two VQAs--the Quantum Approximate Optimization Algorithm (QAOA) and the Feedback-based Algorithm for Quantum Optimization (FALQON)--applied to the Minimum Vertex Cover problem. We employ a variational resource-quantification framework based on the Bures metric and Uhlmann's theorem, in which an auxiliary quantum circuit is optimized to identify the closest resource-free states. This approach allows us to quantify Bures entanglement and Bures coherence of the algorithmic states without requiring full quantum state tomography. For the considered problem instance, QAOA exhibits a pronounced accumulation of entanglement in its initial layers, followed by a progressive reduction as the algorithm converges toward the optimal solution. Its coherence likewise decreases overall with increasing circuit depth, although a finite residual value persists due to the degeneracy of the optimal-solution subspace. In contrast, FALQON exhibits a substantially lower entanglement peak, reached at larger circuit depth, followed by a decay as convergence proceeds. Its coherence decreases smoothly and monotonically together with the optimization error. These results reveal distinct quantum-resource trajectories associated with the two optimization strategies and illustrate how entanglement and coherence evolve as variational quantum states approach solutions of a classical combinatorial optimization problem.

AI Summary

The paper examines how entanglement and computational-basis coherence vary as quantum optimization algorithms approach solutions, and as molecular ground states become more correlated. It applies an existing variational resource-quantification framework to QAOA, FALQON, and FALQON+ on one four-vertex minimum vertex cover instance, and to four-qubit VQE simulations of $H_2$ in the STO-3G basis. The framework estimates Bures-based resource measures by optimizing auxiliary circuits representing purifications of separable or incoherent states. Uhlmann’s theorem converts the calculation into fidelity optimization; overlaps can be measured using a SWAP test without full state tomography. Resource estimates are evaluated after optimizing each circuit depth or molecular geometry. For the vertex-cover instance, QAOA’s estimated entanglement peaks at depth $p=1$ and subsequently decreases. FALQON has a lower peak near $p=16$, followed by decay. FALQON+ peaks near $0.35$ at $p=2$ and approaches zero for $p\geq5$. Coherence generally decreases alongside the reported probability-distribution error. Residual coherence in QAOA and FALQON+ is interpreted as compatible with superpositions of the two optimal bitstrings, $1010$ and $0110$. For $H_2$, entanglement and coherence are low near equilibrium, $R\approx1.40\,a_0$, and increase upon bond stretching. The paper explicitly treats these trajectories as instance-, algorithm-, and quantification-dependent rather than universal. It notes that correlations do not establish causation, degeneracy does not guarantee residual coherence, and low resource estimates alone establish neither efficient classical simulation nor reliable execution on noisy hardware.

Some signs of AI-generated textIncrementalSmall numerics onlyMissing comparisonUnclear novelty

Error found: The paper defines MSE against a single optimal bitstring but interprets vanishing MSE as compatible with finite pure-state coherence from a superposition of two optimal bitstrings; symmetry-preserving QAOA instead has an MSE floor of 1/32 against either bitstring when entirely within this optimal subspace. The paper reports bipartite Bures entanglement without identifying the qubit bipartition, leaving the entanglement trajectories incompletely specified.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
12 pages, 9 figures

Related papers

Variational quantum algorithm for entanglement quantification

Lucas Friedrich, Marcos L. W. Basso, Alberto B. de Palhares +4 more

Quantum entanglement is a foundational resource in quantum information science, underpinning applications across physics. However, detecting and quantifying entanglement remains a significant challenge. In this article, we introduce a variational quantum algorithm inspired by Uhlmann's theorem to quantify the Bures entanglement of general quantum states, a method that naturally extends to other quantum resources, including genuine multipartite entanglement, quantum discord, quantum coherence, and total correlations, while also enabling reconstruction of the closest free states. The algorithm requires a polynomial number of ancillary qubits and circuit depth relative to the system size, dimensionality, and free-state cardinality, making it scalable for practical implementations. Thus, it provides a versatile framework for quantifying quantum resources, demonstrated here through several applications.

arXiv:2507.20813•Physical Review A•Nov 25, 2025•2 citations

Detrimental Agnostic Entanglement: The Case Against Hardware-Efficient Ansätze for Combinatorial Optimization

Tobias Rohe, Markus Baumann, Federico Harjes Ruiloba +3 more

Variational quantum algorithms (VQAs) for combinatorial optimization routinely employ entangling gates as a default design choice, yet the role of entanglement, in its amount and structure, remains poorly understood. This gap is particularly consequential for problems governed by diagonal Hamiltonians, whose ground states are classical product states and therefore require no entanglement in principle, raising the fundamental question of whether and how entangling gates help or hinder the variational search. We investigate this question for MaxCut by introducing two complementary control mechanisms that provide smooth, monotonic control over hardware-efficient ansatz (HEA) entanglement as quantified by the Meyer-Wallach measure $Q$, and by benchmarking against QAOA as a problem-structured reference. Tracking the entanglement trajectory $Q(t)$ throughout VQA training reveals that when the ansatz grants the optimizer indirect control over entanglement through its parameters, it consistently drives entanglement down. In line with this tendency, a fully separable ansatz outperforms all entangled hardware-efficient configurations, establishing a monotonic relationship: less problem-agnostic entanglement yields better performance. In contrast, QAOA, whose entanglement is structurally derived from the problem Hamiltonian, maintains high entanglement yet achieves competitive solution quality, demonstrating that entanglement structure, not merely quantity, determines its utility. These findings suggest that HEAs for diagonal Hamiltonians are inappropriate and that variational approaches to combinatorial optimization should prioritize problem-structured circuit designs.

quant-pharXiv:2605.19827•IEEE International Conference on Quantum Software (QSW)•May 20, 2026•2 citations

Variational Quantum Algorithms for Combinatorial Optimization

Daniel F. Pérez-Ramírez

The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.

arXiv:2407.06421•Jul 8, 2024•20 citations

Performant near-term quantum combinatorial optimization

Titus Morris, Kaushik, Ananth, Martin Roetteler +1 more

Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.

arXiv:2404.16135•Apr 24, 2024•21 citations

Role of overparametrization in quantum approximate optimization

Daniil Rabinovich, Andrey Kardashin, Soumik Adhikary

Variational quantum algorithms have emerged as a cornerstone of contemporary quantum algorithms research. While they have demonstrated considerable promise in solving problems of practical interest, efficiently determining the minimal quantum resources necessary to obtain such a solution remains an open question. In this work, inspired by concepts from classical machine learning, we investigate the impact of overparameterization on the performance of variational algorithms. Our study focuses on the quantum approximate optimization algorithm (QAOA) -- a prominent variational quantum algorithm designed to solve combinatorial optimization problems. We investigate if circuit overparametrization is necessary and sufficient to solve such problems in QAOA, considering two representative problems -- MAX-CUT and MAX-2-SAT. For MAX-CUT we observe that overparametriation is both sufficient and (statistically) necessary for attaining exact solutions, as confirmed numerically for up to $20$ qubits. In fact, for MAX-CUT on 2-regular graphs we show the necessity to be exact, based on the analytically found optimal depth. In sharp contrast, for MAX-2-SAT, underparametrized circuits suffice to solve most instances. This result highlights the potential of QAOA in the underparametrized regime, supporting its utility for current noisy devices.

arXiv:2508.10086•Physical Review A•May 26, 2026•3 citations

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

Boris I. Bantysh, Andrey Yu. Chernyavskiy, Denis A. Kulikov +2 more

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.

quant-pharXiv:2609.15738•Sep 15, 2026•1 citation
Variational Quantum Algorithms (VQAs) are promising approaches for solving combinatorial optimization problems on near-term quantum devices. However, the role played by quantum resources such as entanglement and coherence during the optimization process remains poorly understood. In this work, we investigate the evolution of these resources in two VQAs--the Quantum Approximate Optimization Algorithm (QAOA) and the Feedback-based Algorithm for Quantum Optimization (FALQON)--applied to the Minimum Vertex Cover problem. We employ a variational resource-quantification framework based on the Bures metric and Uhlmann's theorem, in which an auxiliary quantum circuit is optimized to identify the closest resource-free states. This approach allows us to quantify Bures entanglement and Bures coherence of the algorithmic states without requiring full quantum state tomography. For the considered problem instance, QAOA exhibits a pronounced accumulation of entanglement in its initial layers, followed by a progressive reduction as the algorithm converges toward the optimal solution. Its coherence likewise decreases overall with increasing circuit depth, although a finite residual value persists due to the degeneracy of the optimal-solution subspace. In contrast, FALQON exhibits a substantially lower entanglement peak, reached at larger circuit depth, followed by a decay as convergence proceeds. Its coherence decreases smoothly and monotonically together with the optimization error. These results reveal distinct quantum-resource trajectories associated with the two optimization strategies and illustrate how entanglement and coherence evolve as variational quantum states approach solutions of a classical combinatorial optimization problem.
The paper examines how entanglement and computational-basis coherence vary as quantum optimization algorithms approach solutions, and as molecular ground states become more correlated. It applies an existing variational resource-quantification framework to QAOA, FALQON, and FALQON+ on one four-vertex minimum vertex cover instance, and to four-qubit VQE simulations of H2H_2H2​ in the STO-3G basis.
The framework estimates Bures-based resource measures by optimizing auxiliary circuits representing purifications of separable or incoherent states. Uhlmann’s theorem converts the calculation into fidelity optimization; overlaps can be measured using a SWAP test without full state tomography. Resource estimates are evaluated after optimizing each circuit depth or molecular geometry.
For the vertex-cover instance, QAOA’s estimated entanglement peaks at depth p=1p=1p=1 and subsequently decreases. FALQON has a lower peak near p=16p=16p=16, followed by decay. FALQON+ peaks near 0.350.350.35 at p=2p=2p=2 and approaches zero for p≥5p\geq5p≥5. Coherence generally decreases alongside the reported probability-distribution error. Residual coherence in QAOA and FALQON+ is interpreted as compatible with superpositions of the two optimal bitstrings, 101010101010 and 011001100110. For H2H_2H2​, entanglement and coherence are low near equilibrium, R≈1.40 a0R\approx1.40\,a_0R≈1.40a0​, and increase upon bond stretching.
The paper explicitly treats these trajectories as instance-, algorithm-, and quantification-dependent rather than universal. It notes that correlations do not establish causation, degeneracy does not guarantee residual coherence, and low resource estimates alone establish neither efficient classical simulation nor reliable execution on noisy hardware.
Quantum entanglement is a foundational resource in quantum information science, underpinning applications across physics. However, detecting and quantifying entanglement remains a significant challenge. In this article, we introduce a variational quantum algorithm inspired by Uhlmann's theorem to quantify the Bures entanglement of general quantum states, a method that naturally extends to other quantum resources, including genuine multipartite entanglement, quantum discord, quantum coherence, and total correlations, while also enabling reconstruction of the closest free states. The algorithm requires a polynomial number of ancillary qubits and circuit depth relative to the system size, dimensionality, and free-state cardinality, making it scalable for practical implementations. Thus, it provides a versatile framework for quantifying quantum resources, demonstrated here through several applications.
Variational quantum algorithms (VQAs) for combinatorial optimization routinely employ entangling gates as a default design choice, yet the role of entanglement, in its amount and structure, remains poorly understood. This gap is particularly consequential for problems governed by diagonal Hamiltonians, whose ground states are classical product states and therefore require no entanglement in principle, raising the fundamental question of whether and how entangling gates help or hinder the variational search. We investigate this question for MaxCut by introducing two complementary control mechanisms that provide smooth, monotonic control over hardware-efficient ansatz (HEA) entanglement as quantified by the Meyer-Wallach measure QQQ, and by benchmarking against QAOA as a problem-structured reference. Tracking the entanglement trajectory Q(t)Q(t)Q(t) throughout VQA training reveals that when the ansatz grants the optimizer indirect control over entanglement through its parameters, it consistently drives entanglement down. In line with this tendency, a fully separable ansatz outperforms all entangled hardware-efficient configurations, establishing a monotonic relationship: less problem-agnostic entanglement yields better performance. In contrast, QAOA, whose entanglement is structurally derived from the problem Hamiltonian, maintains high entanglement yet achieves competitive solution quality, demonstrating that entanglement structure, not merely quantity, determines its utility. These findings suggest that HEAs for diagonal Hamiltonians are inappropriate and that variational approaches to combinatorial optimization should prioritize problem-structured circuit designs.
The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.
Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.
Variational quantum algorithms have emerged as a cornerstone of contemporary quantum algorithms research. While they have demonstrated considerable promise in solving problems of practical interest, efficiently determining the minimal quantum resources necessary to obtain such a solution remains an open question. In this work, inspired by concepts from classical machine learning, we investigate the impact of overparameterization on the performance of variational algorithms. Our study focuses on the quantum approximate optimization algorithm (QAOA) -- a prominent variational quantum algorithm designed to solve combinatorial optimization problems. We investigate if circuit overparametrization is necessary and sufficient to solve such problems in QAOA, considering two representative problems -- MAX-CUT and MAX-2-SAT. For MAX-CUT we observe that overparametriation is both sufficient and (statistically) necessary for attaining exact solutions, as confirmed numerically for up to 202020 qubits. In fact, for MAX-CUT on 2-regular graphs we show the necessity to be exact, based on the analytically found optimal depth. In sharp contrast, for MAX-2-SAT, underparametrized circuits suffice to solve most instances. This result highlights the potential of QAOA in the underparametrized regime, supporting its utility for current noisy devices.
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.