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

This paper introduces a symmetry-based approach to encode hard constraints in open-shop scheduling problems for quantum computing, proposing a novel variational algorithm that leverages feasibility-preserving permutation groups to guarantee reaching optimal solutions with certainty by optimizing only a quadratic number of parameters.

The Gist

The Big Picture: The Quantum Puzzle Box

Imagine you are a logistics manager trying to schedule a fleet of delivery trucks. You have a list of jobs (deliveries), a set of machines (trucks), and a timeline (time slots). The rules are strict:

1. Every job must be done exactly once.
2. No truck can be in two places at once.
3. No time slot can have two jobs.

This is called the Open-Shop Scheduling Problem (OSSP). It's a classic "hard" puzzle. If you try to solve it with a normal computer, it can take forever because there are too many wrong combinations to check.

The authors of this paper asked: Can we use a quantum computer to solve this faster?

The problem is that current quantum computers are like clumsy toddlers; they make mistakes easily. If you just ask them to "find the best schedule," they often wander into "forbidden zones" (schedules that break the rules, like assigning two jobs to one truck at the same time).

The team's solution is to build a quantum robot that only knows how to walk on the "safe path." They designed a new algorithm that physically prevents the computer from ever considering an illegal schedule.

---

The Core Idea: The "Symmetry" Key

To understand their trick, imagine a room full of people (the possible schedules).

• The Bad Schedules: People standing in the wrong spots (breaking rules).
• The Good Schedules: People standing in the right spots.

Most quantum algorithms try to push the "bad" people out of the room by giving them a heavy penalty (like a fine). But this is messy. The bad people might still linger, or the penalty might not be strong enough.

The Authors' Approach:
Instead of punishing the bad people, they realized that the "Good Schedules" have a hidden symmetry.
Think of the jobs as dancers and the time slots as dance partners. If you have a perfect dance routine (a valid schedule), you can swap the partners around in specific ways, and you still have a perfect routine.

The authors discovered a mathematical "group" (a set of rules) that describes exactly how you can shuffle these jobs around without breaking the rules. They call this the Feasibility-Preserving Group.

The Analogy:
Imagine a Rubik's Cube.

• Standard Approach: You try to solve it by randomly twisting faces and hoping you don't mess up the colors you already fixed.
• This Paper's Approach: You realize that if you only twist the cube in specific, pre-approved ways (symmetries), you are guaranteed to stay in a state where the colors are still aligned. You never have to worry about "breaking" the cube because your moves are mathematically designed to keep it solved.

The New Algorithm: The "Shuffle" Machine

The paper proposes a new type of quantum algorithm (a Variational Quantum Algorithm) that uses this symmetry.

1. Start Safe: You start the computer with one valid schedule (a "seed" solution).
2. The Mixer: Instead of random noise, the computer applies a special "mixer" gate. This gate is like a shuffle button that only swaps jobs around in ways that are mathematically guaranteed to keep the schedule valid.
3. The Guarantee: The authors proved a very strong mathematical fact: If you have $J$ jobs, you only need to adjust a specific, manageable number of "knobs" (parameters) to reach any possible valid schedule, including the absolute best one.

The "Knob" Analogy:
Imagine you have a giant safe with a combination lock.

• Old Quantum Methods: You have to guess the combination by trying billions of random numbers. You might get lucky, but you might also get stuck in a dead end.
• This Method: The authors found the map. They proved that you only need to turn $J^3$ (roughly the cube of the number of jobs) specific knobs to reach every single door in the safe. It's like having a master key that can open every door if you just turn the right dials in the right order.

What They Actually Did (The Proof)

The paper doesn't just talk theory; they tested it.

1. The Simulation: They simulated a small version of the problem (4 jobs, 2 machines) on a classical computer.

   • Result: The old method (which uses "fines" for bad schedules) failed to find good solutions. It got stuck in the "forbidden zones."
   • Result: Their new method, which stays strictly on the "safe path," found the perfect solution quickly.

2. The Real Hardware Test: They took a tiny version of the problem (3 jobs, 1 machine—basically a Traveling Salesperson problem) and ran it on a real quantum computer (IBM Q System One).

   • Result: Even though the real computer was noisy (like a radio with static), their algorithm still managed to find the best solution more often than random chance. It showed that the "safe path" logic works even on imperfect hardware.

The Bottom Line

This paper is about building guardrails for quantum computers.

Instead of hoping the computer stays on the road, they redesigned the car so it cannot leave the road. By using the mathematical symmetries of the scheduling problem, they created an algorithm that:

• Never considers an impossible schedule.
• Can reach the perfect solution by turning a specific, limited number of knobs.
• Works better than current methods, even on today's noisy, imperfect quantum machines.

They didn't solve the problem for every industry in the world yet, but they built a new, more reliable engine for solving this specific type of scheduling puzzle.

Technical Summary

Technical Summary: Symmetry-based Quantum Algorithms for Open-Shop Scheduling with Hard Constraints

Problem Statement
The paper addresses the Open-Shop Scheduling Problem (OSSP), a combinatorial optimization problem where $J$ jobs must be distributed across $M$ machines with $T$ time slots each. The constraints require that every job is performed exactly once and no machine-time slot is assigned more than one job. This problem is a generalization of the Traveling Salesperson Problem (TSP), where $TSP = OSSP(1, T, T)$.

