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

LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism

Franz Georg Fuchs, Ruben Pariente Bassa

Published Nov 25, 2024• 4 citations
arXivHTMLPDF

Abstract

We present a novel formalism to both understand and construct mixers that preserve a given subspace. The method connects and utilizes the stabilizer formalism that is used in error correcting codes. This can be useful in the setting when the quantum approximate optimization algorithm (QAOA), a popular meta-heuristic for solving combinatorial optimization problems, is applied in the setting where the constraints of the problem lead to a feasible subspace that is large but easy to specify. The proposed method gives a systematic way to construct mixers that are resource efficient in the number of controlled not gates and can be understood as a generalization of the well-known X and XY mixers and a relaxation of the Grover mixer: Given a basis of any subspace, a resource efficient mixer can be constructed that preserves the subspace. The numerical examples provided show a dramatic reduction of CX gates when compared to previous results. We call our approach logical X-Mixer or logical X QAOA ( LX-QAOA ), since it can be understood as dividing the subspace into code spaces of stabilizers S and consecutively applying logical rotational X gates associated with these code spaces. Overall, we hope that this new perspective can lead to further insight into the development of quantum algorithms.

DOI
10.22331/q-2024-11-25-1535

Related papers

Constraint Preserving Mixers for the Quantum Approximate Optimization Algorithm

Franz Georg Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen +2 more

The quantum approximate optimization algorithm/quantum alternating operator ansatz (QAOA) is a heuristic to find approximate solutions of combinatorial optimization problems. Most of the literature is limited to quadratic problems without constraints. However, many practically relevant optimization problems do have (hard) constraints that need to be fulfilled. In this article, we present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space given by these constraints. We generalize the “XY”-mixer designed to preserve the subspace of “one-hot” states to the general case of subspaces given by a number of computational basis states. We expose the underlying mathematical structure which reveals more of how mixers work and how one can minimize their cost in terms of the number of CX gates, particularly when Trotterization is taken into account. Our analysis also leads to valid Trotterizations for an “XY”-mixer with fewer CX gates than is known to date. In view of practical implementations, we also describe algorithms for efficient decomposition into basis gates. Several examples of more general cases are presented and analyzed.

arXiv:2203.06095•Algorithms•Jun 10, 2022•47 citations

Design and Analysis of an Improved Constrained Hypercube Mixer in Quantum Approximate Optimization Algorithm

Arkadiusz Wołk, Karol Capała, Katarzyna Rycerz

The Quantum Approximate Optimization Algorithm (QAOA) is expected to offer advantages over classical approaches when solving combinatorial optimization problems in the Noisy Intermediate-Scale Quantum (NISQ) era. In its standard formulation, however, QAOA is not suited for constrained problems. One way to incorporate certain types of constraints is to restrict the mixing operator to the feasible subspace; however, this substantially increases circuit size, thereby reducing noise robustness. In this work, we refine an existing hypercube mixer method for enforcing hard constraints in QAOA. We present a modification that generates circuits with fewer gates for a broad class of constrained problems defined by linear functions. Furthermore, we calculate an analytical upper bound on the number of binary variables for which this reduction might not apply. Additionally, we present numerical experimental results demonstrating that the proposed approach improves robustness to noise. In summary, the method proposed in this paper allows for more accurate QAOA performance in noisy settings, bringing us closer to practical, real-world NISQ-era applications.

quant-pharXiv:2603.05187•Information Sciences•Mar 6, 2026•0 citations

XY vs X mixer in Quantum Alternating Operator Ansatz for optimization problems with constraints

Zhihui Wang, Nicholas C. Rubin, Eleanor Gilbert Rieffel

Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.

Bulletin of the American Physical Society•Mar 8, 2018•0 citations

XY mixers: Analytical and numerical results for the quantum alternating operator ansatz

Zhihui Wang, Nicholas C. Rubin, Jason Dominy +1 more

