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:2510.05576 · Physical review. E

Quantum approximate optimization of finite-state bosonic systems

Shakib Daryanoosh

Published Jan 30, 2026• 1 citation
arXivHTMLPDF

Abstract

There exist numerous problems in nature inherently described by finite D-dimensional states. Formulating these problems for execution on qubit-based quantum hardware requires mapping the qudit Hilbert space to that of multiqubit which may be exponentially larger. To exclude the infeasible subspace, one common approach relies on penalizing the objective function. However, this strategy can be inefficient as the size of the illegitimate subspace grows. Here we propose to employ the Hamiltonian-based quantum approximate optimization algorithm (QAOA) through devising appropriate mixing Hamiltonians such that the infeasible configuration space is ruled out. We investigate this idea by employing binary, symmetric, and unary mapping techniques. It is shown that the standard mixing Hamiltonian (sum of the bit-flip operations) is the optimal option within the standard universal gate set for symmetric mapping, where the controlled-NOT gate count is used as a measure of implementation cost. In contrast, the other two encoding schemes witness a p-fold increase in this figure for a p-layer QAOA. We apply this framework to quantum approximate thermalization and find the ground state of the repulsive Bose-Hubbard model in the strong and weak interaction regimes.

DOI
10.1103/yg66-8ypn

Related papers

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.

arXiv:2405.07211•IEEE Transactions on Quantum Engineering•Jan 1, 2026•10 citations

Quantum approximate optimization algorithm for qudit systems

Yannick Deller, Sebastian Schmitt, Maciej Lewenstein +5 more

A frequent starting point of quantum computation platforms is the two-state quantum system, i.e., the qubit. However, in the context of integer optimization problems, relevant to scheduling optimization and operations research, it is often more resource-efficient to employ quantum systems with more than two basis states, so-called qudits. Here, we discuss the quantum approximate optimization algorithm (QAOA) for qudit systems. We illustrate how the QAOA can be used to formulate a variety of integer optimization problems such as graph coloring problems or electric vehicle charging optimization. In addition, we comment on the implementation of constraints and describe three methods to include these in a quantum circuit of a QAOA by penalty contributions to the cost Hamiltonian, conditional gates using ancilla qubits, and a dynamical decoupling strategy. Finally, as a showcase of qudit-based QAOA, we present numerical results for a charging optimization problem mapped onto a maximum-$k$-graph-coloring problem. Our work illustrates the flexibility of qudit systems to solve integer optimization problems.

arXiv:2204.00340•Physical Review A•Jun 9, 2023•48 citations

From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

Stuart Hadfield, Zhihui Wang, Bryan O’Gorman +3 more

The next few years will be exciting as prototype universal quantum processors emerge, enabling the implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation and which have the potential to significantly expand the breadth of applications for which quantum computers have an established advantage. A leading candidate is Farhi et al.’s quantum approximate optimization algorithm, which alternates between applying a cost function based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the quantum alternating operator ansatz, is the consideration of general parameterized families of unitaries rather than only those corresponding to the time evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. More efficient implementation enables earlier experimental exploration of an alternating operator approach, in the spirit of the quantum approximate optimization algorithm, to a wide variety of approximate optimization, exact optimization, and sampling problems. In addition to introducing the quantum alternating operator ansatz, we lay out design criteria for mixing operators, detail mappings for eight problems, and provide a compendium with brief descriptions of mappings for a diverse array of problems.

arXiv:1709.03489•Algorithms•Feb 12, 2019•952 citations

Quantum Approximate Optimization Algorithm with Sparsified Phase Operator

Xiaoyuan Liu, Ruslan Shaydulin, Ilya Safro

The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate algorithm for demonstrating quantum advantage in optimization using near-term quantum computers. However, QAOA has high requirements on gate fidelity due to the need to encode the objective function in the phase separating operator, requiring a large number of gates that potentially do not match the hardware connectivity. Using the MaxCut problem as the target, we demonstrate numerically that an easier way to implement an alternative phase operator can be used in lieu of the phase operator encoding the objective function, as long as the ground state is the same. We observe that if the ground state energy is not preserved, the approximation ratio obtained by QAOA with such phase separating operator is likely to decrease. Moreover, we show that a better alignment of the low energy subspace of the alternative operator leads to better performance. Leveraging these observations, we propose a sparsification strategy that reduces the resource requirements of QAOA. We also compare our sparsification strategy with some other classical graph sparsification methods, and demonstrate the efficacy of our approach.

arXiv:2205.00118•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•7 citations

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•82 citations

A SWAP-free Framework for QAOA

Thiago Assis, Pedro Baptista, Laila Lopes +2 more

The performance of the Quantum Approximate Optimization Algorithm (QAOA) on noisy intermediate-scale quantum (NISQ) devices is strongly limited by sparse qubit connectivity. When interactions required by QAOA Hamiltonians are not aligned to the hardware topology, transpilation introduces SWAP gates, increasing circuit depth and noise. We propose a SWAP-free QAOA framework based on modifying the cost Hamiltonian so that it can be implemented natively on the hardware. We formulate this as a mixed-integer semidefinite program (MISDP) that selects a hardware-compatible approximation of the original cost matrix and optimizes the allocation of logical variables to physical qubits. We prove that the associated decision problem is NP-complete and derive theoretical guarantees relating the MISDP objective to the loss in the original optimization problem through the Lovász number of the hardware graph. Since solving MISDPs is practical only for small instances, we introduce heuristics based on spectral properties of the problem matrix and hardware graph. Our experiments on a cardinality-constrained quadratic optimization model for index tracking show competitive performance against a baseline representing ideal QAOA under SWAP-induced noise. These results indicate that, on sparse NISQ architectures, a hardware-aware approximation of the objective may be more effective than an exact but heavily transpiled Hamiltonian implementation.

