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:2206.06400 · Quantum

Characterization of variational quantum algorithms using free fermions

Gabriel Matos, Chris N. Self, Zlatko Papić, Konstantinos Meichanetzidis, Henrik Dreyer

Published Mar 30, 2023• 10 citations
arXivHTMLPDF

Abstract

We study variational quantum algorithms from the perspective of free fermions. By deriving the explicit structure of the associated Lie algebras, we show that the Quantum Approximate Optimization Algorithm (QAOA) on a one-dimensional lattice – with and without decoupled angles – is able to prepare all fermionic Gaussian states respecting the symmetries of the circuit. Leveraging these results, we numerically study the interplay between these symmetries and the locality of the target state, and find that an absence of symmetries makes nonlocal states easier to prepare. An efficient classical simulation of Gaussian states, with system sizes up to 80 and deep circuits, is employed to study the behavior of the circuit when it is overparameterized. In this regime of optimization, we find that the number of iterations to converge to the solution scales linearly with system size. Moreover, we observe that the number of iterations to converge to the solution decreases exponentially with the depth of the circuit, until it saturates at a depth which is quadratic in system size. Finally, we conclude that the improvement in the optimization can be explained in terms of better local linear approximations provided by the gradients.

DOI
10.22331/q-2023-03-30-966

Related papers

Quantifying the Efficiency of State Preparation via Quantum Variational Eigensolvers

Gabriel Matos, Sonika Johri, Zlatko Papić

Recently, there has been much interest in the efficient preparation of complex quantum states using low-depth quantum circuits, such as the quantum approximate optimization algorithm (QAOA).While it has been numerically shown that such algorithms prepare certain correlated states of quantum spins with surprising accuracy, a systematic way of quantifying the efficiency of the QAOA in general classes of models has been lacking.Here, we propose that the success of the QAOA in preparing ordered states is related to the interaction distance of the target state, which measures how close that state is to the manifold of all Gaussian states in an arbitrary basis of single-particle modes.We numerically verify this for several examples of nonintegrable quantum models, including Ising models with two-and three-spin interactions and the cluster model in an external field.Our results suggest that the structure of the entanglement spectrum, as witnessed by the interaction distance, correlates with the success of QAOA state preparation, and that this correlation also contains information about different phases present in the model.We conclude that the QAOA typically finds a solution that perturbs around the closest free-fermion state.

arXiv:2007.14338•PRX Quantum•Jan 15, 2021•24 citations

Analyzing the Quantum Approximate Optimization Algorithm: Ansätze, Symmetries, and Lie Algebras

Sujay Kazi, Martín Larocca, Marco Andrés Farinati +3 more

The quantum approximate optimization algorithm (QAOA) has been proposed as a method to obtain approximate solutions for combinatorial optimization tasks. In this work, we study the underlying algebraic properties of three QAOA ansätze for the maximum-cut problem on connected graphs, while focusing on the generated Lie algebras as well as their invariant subspaces. Specifically, we analyze the standard QAOA ansatz as well as the orbit and multiangle ansätze. We are able to fully characterize the Lie algebras of the multiangle ansatz across arbitrary connected graphs, finding that they only fall into one of just six families. Aside from the cycle and path graphs, the Lie dimensions for every graph are exponentially large in the system size, meaning that multiangle ansätze are extremely prone to exhibiting barren plateaus. Then, a similar quasi-graph-independent Lie-algebraic characterization beyond the multiangle ansatz is impeded as the circuit exhibits additional “hidden” symmetries besides those naturally arising from a certain parity-superselection operator and all automorphisms of the considered graph. Disregarding the “hidden” symmetries, we can upper bound the dimensions of the orbit and the standard Lie algebras, and the dimensions of the associated invariant subspaces are determined via explicit character formulas. To finish, we conjecture that (for most graphs) the standard Lie algebras have only components that are either exponential or that grow, at most, polynomially with the system size. This would imply that the QAOA is either prone to barren plateaus or classically simulable. More generally, our work provides a symmetry framework and tools to analyze any desired variational quantum algorithm.

