Feasible Subspace Confinement in Quantum Optimization

23 concepts12 papers1 proposal

When solving combinatorial optimization problems on quantum computers, the sheer size of the search space is a fundamental hurdle. For an $N$-qubit system, the quantum state explores a Hilbert space of $2^N$ possible configurations. However, in real-world problems—such as scheduling flights or routing vehicles—the vast majority of these configurations represent "illegal" or invalid solutions that violate hard constraints.

Traditionally, variational quantum algorithms like the Quantum Approximate Optimization Algorithm (QAOA) handle constraints using soft penalties. This approach adds a penalty term to the objective function to discourage invalid states. However, soft penalties warp the energy landscape, require extensive hyperparameter tuning, and waste valuable quantum precision exploring invalid regions of the state space.

A rapidly growing paradigm shifts this strategy entirely: feasible subspace confinement. Instead of penalizing invalid states after they occur, this approach mathematically restricts the quantum state's evolution so that it never leaves the valid problem subspace. By embedding constraints directly into the quantum operators, every measurement is guaranteed to yield a 100% feasible solution.


The Alternating Operator Ansatz

To understand how we can confine a quantum state, we must look at how standard QAOA operates. Standard QAOA alternates between a problem Hamiltonian (which encodes the objective function) and a generic mixer Hamiltonian (typically a sum of single-qubit Pauli-X rotations). This generic mixer acts like an unconstrained diffusion process, scattering quantum amplitude across the entire $2^N$ Hilbert space.

To overcome this, Stuart Hadfield et al. introduced the Quantum Alternating Operator Ansatz (AOA) in From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz. The core insight of AOA is that the mixer operator does not have to be a blind, global rotation. Instead, we can design specialized mixing operators tailored to the structure of the problem. If the mixer is engineered to only transition between valid states, the algorithm is trapped within the feasible subspace throughout the entire optimization process.

Standard QAOA:
Initial State |+⟩ ───► [ Problem Mixer ] ───► [ Global X-Mixer ] ───► Explores Entire 2^N Space

Alternating Operator Ansatz (AOA):
Valid State |ψ_0⟩ ───► [ Problem Mixer ] ───► [ Subspace-Preserving Mixer ] ───► Confined to Feasible Subspace

Mathematical Confinement via Commuting Mixers

How do we design a mixer that inherently respects constraints? The answer lies in the mathematical property of commutation.

If a driver or mixer Hamiltonian $H_M$ commutes with a constraint operator $C$ (meaning $[H_M, C] = 0$), the expectation value of the constraint is a conserved quantity under the evolution of that mixer. As demonstrated by Debin Xiang et al. in Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization, embedding linear constraints directly into commuting driver Hamiltonians provides a mathematical guarantee of a 100% validity rate for generated solutions. Similarly, the Q-CHOP framework developed by Michael A. Perlin et al. in Q-CHOP: Quantum constrained Hamiltonian optimization utilizes a dedicated constraint Hamiltonian to ensure the state remains strictly within the valid subspace, bypassing the need for fragile soft-penalty tuning.

Example: Hamming Weight Preservation

Consider a "choose $k$ out of $N$" constraint, which requires exactly $k$ qubits to be in the $|1\rangle$ state. In quantum computing, the number of $|1\rangle$ states is known as the Hamming weight.

To confine the algorithm to this subspace, the authors use a two-step mechanism:

  1. State Preparation: Initialize the quantum computer in a state that already satisfies the constraint, such as a Dicke state (an equal superposition of all states with Hamming weight $k$).
  2. XY Mixers: Replace the standard X-mixer with an XY mixer, which performs particle-conserving hops (e.g., transforming $|01\rangle \leftrightarrow |10\rangle$). Because the XY mixer only swaps states without changing the total number of excitations, it commutes with the total Hamming weight operator.

In Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer, Pradeep Niroula et al. implemented this exact strategy (termed XY-QAOA) to natively enforce constraints, demonstrating that restricting quantum evolution to the valid subspace avoids the performance degradation typical of unconstrained methods.


Active Subspace Enforcement: Measurements and Controlled Gates

While commuting mixers work beautifully for linear conservation laws, more complex combinatorial constraints—such as ensuring a variable is never assigned to two conflicting slots simultaneously—require active enforcement mechanisms.

Mid-Circuit Projective Measurements

Instead of relying solely on passive algebraic preservation, the state can be actively forced into the correct subspace using quantum error mitigation principles. In Rethinking Parity Check Enhanced Symmetry-Preserving Ansatz, Ge Yan et al. combined a Hamming-weight-preserving ansatz with mid-circuit projective parity checks. By measuring parity checks during the circuit, any quantum amplitude that has leaked into invalid states due to hardware noise or gate imperfections is actively collapsed back into the valid problem subspace.

Multi-Qubit Controlled Gates

Another approach is to build conditional logic directly into the unitary execution. Xinyu Ye et al. developed a quantum neural network solver for the Quadratic Assignment Problem (QAP) in Towards Quantum Machine Learning for Constrained Combinatorial Optimization: a Quantum QAP Solver. Their architecture uses multi-qubit controlled gates to steer the quantum state dynamically toward the valid permutation subspace, eliminating classical post-processing or soft penalties.


Physics-Inspired Constraints: The QED Analogy

One of the most elegant manifestations of this idea borrows principles from particle physics. In network-flow optimization problems, constraints dictate that the incoming flow at any node must equal the outgoing flow (flow conservation).

In QED driven QAOA for network-flow optimization, Yuxuan Zhang et al. mapped these flow variables to electric fields in lattice Quantum Electrodynamics (QED). In electromagnetism, Gauss's law dictates that the divergence of the electric field equals the charge density, which is a fundamental local conservation law. By constructing a "QED-mixer" Hamiltonian inspired by gauge-invariant lattice field theories, the authors created an operator that inherently respects flow conservation at every node. The quantum state is physically incapable of violating the network constraints because doing so would violate the quantum equivalent of Gauss's law.


Real-World Applications and the Cost of Confinement

Feasible subspace confinement has unlocked the ability to tackle highly structured real-world optimization problems on near-term quantum hardware:

The Circuit Depth Trade-Off

Despite its clear mathematical advantages, confining the quantum state comes at a physical cost. As detailed by Pradeep Niroula et al. in their hardware deployment data, Data from "Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer", constraint-preserving algorithms require significantly deeper, more complex quantum circuits. Implementing multi-qubit interactions and specialized mixers increases gate counts, making the algorithm more sensitive to hardware noise.

To mitigate this hardware bottleneck, researchers are exploring hybrid strategies. For instance, Nicola Franco et al. showed in Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness that mathematical decomposition techniques (like Dantzig-Wolfe decomposition) can keep the quantum subproblem size constant across iterations, preventing the growth of qubit and constraint overhead.

Ultimately, as emphasized by D. Bucher et al. in Towards Robust Benchmarking of Quantum Optimization Algorithms, evaluating these approaches requires rigorous benchmarking metrics like Time-to-Solution (TTS). The field is actively balancing this trade-off: accepting the burden of deeper circuits in exchange for a clean, unwarped optimization landscape where every single measured state is guaranteed to be a valid solution.

Key Foundational Work

Toward Quantum Gate-Model Heuristics for Real-World Planning Problems (2020) — contributed 3 concept elements to this direction.
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2019) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_constraint_preserving_quantum_mixers_d42137ed,
  title = {constraint-preserving quantum mixers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constraint-preserving-quantum-mixers/rdr_d42137ed238b4ccd823342441b7078c7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_constraint_preserving_quantum_mixers_d42137ed_v1,
  title = {constraint-preserving quantum mixers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constraint-preserving-quantum-mixers/rdr_d42137ed238b4ccd823342441b7078c7/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake