Constrained Quantum Optimization meets Model Reduction

Authors: Max Tschaikowski, Andrea Vandin · arXiv:2604.23317 · submission cycle 2026-04-28 · score 8/10 (HIGH)

Abstract

Quantum optimization algorithms promise advantages for difficult problems but are costly to simulate and analyze on classical machines. Recently, constrained quantum optimization has been investigated through the lens of Quantum Zeno dynamics, an approach which constrains the search to a subspace by means of quantum measurements. Exploiting that quantum measurements are projections, we propose a model reduction approach and show that simulations can be conducted in a lower-dimensional space. As possible applications, we demonstrate exponential state-space reduction of constrained quantum optimization in case of random 3-SAT and an agent coordination problem over graphs.

Executive summary

This paper observes that the projector P_Z defining a Quantum Zeno safe subspace also induces an exact reduced model of the constrained dynamics: write S for the orthonormal basis of Z and H&hat;_Z = S^† H S; then the constrained Schrödinger evolution can be carried out in dimension d = dim Z rather than 2ⁿ, with a clean lifting back via S. The reduction is exact (not an approximation) and brings classical simulation cost from O((ν+s) 2²ⁿ) down to O((ν+s) d²) + O(d 2²ⁿ) for the reduced-Hamiltonian computation — useful when d ≪ 2ⁿ. Numerical experiments on random 3-SAT and a graph-based agent-coordination 3-SAT show d dropping by 1–3 orders of magnitude relative to 2ⁿ for sub-formulas of the constraint. For Yuan's programme this is a classical-simulation enabler for Y2/Y3-style hard-constraint QAOA work: when the feasible subspace is small (high cardinality constraints, tight portfolio bounds), this technique gives an exact reduced simulator that scales with the feasible-set size rather than the qubit count.

Main contribution

The two theorems formalise an exact lifting between the constrained dynamics in the full 2ⁿ-dimensional space and a reduced dynamics in the d-dimensional Zeno subspace, plus the cost analysis showing O((ν+s) d²) classical simulation when the reduced unitaries are available. The construction is positioned as a "linear-algebraic analogue of bisimulation-based model reduction" from formal verification — applying that paradigm to QAOA simulation is the framing novelty. The numerical sections demonstrate that on random 3-SAT and an agent-coordination 3-SAT, sub-formulas with 70–90% of the constraints carve the feasible subspace down by > 100×.

Key theorems / lemmas / algorithms

Theorem 1 (Zeno reduction, Section 3): Let P_Z = S S^† with S^†S = I and H&hat;_Z = S^† H S. Then for the projected Zeno equation ∂_t|ψ_t⟩ = −i H_Z|ψ_t⟩ and reduced equation ∂_t|ψ&hat;_t⟩ = −i H&hat;_Z|ψ&hat;_t⟩, with |ψ&hat;₀⟩ = S^†|ψ₀⟩: |ψ_t⟩ - r = S|ψ&hat;_t⟩, where r = (I - P_Z)|ψ₀⟩ is the (unaltered) outside-Zeno remainder.
Equation (Cor): Iterated, U_k,Z(t_k)···U_1,Z(t₁)|ψ₀⟩ - r = S [U&hat;_k,Z···U&hat;_1,Z] S^†|ψ₀⟩.
Theorem 2 (QAOA simulation cost, Section 3.1): (i) constrained QAOA computes in O(ν d²) when reduced unitaries and S are known; (ii) computing U_Z(δ) from H_Z via numerical ODE integration costs O(s d²); (iii) computing H_Z = S^†HS costs O(d 2²ⁿ) in general, dropping to O(d²) when S consists of standard basis vectors and entries of H are computable in O(1).
Lemma (H_B entries in closed form): for the standard QAOA mixer H_B = ∑_j X_j, U_B(δ)_{k+1, l+1} = (cos δ)^{n − d(k,l)} (−i sin δ)^d(k,l) where d(k,l) is the Hamming distance — entries computable in constant time per call, enabling the O(d²) entrywise reduction.
Algorithmic recipe: use any #SAT solver (DPLL, etc.) to enumerate satisfying assignments of the constraint sub-formula Φ_k; these supply the standard-basis columns of S; restrict H_P, H_B to that d-dimensional row/column slice; simulate QAOA in the reduced space.

Detailed walkthrough

The paper's organising metaphor is that hard constraints in quantum optimisation play the role of "unsafe states" in formal verification. The authors recall that bisimulation-based model reduction in concurrency theory yields quotient systems that preserve all properties relevant to the safe subset of behaviours. The novel observation is that Quantum Zeno dynamics (where frequent projections onto a safe subspace Z confine the evolution) admits a strictly stronger reduction: instead of working with the projected Hamiltonian H_Z = P_Z H P_Z in the 2ⁿ-dimensional space (which has zero rows/columns outside Z), one can move to the d-dimensional subspace and work entirely there.

The proof of Theorem 1 (which the paper calls "Theorem on Zeno reduction") is a couple of lines of linear algebra: S^†S = I on Z, so P_Z = SS^† is the projector; the projected dynamics decompose |ψ_t⟩ into a Zeno part P_Z|ψ_t⟩ = S|ψ&hat;_t⟩ (which evolves by H&hat;_Z) and an outside remainder r = (I-P_Z)|ψ₀⟩ (fixed by Zeno). Iterating this through alternating QAOA layers (which all share the same Zeno space Z) gives the stated lifting. Theorem 2 then quantifies simulation cost with the only non-trivial step being the construction of H_Z; in the typical case where S consists of standard basis vectors (the safe subspace is spanned by feasible computational-basis states), each entry of H_Z is just an entry of H at indexed positions, computable in O(1) for both H_P (a diagonal SAT counter) and H_B (the closed-form Hamming-distance lemma).