The core challenge lies in encoding these "hard constraints" into Variational Quantum Algorithms (VQAs). Unlike unconstrained problems (e.g., MAX-CUT) or those with "soft-coded" constraints (where infeasibility is penalized in the objective function), OSSP requires the optimization to remain strictly within the feasible subspace. Soft-coding often leads to suboptimal optimization landscapes or feasibility issues. While the Quantum Alternating Operator Ansatz (QAOA) offers a framework for hard constraints via feasibility-preserving mixers, existing constructions for scheduling problems have often been heuristic, failing to fully exploit the underlying symmetry structures of the problem.

Methodology
The authors employ a rigorous group-theoretic approach combined with graph theory to analyze the feasibility structure of OSSP:

1. Constraint Graph Model: The problem is mapped to a constraint graph $G=(V, E)$ where vertices represent potential job assignments (bits) and edges represent constraints prohibiting simultaneous assignment. Solutions correspond to independent sets (cocliques) of size $J$.
2. Feasibility-Preserving Group ($F$): The authors identify the group $F$ of bit-value permutations that map feasible solutions to other feasible solutions. They prove that for OSSP, this group is isomorphic to the automorphism group of the constraint graph, $\text{Aut}(G)$.
   • For the "busy" case ($MT = J$), the group structure is a wreath product involving symmetric groups.
   • Crucially, they demonstrate that $F$ acts transitively on the set of all feasible solutions. This means any feasible solution can be transformed into any other via a sequence of permutations in $F$.
3. Algorithm Design:
   • QAOA Extension: They refine the QAOA framework by constructing mixers directly from the generators of $F$. Since $F$ acts transitively, mixers derived from its elements guarantee that the entire feasible subspace is accessible.
   • New VQA (Quantum Group Optimization): For busy OSSP instances, the authors propose a novel algorithm that bypasses the standard phase separator. By decomposing permutations in the symmetric group $S_J$ (which represents the solution space for busy OSSP) into products of transpositions, they construct a parameterized circuit using SWAP gates.
   • Parameterization: The algorithm utilizes a specific decomposition of permutations into $J(J-1)/2$ transpositions. Each transposition is implemented as a product of disjoint SWAP gates across job blocks.

Key Contributions

• Theoretical Characterization: The paper provides a complete characterization of the feasibility-preserving group for OSSP, proving its isomorphism to the constraint graph's automorphism group and establishing its transitive action on the solution set.
• Guaranteed Reachability: Unlike generic QAOA, where reachability of the optimum is only guaranteed in the limit of infinite circuit depth ($p \to \infty$), the proposed VQA offers a strict upper bound on parameters. The authors prove that $O(J^3)$ (specifically $J(J-1)/2$) parameters are sufficient to reach any feasible solution, including the global optimum, with certainty.
• Hard-Constraint Implementation: The work demonstrates a systematic method to construct mixers that strictly preserve the feasible subspace, avoiding the pitfalls of soft-coding constraints.
• Hardware Implementation: The authors implement the algorithm on a real quantum device (IBM Q System One) for an $OSSP(1, 3, 3)$ instance (equivalent to a 3-city TSP) and perform noiseless simulations for an $OSSP(2, 2, 4)$ instance.

Results

• Noiseless Simulation ($OSSP(2, 2, 4)$): The proposed VQA with hardcoded constraints successfully reached the global minimum (approximation ratio of 100%) within six iterations (optimizing 12 parameters). In contrast, a standard QAOA with soft-coded constraints failed to exceed an approximation ratio of 30%, even with access to all 18 parameters, due to the difficulty of concentrating amplitude in the small feasible subspace.
• Real Hardware ($OSSP(1, 3, 3)$): On the IBM Q System One, the algorithm demonstrated the ability to leave the initial state and increase the overlap with the local optimum. However, the authors note that hardware noise significantly obscured the convergence to the global optimum, with the noisy background dominating the signal. The classical noisy simulation showed better convergence, suggesting that current hardware limitations (coherence time, gate fidelity) are the primary bottlenecks rather than the algorithmic design.

Significance and Claims
The paper claims that its primary significance lies in providing a systematic, symmetry-based framework for hardcoding constraints in VQAs, moving beyond heuristic mixer design. By linking the problem's feasibility structure to graph automorphisms, the authors derive an algorithm with a theoretical guarantee that a polynomial number of parameters ($O(J^3)$) is sufficient to explore the entire solution space.

The authors are modest regarding practical scalability. They acknowledge that while the theoretical parameter bound is strong, the practical optimization of these parameters is hindered by "barren plateaus" and the exponential number of local minima in high-dimensional spaces. Furthermore, they explicitly state that their approach relies on equality constraints (symmetries) and may not directly apply to problems with inequality constraints (like the knapsack problem) where such symmetries are absent. The work serves as a proof of principle that feasibility-preserving group structures can be leveraged to design more efficient and theoretically grounded quantum algorithms for scheduling problems, provided future hardware improvements address noise and connectivity issues.