Constrained Quantum Optimization at Utility Scale: Application to the Knapsack Problem

1. Problem Statement

The paper addresses the challenge of solving constrained combinatorial optimization problems on near-term quantum hardware, specifically targeting utility-scale problem sizes (up to 150 qubits).

• Context: The primary application is the Unit Commitment (UC) problem in power systems, which involves deciding which power generators to turn on/off to meet demand while minimizing costs and adhering to operational constraints.
• Challenge: Standard Variational Quantum Algorithms (like QAOA) struggle with constrained problems because:
  1. The feasible solution space is a tiny fraction of the full Hilbert space.
  2. Enforcing constraints strictly (via complex mixing Hamiltonians) often requires deep circuits, which are infeasible on current noisy hardware.
  3. The UC problem involves both binary (on/off) and continuous (power output) variables, creating high overhead for quantum hardware.
• Goal: To demonstrate a successful implementation of a constrained optimization algorithm on real quantum hardware at a scale relevant to industrial utility problems, comparing performance against state-of-the-art classical solvers (Gurobi).

2. Methodology

A. Problem Reduction: UC to 1D Knapsack

The authors simplify the single-period Unit Commitment problem by removing time-coupling constraints (ramping, min-up/down times). They utilize first-order optimality conditions to analytically eliminate continuous variables ($p_i$).

• By introducing a marginal cost parameter $D$, the continuous power output variables are determined analytically based on whether they are at their bounds or interior.
• This reduces the problem to a purely binary optimization problem: selecting a subset of units to minimize cost subject to a demand constraint.
• Mathematically, this is equivalent to the 1D Knapsack Problem, where "weights" are power outputs and "values" are cost savings.

B. Algorithm: Copula-QAOA (cop-QAOA)

Instead of using complex mixers that strictly enforce feasibility (which increase circuit depth), the authors employ cop-QAOA, a hardware-efficient approach:

• Biased Initial State: Instead of a uniform superposition, the algorithm starts with a product state biased toward feasible solutions. This is generated using a smoothed "lazy greedy" heuristic, which assigns probabilities to qubits being in the $|1\rangle$ state based on item efficiency ratios.
• Constant-Depth Mixers: The algorithm uses copula mixers (specifically with an anti-correlation parameter $\theta = -1$). These mixers are constant-depth circuits that encourage transitions between states while keeping the quantum state near the feasible subspace without strictly restricting it.
• Cost Function: The objective is encoded via a diagonal cost Hamiltonian. Infeasible solutions are assigned a cost of zero (or penalized) during the classical optimization loop to guide the variational parameters.

C. Experimental Setup

• Hardware: Experiments were run on IBM Quantum processors (specifically ibm_kingston, a Heron r2 processor with a heavy-hex layout).
• Error Mitigation: The team utilized Q-CTRL Performance Management (Fire Opal), which includes layout optimization, dynamical decoupling, and AI-driven transpilation to suppress errors.
• Instance Selection: The authors carefully selected problem instances known to be difficult for classical solvers. They generated instances using "Inversely Strongly Correlated" distributions and methods from [15] that create "hard" knapsack instances where Gurobi struggles to find a zero optimality gap.
• Training Strategy: A layer-by-layer training approach was used. Parameters for new layers were optimized while fixing previous layers. For some instances, a grid search was performed to find optimal initial parameters to avoid local minima.

3. Key Contributions

1. Utility-Scale Demonstration: This work presents the largest successful demonstration of the Knapsack problem on IBM Quantum hardware to date, scaling up to 150 qubits.
2. Hybrid Workflow Innovation: The paper refines the reduction of the Unit Commitment problem to a Knapsack problem, showing it can be solved with a hybrid workflow requiring only one continuous parameter (marginal cost $D$), significantly reducing the classical overhead compared to previous hybrid approaches.
3. Hardware-Efficient Constraint Handling: It validates the cop-QAOA strategy on real hardware, proving that biased initial states and shallow mixers can effectively handle constraints without the circuit depth penalties of strict feasibility-preserving mixers.
4. Benchmarking Rigor: The authors highlight that not all "NP-hard" problems are hard for classical solvers at practical scales. They specifically curated instances where Gurobi fails to close the optimality gap, providing a fair benchmark for quantum advantage.

4. Results

• Performance vs. Lazy Greedy: cop-QAOA consistently outperformed the "lazy greedy" baseline (a standard classical heuristic) in terms of approximation ratio and best-found solution value.
• Performance vs. Gurobi:
  • On simulators, cop-QAOA found solutions very close to, and in some cases slightly better than, those found by Gurobi.
  • On hardware, the results were competitive. For a 100-item instance where Gurobi could not find a zero-gap solution, cop-QAOA found a solution with a better best-value than Gurobi's best feasible solution.
  • For a 150-item instance, while the hardware noise reduced the fraction of valid samples (from ~89% in simulation to ~13% in hardware), the algorithm still produced valid solutions that were competitive with classical baselines.
• Training Landscape: The authors observed that the parameter landscapes (cost vs. $\gamma, \beta$) were structurally similar across different problem instances. This suggests parameter transferability, meaning optimal parameters found for one instance might generalize to others, mitigating the "barren plateau" problem.
• Runtime: The total runtime on hardware (excluding classical parameter optimization) was under 3 minutes for 5 QAOA rounds, significantly faster than the 70+ minutes Gurobi took to fail to improve its solution on the same instance.

5. Significance and Conclusion

• Practical Relevance: This is a significant step toward utility-scale quantum optimization. It demonstrates that quantum algorithms can be applied to real-world industrial problems (like power grid management) on current hardware, not just toy examples.
• Algorithmic Viability: The success of cop-QAOA suggests that biasing the search space via initial states and shallow mixers is a more viable path for near-term constrained optimization than strictly enforcing constraints via deep circuits.
• Future Directions: The authors identify that while the current approach is promising, future work must focus on:
  • Extending to multi-period UC with time-coupling constraints.
  • Developing better training strategies for constrained problems (e.g., moving beyond simple cost averaging to tail-focused objectives like CVaR).
  • Refining instance generation to better reflect real-world operational challenges.

In summary, the paper provides a robust proof-of-concept that constrained quantum optimization can be scaled to 150 qubits on real hardware, yielding solutions that compete with or surpass state-of-the-art classical solvers on specifically crafted hard instances.