arXiv:2410.05187•PRX Quantum•Oct 14, 2025•10 citations

Efficient quantum circuits based on the quantum natural gradient

Ananda Roy, Sameer Erramilli, Robert Konik

Efficient preparation of arbitrary entangled quantum states is crucial for quantum computation. This is particularly important for noisy intermediate-scale quantum simulators relying on variational hybrid quantum-classical algorithms. To that end, we propose symmetry-conserving modified quantum approximate optimization algorithm (SCom-QAOA) circuits. The depths of these circuits depend not only on the desired fidelity to the target state but also on the amount of entanglement the state contains. The parameters of the SCom-QAOA circuits are optimized using the quantum natural gradient method based on the Fubini-Study metric. The SCom-QAOA circuit transforms an unentangled state into a ground state of a gapped one-dimensional Hamiltonian with a circuit depth that depends not on the system size but rather on the finite correlation length. In contrast, the circuit depth grows proportionally to the system size for preparing low-lying states of critical one-dimensional systems. Even in the latter case, SCom-QAOA circuits with depth less than the system size were sufficient to generate states with fidelity in excess of 99%, which is relevant for near-term applications. The proposed scheme enlarges the set of the initial states accessible for variational quantum algorithms and widens the scope of investigation of nonequilibrium phenomena in quantum simulators. Published by the American Physical Society 2024

arXiv:2310.10538•Physical Review Research•Nov 4, 2024•5 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•0 citations

Trainability Analysis of Quantum Optimization Algorithms from a Bayesian Lens

Yanqi Song, Yusen Wu, Su‐Juan Qin +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is an extensively studied variational quantum algorithm utilized for solving optimization problems on near-term quantum devices. A significant focus is placed on determining the effectiveness of training the $n$-qubit QAOA circuit, i.e., whether the optimization error can converge to a constant level as the number of optimization iterations scales polynomially with the number of qubits. In realistic scenarios, the landscape of the corresponding QAOA objective function is generally non-convex and contains numerous local optima. In this work, motivated by the favorable performance of Bayesian optimization in handling non-convex functions, we theoretically investigate the trainability of the QAOA circuit through the lens of the Bayesian approach. This lens considers the corresponding QAOA objective function as a sample drawn from a specific Gaussian process. Specifically, we focus on two scenarios: the noiseless QAOA circuit and the noisy QAOA circuit subjected to local Pauli channels. Our first result demonstrates that the noiseless QAOA circuit with a depth of $\tilde{\mathcal{O}}\left(\sqrt{\log n}\right)$ can be trained efficiently, based on the widely accepted assumption that either the left or right slice of each block in the circuit forms a local 1-design. Furthermore, we show that if each quantum gate is affected by a $q$-strength local Pauli channel with the noise strength range of $1/{\rm poly} (n)$ to 0.1, the noisy QAOA circuit with a depth of $\mathcal{O}\left(\log n/\log(1/q)\right)$ can also be trained efficiently. Our results offer valuable insights into the theoretical performance of quantum optimization algorithms in the noisy intermediate-scale quantum era.

arXiv:2310.06270•Oct 10, 2023•1 citation

On the dynamical Lie algebras of quantum approximate optimization algorithms

Jonathan Allcock, Miklós Sántha, Yuan Pei +1 more

Dynamical Lie algebras (DLAs) have emerged as a valuable tool in the study of parameterized quantum circuits, helping to characterize both their expressiveness and trainability. In particular, the absence or presence of barren plateaus (BPs) – flat regions in parameter space that prevent the efficient training of variational quantum algorithms – has recently been shown to be intimately related to quantities derived from the associated DLA.In this work, we investigate DLAs for the quantum approximate optimization algorithm (QAOA), one of the most studied variational quantum algorithms for solving graph MaxCut and other combinatorial optimization problems. While DLAs for QAOA circuits have been studied before, existing results have either been based on numerical evidence, or else correspond to DLA generators specifically chosen to be universal for quantum computation on a subspace of states. We initiate an analytical study of barren plateaus and other statistics of QAOA algorithms, and give bounds on the dimensions of the corresponding DLAs and their centers for general graphs. We then focus on the n -vertex cycle and complete graphs. For the cycle graph we give an explicit basis, identify its decomposition into the direct sum of a 2 -dimensional center and a semisimple component isomorphic to n − 1 copies of s u ( 2 ) . We give an explicit basis for this isomorphism, and a closed-form expression for the variance of the cost function, proving the absence of BPs. For the complete graph we prove that the dimension of the DLA is O ( n 3 ) and give an explicit basis for the DLA.

