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

Constraint-Preserving QAOA for Personnel Rostering: Coverage-Preserving and Guarded-XY Mixer Constructions

Aruna Gupta, S R Hassan

quant-phSubmitted Jul 10, 2026• Announced Jul 13, 2026• 0 citations
v1 · Jul 10, 2026v2 · Aug 3, 2026
arXivHTMLPDF

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a promising framework for combinatorial optimization, but constrained problems are commonly handled using energetic penalty terms that require calibration and allow infeasible configurations to remain dynamically accessible. We develop a constraint-preserving QAOA framework for personnel rostering in which hard scheduling constraints are embedded directly into the mixer Hamiltonian. Using a binary rostering model with daily coverage and no-consecutive-duty constraints, we formulate the dynamics from a transition-graph perspective and introduce a guarded-XY mixer that confines the evolution to the fully feasible scheduling manifold. We further distinguish feasibility preservation from feasible-transition design and propose a tight-pattern extension that introduces collective feasible exchanges in saturated workload segments where local guarded exchanges alone are insufficient. Exact statevector simulations demonstrate that, compared with Penalty-X and Coverage-XY formulations under both expectation-value and Conditional Value-at-Risk optimization, the proposed approach eliminates hard-constraint penalty calibration, guarantees feasible evolution by construction, and consistently yields higher-quality output distributions with stronger concentration on optimal feasible schedules. To the best of our knowledge, this is the first constraint-preserving QAOA formulation for personnel rostering, and the transition-graph framework is readily applicable to a broad class of constrained quantum optimization problems.

Related papers

Constrained Portfolio Optimization via Quantum Approximate Optimization Algorithm (QAOA) with XY-Mixers and Trotterized Initialization: A Hybrid Approach for Direct Indexing

Javier Mancilla, Theodoros D. Bouloumis, Frederic Goguikian

Portfolio optimization under strict cardinality constraints is a combinatorial challenge that defies classical convex optimization techniques, particularly in the context of "Direct Indexing" and ESG-constrained mandates. In the Noisy Intermediate-Scale Quantum (NISQ) era, the Quantum Approximate Optimization Algorithm (QAOA) offers a promising hybrid approach. However, standard QAOA implementations utilizing transverse field mixers often fail to strictly enforce hard constraints, necessitating soft penalties that distort the energy landscape. This paper presents a comprehensive analysis of a constraint-preserving QAOA formulation against Simulated Annealing (SA) and Hierarchical Risk Parity (HRP). We implement a specific QAOA ansatz utilizing a Dicke state initialization and an XY-mixer Hamiltonian that strictly preserves the Hamming weight of the solution, ensuring only valid portfolios of size K are explored. Furthermore, we introduce a Trotterized parameter initialization schedule inspired by adiabatic quantum computing to mitigate the "Barren Plateau" problem. Backtesting on a basket of 10 US equities over 2025 reveals that our QAOA approach achieves a Sharpe Ratio of 1.81, significantly outperforming Simulated Annealing (1.31) and HRP (0.98). We further analyze the operational implications of the algorithm's high turnover (76.8%), discussing the trade-offs between theoretical optimality and implementation costs in institutional settings.

quant-pharXiv:2602.14827•Feb 17, 2026•0 citations

Constrained Counterdiabatic Quantum Approximate Optimization Algorithm for Portfolio Optimization

Jose Falla, Ilya Safro

We introduce a counterdiabatic (CD) extension of the Quantum Approximate Optimization Algorithm (QAOA) for constrained portfolio optimization. By incorporating approximate adiabatic gauge potentials generated from nested commutators of the Ising-type portfolio problem Hamiltonian and the Hamming weight-preserving XY mixer Hamiltonian into our variational ansatz, the resulting Constrained Counterdiabatic QAOA (CCD-QAOA) achieves improved optimization performance under realistic budget and risk constraints. Benchmarking against standard XY-mixer QAOA, Grover-mixer QAOA, and penalty-based QAOA formulations, our numerical simulations demonstrate that, for a fixed QAOA depth, our CCD-QAOA approach consistently results in better approximation ratios.

quant-pharXiv:2605.06858•May 11, 2026•0 citations

Warm-Starting QAOA With XY Mixers: A Novel Approach for Traveling Salesman Problem

Rafael Simões do Carmo, Marcos Cleison Silva Santana, F. F. Fanchini +2 more