The quantum alternating operator ansatz (QAOA) is a promising gate-model metaheuristic for combinatorial optimization. Applying the algorithm to problems with constraints presents an implementation challenge for near-term quantum resources. This paper explores strategies for enforcing hard constraints by using $XY$ Hamiltonians as mixing operators (mixers). Despite the complexity of simulating the $XY$ model, we demonstrate that, for an integer variable admitting $\ensuremath{\kappa}$ discrete values represented through one-hot encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O(\ensuremath{\kappa})$. We also specify general strategies for implementing QAOA circuits on all-to-all connected hardware graphs and linearly connected hardware graphs inspired by fermionic simulation techniques. Performance is validated on graph-coloring problems that are known to be challenging for a given classical algorithm. The general strategy of using $XY$ mixers is borne out numerically, demonstrating a significant improvement over the general $X$ mixer, and moreover the generalized $W$ state yields better performance than easier-to-generate classical initial states when $XY$ mixers are used.

arXiv:1904.09314•Physical Review A•Jan 14, 2020•189 citations

XY-mixer ansatz assisted by counterdiabatic driving for combinational optimization

Yue Ruan, Pengyue Chen, Qi Li +5 more

XY mixer are a type of mixing Hamiltonians used in the quantum alternating operator ansatzs (QAOA) framework for solving combinatorial optimization problems where the feasible subspace consists of states with the same Hamming weight. In this paper, we propose an extension of the XY-mixer ansatzes to solve optimization problems that do not adhere to this specific subspace structure. For problems, such as maximal independent set, one can employ positive semidefinite programming and a greedy algorithm to obtain upper and lower bounds for the optimal solution, then utilize the XY-mixer ansatzes in the separated subspaces between the upper and lower bounds to address the problem at hand. Additionally, we find suitable counterdiabatic (CD) driving terms that complement the XY-mixer ansatzes. These driving terms accelerate the QAOA evolution towards the target state and also confine the evolution within the subspace. By combining XY-mixer ansatzes with counterdiabatic driving (XY-CD mixers), we present a generalized QAOA-based scheme for finding higher-quality approximate solutions to combinatorial problems.

Physical Review Research•Mar 6, 2025•0 citations

Equivariant Quantum Approximate Optimization Algorithm

Boris Tsvelikhovskiy, Ilya Safro, Yuri Alexeev