arXiv:2407.12587•Quantum•May 29, 2026•1 citation
We study variational quantum algorithms from the perspective of free fermions. By deriving the explicit structure of the associated Lie algebras, we show that the Quantum Approximate Optimization Algorithm (QAOA) on a one-dimensional lattice – with and without decoupled angles – is able to prepare all fermionic Gaussian states respecting the symmetries of the circuit. Leveraging these results, we numerically study the interplay between these symmetries and the locality of the target state, and find that an absence of symmetries makes nonlocal states easier to prepare. An efficient classical simulation of Gaussian states, with system sizes up to 80 and deep circuits, is employed to study the behavior of the circuit when it is overparameterized. In this regime of optimization, we find that the number of iterations to converge to the solution scales linearly with system size. Moreover, we observe that the number of iterations to converge to the solution decreases exponentially with the depth of the circuit, until it saturates at a depth which is quadratic in system size. Finally, we conclude that the improvement in the optimization can be explained in terms of better local linear approximations provided by the gradients.
Recently, there has been much interest in the efficient preparation of complex quantum states using low-depth quantum circuits, such as the quantum approximate optimization algorithm (QAOA).While it has been numerically shown that such algorithms prepare certain correlated states of quantum spins with surprising accuracy, a systematic way of quantifying the efficiency of the QAOA in general classes of models has been lacking.Here, we propose that the success of the QAOA in preparing ordered states is related to the interaction distance of the target state, which measures how close that state is to the manifold of all Gaussian states in an arbitrary basis of single-particle modes.We numerically verify this for several examples of nonintegrable quantum models, including Ising models with two-and three-spin interactions and the cluster model in an external field.Our results suggest that the structure of the entanglement spectrum, as witnessed by the interaction distance, correlates with the success of QAOA state preparation, and that this correlation also contains information about different phases present in the model.We conclude that the QAOA typically finds a solution that perturbs around the closest free-fermion state.
The quantum approximate optimization algorithm (QAOA) has been proposed as a method to obtain approximate solutions for combinatorial optimization tasks. In this work, we study the underlying algebraic properties of three QAOA ansätze for the maximum-cut problem on connected graphs, while focusing on the generated Lie algebras as well as their invariant subspaces. Specifically, we analyze the standard QAOA ansatz as well as the orbit and multiangle ansätze. We are able to fully characterize the Lie algebras of the multiangle ansatz across arbitrary connected graphs, finding that they only fall into one of just six families. Aside from the cycle and path graphs, the Lie dimensions for every graph are exponentially large in the system size, meaning that multiangle ansätze are extremely prone to exhibiting barren plateaus. Then, a similar quasi-graph-independent Lie-algebraic characterization beyond the multiangle ansatz is impeded as the circuit exhibits additional “hidden” symmetries besides those naturally arising from a certain parity-superselection operator and all automorphisms of the considered graph. Disregarding the “hidden” symmetries, we can upper bound the dimensions of the orbit and the standard Lie algebras, and the dimensions of the associated invariant subspaces are determined via explicit character formulas. To finish, we conjecture that (for most graphs) the standard Lie algebras have only components that are either exponential or that grow, at most, polynomially with the system size. This would imply that the QAOA is either prone to barren plateaus or classically simulable. More generally, our work provides a symmetry framework and tools to analyze any desired variational quantum algorithm.
Efficient preparation of arbitrary entangled quantum states is crucial for quantum computation. This is particularly important for noisy intermediate-scale quantum simulators relying on variational hybrid quantum-classical algorithms. To that end, we propose symmetry-conserving modified quantum approximate optimization algorithm (SCom-QAOA) circuits. The depths of these circuits depend not only on the desired fidelity to the target state but also on the amount of entanglement the state contains. The parameters of the SCom-QAOA circuits are optimized using the quantum natural gradient method based on the Fubini-Study metric. The SCom-QAOA circuit transforms an unentangled state into a ground state of a gapped one-dimensional Hamiltonian with a circuit depth that depends not on the system size but rather on the finite correlation length. In contrast, the circuit depth grows proportionally to the system size for preparing low-lying states of critical one-dimensional systems. Even in the latter case, SCom-QAOA circuits with depth less than the system size were sufficient to generate states with fidelity in excess of 99%, which is relevant for near-term applications. The proposed scheme enlarges the set of the initial states accessible for variational quantum algorithms and widens the scope of investigation of nonequilibrium phenomena in quantum simulators. Published by the American Physical Society 2024
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 Quantum Approximate Optimization Algorithm (QAOA) is an extensively studied variational quantum algorithm utilized for solving optimization problems on near-term quantum devices. A significant focus is placed on determining the effectiveness of training the nnn-qubit QAOA circuit, i.e., whether the optimization error can converge to a constant level as the number of optimization iterations scales polynomially with the number of qubits. In realistic scenarios, the landscape of the corresponding QAOA objective function is generally non-convex and contains numerous local optima. In this work, motivated by the favorable performance of Bayesian optimization in handling non-convex functions, we theoretically investigate the trainability of the QAOA circuit through the lens of the Bayesian approach. This lens considers the corresponding QAOA objective function as a sample drawn from a specific Gaussian process. Specifically, we focus on two scenarios: the noiseless QAOA circuit and the noisy QAOA circuit subjected to local Pauli channels. Our first result demonstrates that the noiseless QAOA circuit with a depth of O~(log⁡n)\tilde{\mathcal{O}}\left(\sqrt{\log n}\right)O~(logn​) can be trained efficiently, based on the widely accepted assumption that either the left or right slice of each block in the circuit forms a local 1-design. Furthermore, we show that if each quantum gate is affected by a qqq-strength local Pauli channel with the noise strength range of 1/poly(n)1/{\rm poly} (n)1/poly(n) to 0.1, the noisy QAOA circuit with a depth of O(log⁡n/log⁡(1/q))\mathcal{O}\left(\log n/\log(1/q)\right)O(logn/log(1/q)) can also be trained efficiently. Our results offer valuable insights into the theoretical performance of quantum optimization algorithms in the noisy intermediate-scale quantum era.
Dynamical Lie algebras (DLAs) have emerged as a valuable tool in the study of parameterized quantum circuits, helping to characterize both their expressiveness and trainability. In particular, the absence or presence of barren plateaus (BPs) – flat regions in parameter space that prevent the efficient training of variational quantum algorithms – has recently been shown to be intimately related to quantities derived from the associated DLA.In this work, we investigate DLAs for the quantum approximate optimization algorithm (QAOA), one of the most studied variational quantum algorithms for solving graph MaxCut and other combinatorial optimization problems. While DLAs for QAOA circuits have been studied before, existing results have either been based on numerical evidence, or else correspond to DLA generators specifically chosen to be universal for quantum computation on a subspace of states. We initiate an analytical study of barren plateaus and other statistics of QAOA algorithms, and give bounds on the dimensions of the corresponding DLAs and their centers for general graphs. We then focus on the n -vertex cycle and complete graphs. For the cycle graph we give an explicit basis, identify its decomposition into the direct sum of a 2 -dimensional center and a semisimple component isomorphic to n − 1 copies of s u ( 2 ) . We give an explicit basis for this isomorphism, and a closed-form expression for the variance of the cost function, proving the absence of BPs. For the complete graph we prove that the dimension of the DLA is O ( n 3 ) and give an explicit basis for the DLA.