Quantum optimization algorithms, such as the Quantum Approximate Optimization Algorithm, are emerging as promising heuristics for solving complex combinatorial problems. To improve performance, several extensions to the standard QAOA framework have been proposed in recent years. Two notable directions include: warm-starting techniques, which incorporate classical approximate solutions to guide the quantum evolution, and custom mixer Hamiltonians, such as XY mixers, which constrain the search to feasible subspaces aligned with the structure of the problem. In this work, we propose an approach that integrates these two strategies: a warm-start initialization with an XY mixer ansatz, enabling constraint-preserving quantum evolution biased toward high-quality classical solutions. The method begins by reformulating the combinatorial problem as a MaxCut instance, solved approximately using the Goemans-Williamson algorithm. The resulting binary solution is relaxed and used to construct a biased superposition over valid one-hot quantum states, maintaining compatibility with the XY mixer's constraints. We evaluate the approach on 5-city instances of the Traveling Salesperson Problem, a canonical optimization problem frequently encountered as a subroutine in real-world Vehicle Routing Problems. Our method is benchmarked against both the standard XY-mixer QAOA and a warm-start-only variant based on MaxCut relaxation. Results show that the proposed combination consistently outperforms both baselines in terms of the percentage and rank of optimal solutions, demonstrating the effectiveness of combining structured initializations with constraint-aware quantum evolution for optimization problems.

arXiv:2504.19934•IEEE Transactions on Intelligent Transportation Systems•Jan 1, 2026•0 citations

Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers

David Bucher, Maximilian Janetschek, Michael Poppel +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-$k$-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.

quant-pharXiv:2604.02083•New Journal of Physics•Apr 3, 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

Improving Feasibility in Quantum Approximate Optimization Algorithm for Vehicle Routing via Constraint-Aware Initialization and Hybrid XY-X Mixing

Yuan-Zheng Lei, Yaobang Gong, Xianfeng Terry Yang +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is a leading framework for quantum combinatorial optimization. The Vehicle Routing Problem (VRP), a core problem in logistics and transportation, is a natural application target, but it poses a major feasibility challenge for standard QAOA because feasible solutions occupy only a tiny fraction of the search space, and the conventional Pauli-$X$ mixer can disrupt partial solution structures that satisfy key local constraints. To address this issue, we propose a constraint-aware QAOA framework with two complementary components. First, we design a lightweight initialization strategy that encodes a selected subset of simple yet informative local one-hot constraints into the initial state, thereby reducing the initial superposition space and increasing the probability mass on states with important local structure. Second, we introduce a hybrid XY-$X$ mixer that preserves the constraint structure imposed at initialization while retaining exploratory flexibility over the remaining unconstrained degrees of freedom during QAOA evolution. We evaluate the proposed framework against standard QAOA under three progressively more realistic regimes: ideal statevector simulation, finite-shot sampling, and noisy finite-shot sampling. Across all regimes, the proposed method consistently achieves lower average energy and higher feasible-solution ratios than standard QAOA, indicating more effective guidance toward structurally valid, lower-cost VRP solutions. However, the performance gap narrows in the noisy regime. Because this setting adopts a hardware-inspired error model based on near-best-reported laboratory-level qubit gate and readout fidelities, the observed attenuation suggests that the practical advantage of the more structured mixer is likely to grow as quantum hardware improves and error rates decline.

