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:2211.05822 · Academia quantum.

Symmetry-based quantum algorithms for open-shop scheduling with hard constraints

Lennart Binkowski, Gereon Koßmann, Christian Tutschku, René Schwonnek

Published Sep 12, 2025• 3 citations
arXivHTMLPDF

Abstract

Encoding hard-constrained optimization problems into a variational quantum algorithm often turns out to be a challenging task. In this work, we provide a solution for the class of open-shop scheduling problems (OSSPs), which we achieve by rigorously employing the symmetries of the classical problem. An established approach for encoding the hard constraints of the closely related traveling salesperson problem (TSP) into mixer Hamiltonians was recently given by Hadfield et al.’s Quantum Alternating Operator Ansatz (QAOA). For the OSSP, which contains TSP as a special case, we show that desired properties of similarly constructed mixers can be directly linked to a purely classical object: the group of feasibility-preserving bit value permutations. We also outline a generic way to construct QAOA-like mixers for these problems. We further propose a new variational quantum algorithm that incorporates the underlying group structure more naturally and, as a proof of principle, implement our new algorithm for a small OSSP instance on an IBM Q System One. Unlike the generic QAOA, our algorithm allows for bounding the amount and the domain of parameters necessary to reach every feasible solution from above: If J jobs should be distributed, optimizing at most J ( J − 1 ) 2 / 2 parameters should suffice to reach the optimum with certainty.

DOI
10.20935/acadquant7900

Related papers

Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop Problem

Lilly Palackal, Richter, Leonhard, Maximilian Hess

One of the most promising attempts towards solving optimization problems with quantum computers in the noisy intermediate scale era of quantum computing are variational quantum algorithms. The Quantum Alternating Operator Ansatz provides an algorithmic framework for constrained, combinatorial optimization problems. As opposed to the better known standard QAOA protocol, the constraints of the optimization problem are built into the mixing layers of the ansatz circuit, thereby limiting the search to the much smaller Hilbert space of feasible solutions. In this work we develop mixing operators for a wide range of scheduling problems including the flexible job shop problem. These mixing operators are based on a special control scheme defined by a constraint graph model. After describing an explicit construction of those mixing operators, they are proven to be feasibility preserving, as well as exploring the feasible subspace.

arXiv:2311.04100•Journal of the Association for Information Systems•Nov 7, 2023•0 citations

Graph-controlled Permutation Mixers in QAOA for the Flexible Job-Shop Problem

Lilly Palackal, Leonhard Richter, Maximilian Hess

One of the most promising attempts towards solving optimization problems with quantum computers in the noisy intermediate scale era of quantum computing are variational quantum algorithms.The Quantum Alternating Operator Ansatz provides an algorithmic framework for constrained, combinatorial optimization problems.As opposed to the better known standard QAOA protocol, the constraints of the optimization problem are built into the mixing layers of the ansatz circuit, thereby limiting the search to the much smaller Hilbert space of feasible solutions.In this work we develop mixing operators for a wide range of scheduling problems including the flexible job shop problem.These mixing operators are based on a special control scheme defined by a constraint graph model.After describing an explicit construction of those mixing operators, they are proven to be feasibility preserving, as well as exploring the feasible subspace.

Hawaii International Conference on System Sciences (HICSS)•Jan 1, 2024•1 citation

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

Aruna Gupta, S R Hassan

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.

quant-pharXiv:2607.09145•Jul 13, 2026•0 citations

Application of quantum approximate optimization algorithm to job shop scheduling problem

Krzysztof Kurowski, Tomasz Pecyna, Mateusz Slysz +3 more

The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.

European Journal of Operational Research•Mar 12, 2023•62 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

Feasibility-Preserving Quantum Search for Constrained Transportation Routing

Dahye Kim, Monika Filipovska

Transportation routing problems such as the Traveling Salesperson Problem (TSP) and the Vehicle Routing Problem (VRP) are characterized by strict feasibility requirements involving customer assignment and visit rules, route sequencing, and depot-return logic alongside cost minimization. Most quantum routing formulations adopt Quadratic Unconstrained Binary Optimization (QUBO) encodings, where feasibility is incorporated indirectly via penalty terms in the cost Hamiltonian. While convenient for standard implementations of the Quantum Approximate Optimization Algorithm (QAOA), QUBO encodings allow the quantum search dynamics to allocate substantial probability to infeasible route configurations. This study develops a transportation-grounded constraint-aware Quantum Alternating Operator Ansatz (QAOA+) framework that embeds feasibility-preserving logic directly into the search operator. We introduce a custom mixer that functions as a quantum analogue of feasibility-preserving routing neighborhoods, using column-wise swap moves, it restricts evolution to feasible configurations while enabling structured exploration of valid routes. We compare three constraint-handling architectures: penalty-based QUBO QAOA, penalty free QAOA+ with the feasibility-preserving mixer, and a Hybrid QAOA+ combining mixer based feasibility with and penalty guidance. Results on small TSP and VRP instances show that constraint-handling architecture strongly influences feasible-route sampling, convergence behavior, and probability concentration over low-cost feasible routes. These findings position constraint-aware quantum search as a methodological extension of transportation routing search approaches, where feasibility is enforced through admissible quantum transitions rather than post-hoc penalties.