quant-pharXiv:2604.25058•Apr 29, 2026•0 citations
There exist numerous problems in nature inherently described by finite D-dimensional states. Formulating these problems for execution on qubit-based quantum hardware requires mapping the qudit Hilbert space to that of multiqubit which may be exponentially larger. To exclude the infeasible subspace, one common approach relies on penalizing the objective function. However, this strategy can be inefficient as the size of the illegitimate subspace grows. Here we propose to employ the Hamiltonian-based quantum approximate optimization algorithm (QAOA) through devising appropriate mixing Hamiltonians such that the infeasible configuration space is ruled out. We investigate this idea by employing binary, symmetric, and unary mapping techniques. It is shown that the standard mixing Hamiltonian (sum of the bit-flip operations) is the optimal option within the standard universal gate set for symmetric mapping, where the controlled-NOT gate count is used as a measure of implementation cost. In contrast, the other two encoding schemes witness a p-fold increase in this figure for a p-layer QAOA. We apply this framework to quantum approximate thermalization and find the ground state of the repulsive Bose-Hubbard model in the strong and weak interaction regimes.
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.
A frequent starting point of quantum computation platforms is the two-state quantum system, i.e., the qubit. However, in the context of integer optimization problems, relevant to scheduling optimization and operations research, it is often more resource-efficient to employ quantum systems with more than two basis states, so-called qudits. Here, we discuss the quantum approximate optimization algorithm (QAOA) for qudit systems. We illustrate how the QAOA can be used to formulate a variety of integer optimization problems such as graph coloring problems or electric vehicle charging optimization. In addition, we comment on the implementation of constraints and describe three methods to include these in a quantum circuit of a QAOA by penalty contributions to the cost Hamiltonian, conditional gates using ancilla qubits, and a dynamical decoupling strategy. Finally, as a showcase of qudit-based QAOA, we present numerical results for a charging optimization problem mapped onto a maximum-kkk-graph-coloring problem. Our work illustrates the flexibility of qudit systems to solve integer optimization problems.
The next few years will be exciting as prototype universal quantum processors emerge, enabling the implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation and which have the potential to significantly expand the breadth of applications for which quantum computers have an established advantage. A leading candidate is Farhi et al.’s quantum approximate optimization algorithm, which alternates between applying a cost function based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the quantum alternating operator ansatz, is the consideration of general parameterized families of unitaries rather than only those corresponding to the time evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. More efficient implementation enables earlier experimental exploration of an alternating operator approach, in the spirit of the quantum approximate optimization algorithm, to a wide variety of approximate optimization, exact optimization, and sampling problems. In addition to introducing the quantum alternating operator ansatz, we lay out design criteria for mixing operators, detail mappings for eight problems, and provide a compendium with brief descriptions of mappings for a diverse array of problems.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate algorithm for demonstrating quantum advantage in optimization using near-term quantum computers. However, QAOA has high requirements on gate fidelity due to the need to encode the objective function in the phase separating operator, requiring a large number of gates that potentially do not match the hardware connectivity. Using the MaxCut problem as the target, we demonstrate numerically that an easier way to implement an alternative phase operator can be used in lieu of the phase operator encoding the objective function, as long as the ground state is the same. We observe that if the ground state energy is not preserved, the approximation ratio obtained by QAOA with such phase separating operator is likely to decrease. Moreover, we show that a better alignment of the low energy subspace of the alternative operator leads to better performance. Leveraging these observations, we propose a sparsification strategy that reduces the resource requirements of QAOA. We also compare our sparsification strategy with some other classical graph sparsification methods, and demonstrate the efficacy of our approach.
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 performance of the Quantum Approximate Optimization Algorithm (QAOA) on noisy intermediate-scale quantum (NISQ) devices is strongly limited by sparse qubit connectivity. When interactions required by QAOA Hamiltonians are not aligned to the hardware topology, transpilation introduces SWAP gates, increasing circuit depth and noise. We propose a SWAP-free QAOA framework based on modifying the cost Hamiltonian so that it can be implemented natively on the hardware. We formulate this as a mixed-integer semidefinite program (MISDP) that selects a hardware-compatible approximation of the original cost matrix and optimizes the allocation of logical variables to physical qubits. We prove that the associated decision problem is NP-complete and derive theoretical guarantees relating the MISDP objective to the loss in the original optimization problem through the Lovász number of the hardware graph. Since solving MISDPs is practical only for small instances, we introduce heuristics based on spectral properties of the problem matrix and hardware graph. Our experiments on a cardinality-constrained quadratic optimization model for index tracking show competitive performance against a baseline representing ideal QAOA under SWAP-induced noise. These results indicate that, on sparse NISQ architectures, a hardware-aware approximation of the objective may be more effective than an exact but heavily transpiled Hamiltonian implementation.