cs.ETCross-listedarXiv:2604.07218•Transportation Research Part C Emerging Technologies•Apr 9, 2026•0 citations
The Quantum Approximate Optimization Algorithm (QAOA) is a promising framework for combinatorial optimization, but constrained problems are commonly handled using energetic penalty terms that require calibration and allow infeasible configurations to remain dynamically accessible. We develop a constraint-preserving QAOA framework for personnel rostering in which hard scheduling constraints are embedded directly into the mixer Hamiltonian. Using a binary rostering model with daily coverage and no-consecutive-duty constraints, we formulate the dynamics from a transition-graph perspective and introduce a guarded-XY mixer that confines the evolution to the fully feasible scheduling manifold. We further distinguish feasibility preservation from feasible-transition design and propose a tight-pattern extension that introduces collective feasible exchanges in saturated workload segments where local guarded exchanges alone are insufficient. Exact statevector simulations demonstrate that, compared with Penalty-X and Coverage-XY formulations under both expectation-value and Conditional Value-at-Risk optimization, the proposed approach eliminates hard-constraint penalty calibration, guarantees feasible evolution by construction, and consistently yields higher-quality output distributions with stronger concentration on optimal feasible schedules. To the best of our knowledge, this is the first constraint-preserving QAOA formulation for personnel rostering, and the transition-graph framework is readily applicable to a broad class of constrained quantum optimization problems.
Portfolio optimization under strict cardinality constraints is a combinatorial challenge that defies classical convex optimization techniques, particularly in the context of "Direct Indexing" and ESG-constrained mandates. In the Noisy Intermediate-Scale Quantum (NISQ) era, the Quantum Approximate Optimization Algorithm (QAOA) offers a promising hybrid approach. However, standard QAOA implementations utilizing transverse field mixers often fail to strictly enforce hard constraints, necessitating soft penalties that distort the energy landscape. This paper presents a comprehensive analysis of a constraint-preserving QAOA formulation against Simulated Annealing (SA) and Hierarchical Risk Parity (HRP). We implement a specific QAOA ansatz utilizing a Dicke state initialization and an XY-mixer Hamiltonian that strictly preserves the Hamming weight of the solution, ensuring only valid portfolios of size K are explored. Furthermore, we introduce a Trotterized parameter initialization schedule inspired by adiabatic quantum computing to mitigate the "Barren Plateau" problem. Backtesting on a basket of 10 US equities over 2025 reveals that our QAOA approach achieves a Sharpe Ratio of 1.81, significantly outperforming Simulated Annealing (1.31) and HRP (0.98). We further analyze the operational implications of the algorithm's high turnover (76.8%), discussing the trade-offs between theoretical optimality and implementation costs in institutional settings.
We introduce a counterdiabatic (CD) extension of the Quantum Approximate Optimization Algorithm (QAOA) for constrained portfolio optimization. By incorporating approximate adiabatic gauge potentials generated from nested commutators of the Ising-type portfolio problem Hamiltonian and the Hamming weight-preserving XY mixer Hamiltonian into our variational ansatz, the resulting Constrained Counterdiabatic QAOA (CCD-QAOA) achieves improved optimization performance under realistic budget and risk constraints. Benchmarking against standard XY-mixer QAOA, Grover-mixer QAOA, and penalty-based QAOA formulations, our numerical simulations demonstrate that, for a fixed QAOA depth, our CCD-QAOA approach consistently results in better approximation ratios.
Quantum optimization algorithms, such as the Quantum Approximate Optimization Algorithm, are emerging as promising heuristics for solving complex combinatorial problems. To improve performance, several extensions to the standard QAOA framework have been proposed in recent years. Two notable directions include: warm-starting techniques, which incorporate classical approximate solutions to guide the quantum evolution, and custom mixer Hamiltonians, such as XY mixers, which constrain the search to feasible subspaces aligned with the structure of the problem. In this work, we propose an approach that integrates these two strategies: a warm-start initialization with an XY mixer ansatz, enabling constraint-preserving quantum evolution biased toward high-quality classical solutions. The method begins by reformulating the combinatorial problem as a MaxCut instance, solved approximately using the Goemans-Williamson algorithm. The resulting binary solution is relaxed and used to construct a biased superposition over valid one-hot quantum states, maintaining compatibility with the XY mixer's constraints. We evaluate the approach on 5-city instances of the Traveling Salesperson Problem, a canonical optimization problem frequently encountered as a subroutine in real-world Vehicle Routing Problems. Our method is benchmarked against both the standard XY-mixer QAOA and a warm-start-only variant based on MaxCut relaxation. Results show that the proposed combination consistently outperforms both baselines in terms of the percentage and rank of optimal solutions, demonstrating the effectiveness of combining structured initializations with constraint-aware quantum evolution for optimization problems.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-kkk-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.
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 Approximate Optimization Algorithm (QAOA) is a leading framework for quantum combinatorial optimization. The Vehicle Routing Problem (VRP), a core problem in logistics and transportation, is a natural application target, but it poses a major feasibility challenge for standard QAOA because feasible solutions occupy only a tiny fraction of the search space, and the conventional Pauli-XXX mixer can disrupt partial solution structures that satisfy key local constraints. To address this issue, we propose a constraint-aware QAOA framework with two complementary components. First, we design a lightweight initialization strategy that encodes a selected subset of simple yet informative local one-hot constraints into the initial state, thereby reducing the initial superposition space and increasing the probability mass on states with important local structure. Second, we introduce a hybrid XY-XXX mixer that preserves the constraint structure imposed at initialization while retaining exploratory flexibility over the remaining unconstrained degrees of freedom during QAOA evolution. We evaluate the proposed framework against standard QAOA under three progressively more realistic regimes: ideal statevector simulation, finite-shot sampling, and noisy finite-shot sampling. Across all regimes, the proposed method consistently achieves lower average energy and higher feasible-solution ratios than standard QAOA, indicating more effective guidance toward structurally valid, lower-cost VRP solutions. However, the performance gap narrows in the noisy regime. Because this setting adopts a hardware-inspired error model based on near-best-reported laboratory-level qubit gate and readout fidelities, the observed attenuation suggests that the practical advantage of the more structured mixer is likely to grow as quantum hardware improves and error rates decline.