pith. sign in

arxiv: 2211.05822 · v3 · pith:74TEUKIHnew · submitted 2022-11-10 · 🪐 quant-ph · math-ph· math.MP

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

Lennart Binkowski , Gereon Ko{\ss}mann , Christian Tutschku , Ren\'e Schwonnek This is my paper

Pith reviewed 2026-05-24 10:57 UTC · model grok-4.3

classification 🪐 quant-ph math-phmath.MP
keywords variational quantum algorithmsopen-shop schedulingQAOAsymmetrieshard constraintsmixer Hamiltoniansscheduling problems
0
0 comments X

The pith

Symmetries of open-shop scheduling allow a variational quantum algorithm to reach every feasible solution by optimizing at most quadratically many parameters.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how symmetries of the classical open-shop scheduling problem can be used to encode hard constraints into variational quantum algorithms. It connects the required properties of mixer Hamiltonians directly to the group of feasibility-preserving bit value permutations. This connection yields both a generic construction for QAOA-style mixers and a new algorithm that incorporates the group structure more naturally. The result is an explicit upper bound: at most quadratically many parameters, with bounded domains, suffice to reach every feasible solution, including the optimum, with certainty.

Core claim

By rigorously employing the symmetries of the open-shop scheduling problem, desired properties of similarly constructed mixers can be directly linked to the purely classical group of feasibility-preserving bit value permutations. This link enables a generic construction of QAOA-like mixers for OSSP. The authors further propose a new variational quantum algorithm that incorporates the underlying group structure more naturally. Unlike generic QAOA, this algorithm allows bounding the amount and domain of parameters from above: optimizing at most quadratically many parameters suffices to reach every feasible solution from above, including the optimum with certainty. A small instance was run as a

What carries the argument

The group of feasibility-preserving bit value permutations, which supplies the classical symmetries used to construct and analyze the quantum mixer Hamiltonians.

If this is right

  • OSSP instances, including TSP as a special case, admit QAOA-like mixers built generically from the permutation group.
  • The new algorithm reaches every feasible solution with certainty once the quadratic parameter bound is met.
  • The parameter domain is also bounded, reducing the search space compared with generic QAOA.
  • Small instances can be implemented on current quantum hardware, as shown by the IBM Q demonstration.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The symmetry-group approach may extend to other hard-constrained combinatorial problems whose feasible sets are closed under similar permutation groups.
  • If the quadratic bound holds in practice, it could make variational scheduling algorithms scale better than methods without such symmetry reduction.
  • The construction suggests a systematic way to derive mixers for any problem whose constraints define a group action on bit strings.

Load-bearing premise

The desired properties of the constructed mixers can be directly linked to the classical group of feasibility-preserving bit value permutations.

What would settle it

For an OSSP instance, run the new algorithm while varying only a quadratic number of parameters and check whether every feasible solution, including the known optimum, is reachable; failure to reach them would falsify the bound.

Figures

Figures reproduced from arXiv: 2211.05822 by Christian Tutschku, Gereon Ko{\ss}mann, Lennart Binkowski, Ren\'e Schwonnek.