Constructing effective mixer Hamiltonians is essential for enhancing the performance of the Quantum Approximate Optimization Algorithm (QAOA) in solving combinatorial optimization problems. In this work, we develop a systematic methodology for designing QAOA mixers that align with the symmetries of the classical objective function, with the goal of achieving values (mean, median, and minimum over multiple runs) that are closer to the true optimum. Our main idea is to design QAOA operators that are explicitly adapted to the action of symmetry groups on the Hilbert space. We focus on subgroups of the symmetric group$ S_{d}$, where$ d = 2^\ell$, to ensure compatibility with qudit-based quantum architectures. In particular, we construct QAOA mixers invariant under the full symmetric group$ S_{d}$as well as its cyclic subgroup$ \mathbb {Z}_{d} \subset S_{d}$. These constructions are natural in that they respect the decomposition of the Hilbert space into isotypic components under the symmetry group action. Notably, to the best of our knowledge, the QAOA algorithm based on the$ \mathbb {Z}_{d}$-invariant mixer provides the first example of a QAOA protocol whose dynamics (up to final measurement) are confined entirely within a nontrivial irreducible representation of a symmetry group of the objective function. Although our work does not investigate the benefits of exploiting such subspaces as computational resources, we think that the very realization of a variational algorithm whose evolution is restricted to a nontrivial symmetry-adapted subspace is of fundamental conceptual interest. We provide closed-form expressions for these mixers, together with explicit quantum circuit implementations. To empirically evaluate our approach, we compare QAOA variants employing the standard mixer$B = \sum X_{i}$with those using our proposed Hamiltonians$H_{M}$and$H_\chi$on edge coloring and graph partitioning problems. Across multiple graph instances, our symmetry-adapted mixers consistently yield objective values closer to the optimum, demonstrating statistically significant improvements over classical baselines.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations
We present a novel formalism to both understand and construct mixers that preserve a given subspace. The method connects and utilizes the stabilizer formalism that is used in error correcting codes. This can be useful in the setting when the quantum approximate optimization algorithm (QAOA), a popular meta-heuristic for solving combinatorial optimization problems, is applied in the setting where the constraints of the problem lead to a feasible subspace that is large but easy to specify. The proposed method gives a systematic way to construct mixers that are resource efficient in the number of controlled not gates and can be understood as a generalization of the well-known X and XY mixers and a relaxation of the Grover mixer: Given a basis of any subspace, a resource efficient mixer can be constructed that preserves the subspace. The numerical examples provided show a dramatic reduction of CX gates when compared to previous results. We call our approach logical X-Mixer or logical X QAOA ( LX-QAOA ), since it can be understood as dividing the subspace into code spaces of stabilizers S and consecutively applying logical rotational X gates associated with these code spaces. Overall, we hope that this new perspective can lead to further insight into the development of quantum algorithms.
The quantum approximate optimization algorithm/quantum alternating operator ansatz (QAOA) is a heuristic to find approximate solutions of combinatorial optimization problems. Most of the literature is limited to quadratic problems without constraints. However, many practically relevant optimization problems do have (hard) constraints that need to be fulfilled. In this article, we present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space given by these constraints. We generalize the “XY”-mixer designed to preserve the subspace of “one-hot” states to the general case of subspaces given by a number of computational basis states. We expose the underlying mathematical structure which reveals more of how mixers work and how one can minimize their cost in terms of the number of CX gates, particularly when Trotterization is taken into account. Our analysis also leads to valid Trotterizations for an “XY”-mixer with fewer CX gates than is known to date. In view of practical implementations, we also describe algorithms for efficient decomposition into basis gates. Several examples of more general cases are presented and analyzed.
The Quantum Approximate Optimization Algorithm (QAOA) is expected to offer advantages over classical approaches when solving combinatorial optimization problems in the Noisy Intermediate-Scale Quantum (NISQ) era. In its standard formulation, however, QAOA is not suited for constrained problems. One way to incorporate certain types of constraints is to restrict the mixing operator to the feasible subspace; however, this substantially increases circuit size, thereby reducing noise robustness. In this work, we refine an existing hypercube mixer method for enforcing hard constraints in QAOA. We present a modification that generates circuits with fewer gates for a broad class of constrained problems defined by linear functions. Furthermore, we calculate an analytical upper bound on the number of binary variables for which this reduction might not apply. Additionally, we present numerical experimental results demonstrating that the proposed approach improves robustness to noise. In summary, the method proposed in this paper allows for more accurate QAOA performance in noisy settings, bringing us closer to practical, real-world NISQ-era applications.
Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.
The quantum alternating operator ansatz (QAOA) is a promising gate-model metaheuristic for combinatorial optimization. Applying the algorithm to problems with constraints presents an implementation challenge for near-term quantum resources. This paper explores strategies for enforcing hard constraints by using XYXYXY Hamiltonians as mixing operators (mixers). Despite the complexity of simulating the XYXYXY model, we demonstrate that, for an integer variable admitting $\ensuremath{\kappa}$ discrete values represented through one-hot encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O(\ensuremath{\kappa})$. We also specify general strategies for implementing QAOA circuits on all-to-all connected hardware graphs and linearly connected hardware graphs inspired by fermionic simulation techniques. Performance is validated on graph-coloring problems that are known to be challenging for a given classical algorithm. The general strategy of using XYXYXY mixers is borne out numerically, demonstrating a significant improvement over the general XXX mixer, and moreover the generalized WWW state yields better performance than easier-to-generate classical initial states when XYXYXY mixers are used.
XY mixer are a type of mixing Hamiltonians used in the quantum alternating operator ansatzs (QAOA) framework for solving combinatorial optimization problems where the feasible subspace consists of states with the same Hamming weight. In this paper, we propose an extension of the XY-mixer ansatzes to solve optimization problems that do not adhere to this specific subspace structure. For problems, such as maximal independent set, one can employ positive semidefinite programming and a greedy algorithm to obtain upper and lower bounds for the optimal solution, then utilize the XY-mixer ansatzes in the separated subspaces between the upper and lower bounds to address the problem at hand. Additionally, we find suitable counterdiabatic (CD) driving terms that complement the XY-mixer ansatzes. These driving terms accelerate the QAOA evolution towards the target state and also confine the evolution within the subspace. By combining XY-mixer ansatzes with counterdiabatic driving (XY-CD mixers), we present a generalized QAOA-based scheme for finding higher-quality approximate solutions to combinatorial problems.
Constructing effective mixer Hamiltonians is essential for enhancing the performance of the Quantum Approximate Optimization Algorithm (QAOA) in solving combinatorial optimization problems. In this work, we develop a systematic methodology for designing QAOA mixers that align with the symmetries of the classical objective function, with the goal of achieving values (mean, median, and minimum over multiple runs) that are closer to the true optimum. Our main idea is to design QAOA operators that are explicitly adapted to the action of symmetry groups on the Hilbert space. We focus on subgroups of the symmetric group$ S_{d},where, where,where d = 2^\ell,toensurecompatibilitywithqudit−basedquantumarchitectures.Inparticular,weconstructQAOAmixersinvariantunderthefullsymmetricgroup, to ensure compatibility with qudit-based quantum architectures. In particular, we construct QAOA mixers invariant under the full symmetric group,toensurecompatibilitywithqudit−basedquantumarchitectures.Inparticular,weconstructQAOAmixersinvariantunderthefullsymmetricgroup S_{d}aswellasitscyclicsubgroupas well as its cyclic subgroupaswellasitscyclicsubgroup \mathbb {Z}_{d} \subset S_{d}.TheseconstructionsarenaturalinthattheyrespectthedecompositionoftheHilbertspaceintoisotypiccomponentsunderthesymmetrygroupaction.Notably,tothebestofourknowledge,theQAOAalgorithmbasedonthe. These constructions are natural in that they respect the decomposition of the Hilbert space into isotypic components under the symmetry group action. Notably, to the best of our knowledge, the QAOA algorithm based on the.TheseconstructionsarenaturalinthattheyrespectthedecompositionoftheHilbertspaceintoisotypiccomponentsunderthesymmetrygroupaction.Notably,tothebestofourknowledge,theQAOAalgorithmbasedonthe \mathbb {Z}_{d}−invariantmixerprovidesthefirstexampleofaQAOAprotocolwhosedynamics(uptofinalmeasurement)areconfinedentirelywithinanontrivialirreduciblerepresentationofasymmetrygroupoftheobjectivefunction.Althoughourworkdoesnotinvestigatethebenefitsofexploitingsuchsubspacesascomputationalresources,wethinkthattheveryrealizationofavariationalalgorithmwhoseevolutionisrestrictedtoanontrivialsymmetry−adaptedsubspaceisoffundamentalconceptualinterest.Weprovideclosed−formexpressionsforthesemixers,togetherwithexplicitquantumcircuitimplementations.Toempiricallyevaluateourapproach,wecompareQAOAvariantsemployingthestandardmixer-invariant mixer provides the first example of a QAOA protocol whose dynamics (up to final measurement) are confined entirely within a nontrivial irreducible representation of a symmetry group of the objective function. Although our work does not investigate the benefits of exploiting such subspaces as computational resources, we think that the very realization of a variational algorithm whose evolution is restricted to a nontrivial symmetry-adapted subspace is of fundamental conceptual interest. We provide closed-form expressions for these mixers, together with explicit quantum circuit implementations. To empirically evaluate our approach, we compare QAOA variants employing the standard mixer−invariantmixerprovidesthefirstexampleofaQAOAprotocolwhosedynamics(uptofinalmeasurement)areconfinedentirelywithinanontrivialirreduciblerepresentationofasymmetrygroupoftheobjectivefunction.Althoughourworkdoesnotinvestigatethebenefitsofexploitingsuchsubspacesascomputationalresources,wethinkthattheveryrealizationofavariationalalgorithmwhoseevolutionisrestrictedtoanontrivialsymmetry−adaptedsubspaceisoffundamentalconceptualinterest.Weprovideclosed−formexpressionsforthesemixers,togetherwithexplicitquantumcircuitimplementations.Toempiricallyevaluateourapproach,wecompareQAOAvariantsemployingthestandardmixerB = \sum X_{i}withthoseusingourproposedHamiltonianswith those using our proposed HamiltonianswiththoseusingourproposedHamiltoniansH_{M}andandandH_\chi$on edge coloring and graph partitioning problems. Across multiple graph instances, our symmetry-adapted mixers consistently yield objective values closer to the optimum, demonstrating statistically significant improvements over classical baselines.