quant-pharXiv:2608.05394•Aug 7, 2026•0 citations
Encoding hard-constrained optimization problems into a variational quantum algorithm often turns out to be a challenging task. In this work, we provide a solution for the class of open-shop scheduling problems (OSSPs), which we achieve by rigorously employing the symmetries of the classical problem. An established approach for encoding the hard constraints of the closely related traveling salesperson problem (TSP) into mixer Hamiltonians was recently given by Hadfield et al.’s Quantum Alternating Operator Ansatz (QAOA). For the OSSP, which contains TSP as a special case, we show that desired properties of similarly constructed mixers can be directly linked to a purely classical object: the group of feasibility-preserving bit value permutations. We also outline a generic way to construct QAOA-like mixers for these problems. We further propose a new variational quantum algorithm that incorporates the underlying group structure more naturally and, as a proof of principle, implement our new algorithm for a small OSSP instance on an IBM Q System One. Unlike the generic QAOA, our algorithm allows for bounding the amount and the domain of parameters necessary to reach every feasible solution from above: If J jobs should be distributed, optimizing at most J ( J − 1 ) 2 / 2 parameters should suffice to reach the optimum with certainty.
One of the most promising attempts towards solving optimization problems with quantum computers in the noisy intermediate scale era of quantum computing are variational quantum algorithms. The Quantum Alternating Operator Ansatz provides an algorithmic framework for constrained, combinatorial optimization problems. As opposed to the better known standard QAOA protocol, the constraints of the optimization problem are built into the mixing layers of the ansatz circuit, thereby limiting the search to the much smaller Hilbert space of feasible solutions. In this work we develop mixing operators for a wide range of scheduling problems including the flexible job shop problem. These mixing operators are based on a special control scheme defined by a constraint graph model. After describing an explicit construction of those mixing operators, they are proven to be feasibility preserving, as well as exploring the feasible subspace.
One of the most promising attempts towards solving optimization problems with quantum computers in the noisy intermediate scale era of quantum computing are variational quantum algorithms.The Quantum Alternating Operator Ansatz provides an algorithmic framework for constrained, combinatorial optimization problems.As opposed to the better known standard QAOA protocol, the constraints of the optimization problem are built into the mixing layers of the ansatz circuit, thereby limiting the search to the much smaller Hilbert space of feasible solutions.In this work we develop mixing operators for a wide range of scheduling problems including the flexible job shop problem.These mixing operators are based on a special control scheme defined by a constraint graph model.After describing an explicit construction of those mixing operators, they are proven to be feasibility preserving, as well as exploring the feasible subspace.
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.
The Job Shop Scheduling Problem (JSSP) has always been considered as one of the most complex and industry essential scheduling problems. Optimizing the makespan of a given schedule generally involves using dedicated algorithms, local search strategies, or metaheuristics. These approaches, however, heavily rely on classical computational power, which is bounded by the physical limits of microcontrollers and power issues. Inspired by the promising results achieved for Quantum Annealing (QA) based approaches to solve JSSP instances, we propose a new approach that uses gate-model quantum architecture as an alternative to QA. We find that we can make use of the time-indexed JSSP instance representation to build a cost Hamiltonian, which can be embedded into Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution to a basic JSSP instance. We demonstrate the use of QAOA to solve the JSSP, and we evaluate its efficiency and accuracy for this problem from experimental results, as there is an increased urgency to demonstrate the applicability of quantum optimization algorithms. We also find that optimal variational parameters form patterns that can facilitate computation in bigger quantum circuits. Additionally, we compare the obtained noiseless simulation results of gate-model quantum circuits demonstrating the relationship between two evaluation criteria - makespan and energy. Finally, we analyze and present the overall performance of our approach with the increasing deadline and simulated depth of QAOA circuits.
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.
Transportation routing problems such as the Traveling Salesperson Problem (TSP) and the Vehicle Routing Problem (VRP) are characterized by strict feasibility requirements involving customer assignment and visit rules, route sequencing, and depot-return logic alongside cost minimization. Most quantum routing formulations adopt Quadratic Unconstrained Binary Optimization (QUBO) encodings, where feasibility is incorporated indirectly via penalty terms in the cost Hamiltonian. While convenient for standard implementations of the Quantum Approximate Optimization Algorithm (QAOA), QUBO encodings allow the quantum search dynamics to allocate substantial probability to infeasible route configurations. This study develops a transportation-grounded constraint-aware Quantum Alternating Operator Ansatz (QAOA+) framework that embeds feasibility-preserving logic directly into the search operator. We introduce a custom mixer that functions as a quantum analogue of feasibility-preserving routing neighborhoods, using column-wise swap moves, it restricts evolution to feasible configurations while enabling structured exploration of valid routes. We compare three constraint-handling architectures: penalty-based QUBO QAOA, penalty free QAOA+ with the feasibility-preserving mixer, and a Hybrid QAOA+ combining mixer based feasibility with and penalty guidance. Results on small TSP and VRP instances show that constraint-handling architecture strongly influences feasible-route sampling, convergence behavior, and probability concentration over low-cost feasible routes. These findings position constraint-aware quantum search as a methodological extension of transportation routing search approaches, where feasibility is enforced through admissible quantum transitions rather than post-hoc penalties.