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

An Adaptive Mixer Allocation Algorithm for the Quantum Alternating Operator Ansatz

Xiao‐Hui Ni, Yusen Wu, Bin‐Bin Cai, Wenmin Li, Su‐Juan Qin, Fei Gao

Published Dec 27, 2024• 0 citations
arXivHTMLPDF

Abstract

Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA-QAOA+. Unlike QAOA+, AMA-QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA-QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA-QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by $5.30\%$ on ER random graphs and $5.41\%$ on 3-regular graphs. Moreover, AMA-QAOA+ significantly reduces the CNOT gate consumption, requiring only $15.30\%$ and $25.18\%$ of the CNOT gates used by QAOA+ on ER and 3-regular random graphs, respectively. These results demonstrate that AMA-QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource-efficient quantum circuits.

DOI
10.48550/arxiv.2412.19621

Related papers

An Adaptive Mixer Allocation Strategy for the Quantum Alternating Operator Ansatz

Xiao‐Hui Ni, Yusen Wu, Bin‐Bin Cai +3 more

ABSTRACT Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA‐QAOA+. Unlike QAOA+, AMA‐QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA‐QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA‐QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by on Erdős–Rényi random graphs and on 3‐regular graphs. Moreover, AMA‐QAOA+ significantly reduces the CNOT gate consumption, requiring only and of the CNOT gates used by QAOA+ on Erdős–Rényi and 3‐regular random graphs, respectively. These results demonstrate that AMA‐QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource‐efficient quantum circuits.

Advanced Quantum Technologies•Nov 23, 2025•0 citations

Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz

Xiao‐Hui Ni, Lingxiao Li, Yan-Qi Song +3 more

Hadfield et al. proposed a novel Quantum Alternating Operator Ansatz algorithm (QAOA+), and this algorithm has wide applications in solving constrained combinatorial optimization problems (CCOPs) because of the advantages of QAOA+ ansatz in constructing a feasible solution space. In this paper, we propose a Progressive Quantum Algorithm (PQA) with QAOA+ ansatz to solve the Maximum Independent Set (MIS) problem using fewer qubits. The core idea of PQA is to construct a subgraph that is likely to contain the MIS solution of the target graph and then solve the MIS problem on this subgraph to obtain an approximate solution. To construct such a subgraph, PQA starts with a small-scale initial subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results demonstrate that to achieve an approximation ratio of 0.95, PQA requires only $5.565\%$ ($2.170\%$) of the qubits and $17.59\%$ ($6.430\%$) of the runtime compared with directly solving the original problem using QAOA+ on Erdős-Rényi (3-regular) graphs, highlighting the efficiency of PQA.

arXiv:2405.04303•May 7, 2024•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 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

Progressive quantum algorithm for maximum independent set with quantum alternating operator ansatz

Xiao‐Hui Ni, Ling-Xiao 凌霄 Li 李, Yanqi Song +3 more

Abstract The quantum alternating operator ansatz algorithm (QAOA+) is widely used for constrained combinatorial optimization problems (CCOPs) due to its ability to construct feasible solution spaces. In this paper, we propose a progressive quantum algorithm (PQA) to reduce qubit requirements for QAOA+ in solving the maximum independent set (MIS) problem. PQA iteratively constructs a subgraph likely to include the MIS solution of the original graph and solves the problem on it to approximate the global solution. Specifically, PQA starts with a small-scale subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph using QAOA+. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results show that PQA achieves an approximation ratio of 0.95 using only 5.57% (2.17%) of the qubits and 17.59% (6.43%) of the runtime compared with directly solving the original problem with QAOA+ on Erdös–Rényi (3-regular) graphs, highlighting the efficiency and scalability of PQA.

Chinese Physics B•May 28, 2025•1 citation

The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover

Jeremy Cook, Stephan Eidenbenz, Andreas Bärtschi

The Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm (QAOA) designed for finding approximate solutions to combinatorial optimization problems with hard constraints. In this paper, we study Maximum k-Vertex Cover under this ansatz due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max E3-LIN2. Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states as starting states, (ii) a performance comparison between two XY-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies. Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) numerical results indicating the standard deviation of the distribution of solutions decreases exponentially in$p$(the number of rounds in the algorithm), requiring an exponential number of random samples to find a better solution in the next round, and (v) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.

arXiv:1910.13483•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2020•73 citations
Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA-QAOA+. Unlike QAOA+, AMA-QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA-QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA-QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by 5.30%5.30\%5.30% on ER random graphs and 5.41%5.41\%5.41% on 3-regular graphs. Moreover, AMA-QAOA+ significantly reduces the CNOT gate consumption, requiring only 15.30%15.30\%15.30% and 25.18%25.18\%25.18% of the CNOT gates used by QAOA+ on ER and 3-regular random graphs, respectively. These results demonstrate that AMA-QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource-efficient quantum circuits.
ABSTRACT Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA‐QAOA+. Unlike QAOA+, AMA‐QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA‐QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA‐QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by on Erdős–Rényi random graphs and on 3‐regular graphs. Moreover, AMA‐QAOA+ significantly reduces the CNOT gate consumption, requiring only and of the CNOT gates used by QAOA+ on Erdős–Rényi and 3‐regular random graphs, respectively. These results demonstrate that AMA‐QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource‐efficient quantum circuits.
Hadfield et al. proposed a novel Quantum Alternating Operator Ansatz algorithm (QAOA+), and this algorithm has wide applications in solving constrained combinatorial optimization problems (CCOPs) because of the advantages of QAOA+ ansatz in constructing a feasible solution space. In this paper, we propose a Progressive Quantum Algorithm (PQA) with QAOA+ ansatz to solve the Maximum Independent Set (MIS) problem using fewer qubits. The core idea of PQA is to construct a subgraph that is likely to contain the MIS solution of the target graph and then solve the MIS problem on this subgraph to obtain an approximate solution. To construct such a subgraph, PQA starts with a small-scale initial subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results demonstrate that to achieve an approximation ratio of 0.95, PQA requires only 5.565%5.565\%5.565% (2.170%2.170\%2.170%) of the qubits and 17.59%17.59\%17.59% (6.430%6.430\%6.430%) of the runtime compared with directly solving the original problem using QAOA+ on Erdős-Rényi (3-regular) graphs, highlighting the efficiency of PQA.
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.
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.
Abstract The quantum alternating operator ansatz algorithm (QAOA+) is widely used for constrained combinatorial optimization problems (CCOPs) due to its ability to construct feasible solution spaces. In this paper, we propose a progressive quantum algorithm (PQA) to reduce qubit requirements for QAOA+ in solving the maximum independent set (MIS) problem. PQA iteratively constructs a subgraph likely to include the MIS solution of the original graph and solves the problem on it to approximate the global solution. Specifically, PQA starts with a small-scale subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph using QAOA+. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results show that PQA achieves an approximation ratio of 0.95 using only 5.57% (2.17%) of the qubits and 17.59% (6.43%) of the runtime compared with directly solving the original problem with QAOA+ on Erdös–Rényi (3-regular) graphs, highlighting the efficiency and scalability of PQA.
The Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm (QAOA) designed for finding approximate solutions to combinatorial optimization problems with hard constraints. In this paper, we study Maximum k-Vertex Cover under this ansatz due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max E3-LIN2. Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states as starting states, (ii) a performance comparison between two XY-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies. Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) numerical results indicating the standard deviation of the distribution of solutions decreases exponentially inppp(the number of rounds in the algorithm), requiring an exponential number of random samples to find a better solution in the next round, and (v) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.