Section 4 numerically demonstrates the reduction on two benchmark families. Random 3-SAT: for n=10–15 boolean variables, m clauses with m=4n or 5n, treat the first k = 0.7m / 0.8m / 0.9m clauses as the constraint Φ_k and use the remaining clauses as the QAOA objective. The average d across 100 instances drops sharply: e.g. at n=15, m=4n, k=0.9m, the mean d ≈ 22 against 2¹⁵ = 32 768 — a ratio of ~1500×. Tighter constraints (m=5n or k=0.9m) push the reduction further, as more clauses cut the feasible set faster. Agent coordination on graphs (not-all-equal 3-SAT from Erdös-Rényi graph adjacencies): the same picture — for n=15, p=0.4, k=0.9m, the average d is essentially 0 (the constraint becomes infeasible on most random graphs) — demonstrating that the construction degrades gracefully when the constraint pushes the safe subspace to nothing.

The honest caveat in the discussion is that this is an exact simulation result, not an algorithmic speedup of the quantum algorithm itself. Construction of S requires enumerating satisfying assignments of Φ_k, which is #SAT — itself exponential in n. But practical #SAT solvers (DPLL with caching, sharpSAT, etc.) handle instances with millions of variables in many real cases — far more than direct 2ⁿ simulation can. So the claim is: combine #SAT advances with QAOA simulation to push the size of classically-tractable constrained QAOA experiments. This connects to a recent thread of work cited in the paper (Mei, Bhattacharya, Lukashov, Hsieh 2024 in CAV) that exploits SAT solving for quantum-circuit reductions.

For Yuan, the operationally relevant point is that DGMVP (Y3) and quasi-binary portfolio QAOA (Y2) both have natural feasible subspaces — fixed-cardinality binary strings, integer-valued portfolios respecting budget — whose dimensions d are combinatorially polynomial in the qubit count. For DGMVP with a fixed-cardinality K out of N assets, d = C(N, K), and once K is small (the typical regime in Y3), d can be far smaller than 2^N. The reduction recipe here (Theorem 2 part iii with S = standard-basis indicators of feasible solutions) directly applies: simulate Y3's QAOA in the C(N,K)-dimensional feasible space rather than the 2^N-dimensional Hilbert space, and entries of H_P (the Markowitz objective on basis states) and H_B (X-mixer with the Hamming-distance closed form) are computable on demand. This could drastically extend the size of DGMVP instances Y3's classical methodology can probe before reaching the actual quantum hardware.

Figure rendering: this paper has no figures — only tables. Tables 1 (random 3-SAT reductions) and 2 (agent coordination reductions) are rendered in the source PDF.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y1 (warm-started QAOA): Indirect — Y1's iterative warm-starting in the full 2ⁿ space could be replicated more cheaply in the reduced d-space when the warm-start state is supported on the feasible subspace.
Y2 (quasi-binary portfolio QAOA): Direct method overlap. Y2's hard constraint-preserving mixer keeps the evolution inside a d-dimensional fixed-cardinality subspace by design. The reduction here is exactly the right simulation tool: S consists of feasible-cardinality computational basis states, and Y2's mixer satisfies the standard-basis assumption that gives the O(d²) reduction cost. Y2's classical benchmarks could push to larger N once this reduction is plugged in.
Y3 (QAOA DGMVP portfolio): Most actionable connection. Y3's classical simulation of QAOA-DGMVP is currently bounded by 2^N (or the chosen encoding's qubit count). Switching to the reduced simulator with d = C(N, K) immediately enlarges the accessible regime. Y3's dual-annealing and layerwise optimisations would all transfer unchanged (they operate on QAOA parameters, not on the simulation backend).
Y4 (Grover + ADMM cardinality-constrained): Tangential — Y4 uses amplitude amplification, not Zeno dynamics, but the cardinality-feasible subspace it operates in is exactly the one this reduction exploits. The reduction here would speed up classical baseline computations Y4 needs for its epsilon-approximation analysis.
Y5 (GW + Pauli sparsity): Mostly orthogonal — Y5's quantum-inspired SDP solver works with Gibbs states and Pauli-sparse decompositions, a different reduction principle than projection onto a discrete safe subspace. There is a thematic kinship in that both papers find structural sparsity that lets a 2ⁿ-dim quantum problem be carried out in a much smaller representation, but the techniques are not directly composable.
Y6 (PBR Heron2): Unrelated.

Recommended action for Yuan

Implement for Y3 follow-up. The reduction is short to code: take Y3's existing QAOA simulator, replace its full state-vector with a length-d vector indexed by feasible portfolios, replace H_P with its diagonal restriction (instant), replace H_B entry-access with the closed-form Hamming-distance lemma. The expected payoff is a 2–3 order-of-magnitude expansion of the classically simulable DGMVP regime — useful for tighter scaling fits and reaching the size where thermal-noise crossovers actually appear.
Cite in any future Y2 or Y3 paper that discusses classical-simulation methodology for hard-constraint QAOA. The paper makes a clean conceptual contribution that deserves to be on the reading list.
No urgent collaborator outreach — the technique is ready-to-implement from the paper alone. Email Tschaikowski only if Yuan plans a methodology paper combining this reduction with the SDP-Gibbs reductions of Y5.