Figure 1
Figure 1. Figure 1: FIG. 1: OSSP(2,2,4) constraint graph. In the above graph, the ve [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: OSSP(2,2,4) constraint graph with feasible solution. The colo [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: Sampling amplitudes of bit strings. One of the [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4: First iteration with sampled gradient descent. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5: Second iteration with sampled gradient descent. [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7: Fourth iteration with sampled gradient descent. [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8: Fifth iteration with sampled gradient descent. [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
read the original 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: Optimizing at most quadratically many parameters should suffice to reach the optimum with certainty.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper develops a symmetry-based approach to constructing mixers for variational quantum algorithms applied to open-shop scheduling problems (OSSP) with hard constraints. It links desired mixer properties to the classical group of feasibility-preserving bit-value permutations, outlines a generic QAOA-style mixer construction extending Hadfield et al.'s TSP work, and introduces a new variational algorithm that more directly incorporates the group structure. The central claim is that this enables an upper bound of at most quadratically many variational parameters whose optimization suffices to reach every feasible solution (and thus the optimum) with certainty; a proof-of-principle implementation on a small OSSP instance is executed on IBM Q hardware.

Significance. If the claimed parameter bound and mixer construction are rigorously established, the work would meaningfully advance constrained variational quantum optimization by providing a systematic, symmetry-driven reduction in the number of free parameters. The explicit reduction to a classical permutation group is a conceptual strength that could generalize to other permutation-constrained problems, and the hardware demonstration supplies concrete evidence of implementability on current devices.

minor comments (3)
  1. The abstract states the quadratic parameter bound but does not indicate the precise scaling (e.g., in terms of number of jobs or machines); adding this would clarify the practical scope of the result.
  2. Notation for the group of feasibility-preserving permutations and its action on bit strings should be introduced with a short definition or reference in the first section where it appears, to aid readers outside quantum information.
  3. The proof-of-principle section would benefit from an explicit statement of the instance size (number of jobs/machines) and the number of parameters actually optimized, to allow direct comparison with the claimed quadratic bound.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our manuscript on symmetry-based QAOA mixers for open-shop scheduling and for recommending minor revision. No specific major comments appear in the provided report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation links mixer Hamiltonians to the classical group of feasibility-preserving permutations and cites Hadfield et al. (external) for the TSP case. The quadratic parameter bound follows from incorporating the group structure into a new variational algorithm; no step reduces by construction to a fitted input, self-citation chain, or renamed ansatz. The construction is presented as independent of the target result and externally grounded.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides insufficient detail to identify specific free parameters, axioms, or invented entities; no explicit fitting or postulates described.

pith-pipeline@v0.9.0 · 5758 in / 1028 out tokens · 48340 ms · 2026-05-24T10:57:23.867149+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    As a consequence, a VQA ideally has to perform its opti- mization only on a subset of ’allowed/feasible’ quantum states, i.e

    In contrast to other popular problems, like a)Electronic mail: kossmann@stud.uni-hannover.de; These authors contributed equally b)Electronic mail: lennart.binkowski@itp.uni-hannover.de; These authors contributed equally c)Electronic mail: christian.tutschku@iao.fraunhofer.de d)Electronic mail: rene.schwonnek@itp.uni-hannover.de MAX-CUT or 3-Sat, the OSSP ...

    work page

  2. [2]

    Then a generic COP of size N with A constraints is of the form min z∈ Z(N ) f (z) s.t

    Constrained Combinatorial Optimization In the following, we restrict to minimization problems, as maximization tasks may be considered analogously. Then a generic COP of size N with A constraints is of the form min z∈ Z(N ) f (z) s.t. ca(z) = 1, a ∈ [A], (1) where - Z(N ) := {0, 1}N is the bit strings of length N , - f :Z(N ) → R is the objective function...

    work page

  3. [3]

    The J jobs should be distributed to the MT available positions such that J: every job gets performed precisely once P: no position is filled with more than one job

    Open-Shop Scheduling Let us formally introduce the OSSP, depending on the three parameters - M : number of machines, - T : number of time slots per machine, and - J: number of jobs. The J jobs should be distributed to the MT available positions such that J: every job gets performed precisely once P: no position is filled with more than one job. Note that O...

    work page

  4. [4]

    First we identify [ N ] with a vertex set V = {v1,...,v N }

    Constraint Graph Model The solution set of a COP C = (N,f, {ca}) can be further studied by introducing the so-called constraint graph16,17. First we identify [ N ] with a vertex set V = {v1,...,v N }. Moreover, the bit string zI , associated to the subset I ⊆ [N ], is identified with the subset of ver- tices VI := {vn : n ∈ I} ⊆ V . The constraints enter a...

    work page

  5. [5]

    The standard en- coding procedure identifies each bit string z with a com- putational basis state |z⟩ of theN -qubit space H := C2N

    Encoding on Quantum Computers Consider a COP C = (N,f, {ca}). The standard en- coding procedure identifies each bit string z with a com- putational basis state |z⟩ of theN -qubit space H := C2N . This induces a representation of functions over Z(N ) as linear operators on H. Namely, the classical objective functionf is mapped to an objective Hamiltonian, d...

    work page

  6. [6]

    Recall that a graph au- tomorphism is a bijection ϕ : V → V such that ϕ as well as ϕ − 1 preserve adjacency

    Feasibility-Preserving Graph Automorphisms Let G = (V,E ) be a graph. Recall that a graph au- tomorphism is a bijection ϕ : V → V such that ϕ as well as ϕ − 1 preserve adjacency. One can actually prove that any bijective graph homomorphism between G and itself is already a graph automorphism. We start with the general observation that graph automorphisms ...

    work page

  7. [7]

    With some effort one can show the fol- lowing theorem

    Determining F Since the relation ( 11) is divided in two logically dis- joint parts, one concludes that the constraint graph is given by the cartesian product 19 of the two graphs K P and K J for P := MT , where K n is the complete graph with n vertices. With some effort one can show the fol- lowing theorem. 20 Theorem 3. Let G be a graph and H1,...,H k be...

    work page

  8. [8]

    F ′) via block systems

    Block Structure We further characterize the group action of F (resp. F ′) via block systems. Given a group G acting on some set X, a subset ∆ ⊂ X with 1 < |∆|< |X| is called a block23 of G iff ∀g ∈ G : g∆ = ∆ ∨ g∆ ∩ ∆ = ∅. A partition of X into blocks of G is then called a block system. It is immediately clear that the collection of job blocks ∆(j) and of ...

    work page

  9. [9]

    Starting from a feasible initial state |ι⟩ ∈ S , we alternately apply parametrized ’phase separator’ gates UP(γ) and ’mixer’ gates UM(β ) p times, where p is the circuit depth

    Relation to the QAOA Consider a COP with encoded objective Hamiltonian C, solution space S ⊆ H , and optimal solution space Smin ⊆ S . Starting from a feasible initial state |ι⟩ ∈ S , we alternately apply parametrized ’phase separator’ gates UP(γ) and ’mixer’ gates UM(β ) p times, where p is the circuit depth. This yields a parametrized trial state |⃗β,⃗ ...

    work page

  10. [10]

    A Quantum Group Optimization Algorithm We propose a VQA tailored to busy OSSP-instances 22, thus conceptually considering the TSP. Namely, given a complete graph G = (V,E ) (not the constraint graph!) with |V |=J vertices, we consider the quadratic objective function f :Z(J 2) → R z ↦→ ∑ {u,v}∈ E duv J∑ j=1 (zu,jzv,j+1 +zv,jzu,j+1), (30) where duv is the ...

    work page

  11. [11]

    Start in a solution state |ι⟩ ∈ S

    work page

  12. [12]

    Apply the parameterized quantum circuit ( 33)

    work page

  13. [13]

    Variationally optimize ⃗β ∈ [0, π 2 ] J(J− 1)2 2 using a classical optimization rule

    work page

  14. [14]

    Furthermore, the parameter space is always the same and especially compact, regardless of the objective func- tionf

    Measure the final outcome state in the computa- tional basis. Furthermore, the parameter space is always the same and especially compact, regardless of the objective func- tionf . This has to be seen in contrast to general QAOA- mixers for which no comparable restriction of the neces- sary parameter space is possible. Thus, in our case, sam- pling methods ...

    work page

  15. [15]

    Figure 1 displays its constraint graph

    Noiseless Implementation First, we demonstrate our just introduced VQA with- out noise on an OSSP(2,2,4)-instance. Figure 1 displays its constraint graph. The group of job permutations is thus given by SJ =S4. After assigning a bit to each of the 16 elements in [2] ×

    work page

  16. [16]

    (36) Consequently, we have to implement three distinct mixer Hamiltonians B1, B2, B3

    × [4] via (m,t,j ) ↦→ 4(m − 1) + 2(t − 1) +j, (35) we explicitly generate SJ with τ1,τ2, and τ3: SJ = ⟨(1, 2)(5, 6)(9, 10)(13, 14), (2, 3)(6, 7)(10, 11)(14, 15), (3, 4)(7, 8)(11, 12)(15, 16)⟩. (36) Consequently, we have to implement three distinct mixer Hamiltonians B1, B2, B3. As a concrete example, con- sider the permutation (1, 2)(5, 6)(9, 10)(13, 14) ...

    work page

  17. [17]

    a TSP instance with 3 cities, and demonstrate our VQA on a real (noisy) quantum hardware: the IBM Q Sys- tem One

    Implementation With Noise Second, we consider an OSSP(1,3,3)-instance, i.e. a TSP instance with 3 cities, and demonstrate our VQA on a real (noisy) quantum hardware: the IBM Q Sys- tem One. In addition, we simulate the application with a classical computer. The group of job permutations is given by SJ = S3. Since we only have one machine, we simply drop t...

    work page

  18. [18]

    Their application to z0 yields idz0 = z0, τ1 z0 = 010100001, τ2z0 = 100001010, τ1τ2z0 = 010001100

    clas- sically corresponds to having only access to four group elements: id, τ1, τ2, and τ1τ2. Their application to z0 yields idz0 = z0, τ1 z0 = 010100001, τ2z0 = 100001010, τ1τ2z0 = 010001100. (46) According to Table III , the colored bit string is thus the optimal accessible feasible solution. For the actual parameter adaptation we use sampled gradient descent:

    work page

  19. [19]

    Construct a ball Bi ⊂ [0,π/ 2]3 around some pa- rameter values ⃗βi

    work page

  20. [20]

    Sample new parameter values uniformly from Bi

    work page

  21. [21]

    Apply the correspondingly parametrized circuit to the initial state and measure the expectation value of C

    work page

  22. [22]

    The size of the constructed ball Bi is adapted in each step i: The steeper the drop in expectation values, the smaller the radius becomes

    Choose parameter values ⃗βi+1 from the sample minimizing the expectation value and repeat step 1 with i ↦→ i + 1. The size of the constructed ball Bi is adapted in each step i: The steeper the drop in expectation values, the smaller the radius becomes. For our numerical execution we choose random initial parameters and a sample size of 40 in each step. 11...

    work page arXiv 2021