Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers

1. Problem Statement

The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization. However, it faces two significant challenges when applied to real-world problems:

1. Hard Constraints: Standard QAOA is designed for unconstrained problems. Handling hard constraints (e.g., "one-hot" constraints where exactly one variable in a set must be 1) typically requires penalty terms, which expand the search space and complicate the optimization landscape.
2. XY-Mixer Limitations: While XY-mixers successfully confine quantum state evolution to feasible subspaces (preserving Hamming weight), previous attempts to "warm-start" these mixers (biasing the initial state toward promising regions based on classical solutions) failed to maintain theoretical guarantees. Specifically, using a biased initial state with a standard (unmodified) XY-mixer breaks the alignment between the initial state and the mixer's ground state, undermining the adiabatic theorem's convergence guarantees.

2. Methodology

The authors propose a unified framework called Iterative Warm-Start QAOA (IWS-QAOA) that integrates three core innovations:

A. Theoretical Foundation: Warm-Started XY-Mixer

• Alignment: The authors derive a new warm-started XY-mixer Hamiltonian ($H_P$) specifically for one-hot constraints (Hamming weight 1).
• Ground State Property: They analytically prove that the biased initial state $|W_P\rangle$ (a superposition of one-hot states weighted by a probability distribution $P$) is the unique ground state of this new Hamiltonian within the feasible subspace. This restores the critical alignment required for QAOA performance guarantees.
• Topology Agnostic: The formulation works for both fully-connected and sparse (e.g., ring or line) mixer topologies, provided the graph is connected.

B. Circuit Implementation

• Shallow Circuits: To ensure suitability for Noisy Intermediate-Scale Quantum (NISQ) devices, the authors provide a shallow circuit implementation of the warm-started XY-block.
• Decomposition: They demonstrate that the time evolution operator $e^{-i\beta H(q)}$ can be exactly decomposed into two two-qubit Pauli rotations ($R_Z$ and $U_{XY}$), avoiding the need for complex multi-qubit gates or deep circuits.
• Scaling: A scaling factor is introduced to the Hamiltonian to ensure consistent optimal $\beta$ parameters regardless of the bias strength, preventing the mixing magnitude from vanishing as probabilities approach 0 or 1.

C. Iterative Warm-Start (IWS) Algorithm

• Adaptive Bias: Instead of relying on a single classical solver to generate a fixed initial bias, the algorithm uses an iterative loop.
• Process:
  1. Initialize with a uniform distribution.
  2. Run QAOA to generate samples.
  3. Update the probability distribution $P$ based on the energy of the sampled solutions (using a Boltzmann-weighted expectation).
  4. Clamp probabilities to prevent premature convergence (regularization).
  5. Repeat until a target number of shots is reached.
• Hybrid Nature: This approach acts as an adaptive bias field, steering the quantum search toward high-quality regions discovered in previous iterations without requiring a problem-specific classical solver.

3. Key Contributions

1. Theoretical Proof: Analytical proof that the proposed warm-started XY-mixer Hamiltonian has the biased $|W_P\rangle$ state as its unique ground state, resolving the misalignment issue of prior work.
2. Hardware-Efficient Circuit: A decomposition of the warm-started mixer into shallow, two-qubit Pauli rotations suitable for NISQ hardware.
3. IWS-QAOA Framework: A novel hybrid algorithm that iteratively updates the bias distribution, significantly accelerating solution finding compared to standard QAOA.
4. Large-Scale Hardware Validation: Successful execution on the IBM Boston (Heron r3) QPU using 144-qubit problem instances, a scale rarely achieved with constrained mixers.

4. Results

Numerical Simulations

• Problems Tested: Max-k-Cut and Traveling Salesperson Problem (TSP).
• Performance: IWS-QAOA significantly outperformed standard XY-QAOA and random sampling baselines.
  • Probability Boost: It increased the probability of sampling optimal solutions ($P_{opt}$) by orders of magnitude (up to $100\times$ in some TSP cases).
  • Convergence: The algorithm found optimal solutions with fewer total shots. For example, in TSP instances, it reached optimal solutions in ~200 shots where standard QAOA failed to converge within 3000 shots.
  • Parameter Stability: The optimal QAOA parameters ($\beta, \gamma$) remained stable across iterations, justifying the "optimize-once" strategy used in the algorithm.

Hardware Experiments (IBM Boston QPU)

• Setup: 144 qubits (48 one-hot constraints of size 3) mapped to the heavy-hex topology.
• Noise Mitigation: Due to hardware noise causing constraint violations, a greedy steepest-descent post-processing step was applied to repair infeasible bitstrings.
• Outcomes:
  • IWS-QAOA successfully identified optimal solutions in 3 out of 5 tested instances.
  • For the remaining 2 instances, it found solutions with an approximation ratio >99%.
  • The method outperformed both standard QAOA (without warm-start) and random sampling with post-processing.

5. Significance

• Scalability: This work demonstrates one of the first large-scale applications of XY-mixers on utility-scale quantum hardware (144 qubits), proving that constrained optimization is feasible on current NISQ devices.
• Theoretical Rigor: By fixing the ground-state misalignment in warm-started mixers, the paper provides a theoretically sound path for integrating classical heuristics with quantum algorithms.
• Practical Utility: The combination of iterative warm-starting and classical post-processing offers a robust pipeline for solving real-world constrained optimization problems (like logistics and scheduling) where strict feasibility is required.
• Future Direction: The paper establishes a foundation for exploring other constraint types, advanced error mitigation, and hybrid genetic search algorithms using this iterative framework.