⚛️ quantum physics

One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems

This paper introduces a unified quantum-classical framework that generalizes Quantum Conic Programming to solve arbitrary hard-constrained combinatorial optimization problems by encoding feasibility into a single constraint, thereby enabling efficient parameter optimization via a generalized eigenvalue problem while avoiding barren plateaus and requiring no problem-specific Hamiltonians or oracles.

Original authors: Lennart Binkowski, Tobias J. Osborne, Marvin Schwiering, René Schwonnek, Timo Ziegler

Published 2026-07-29

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Lennart Binkowski, Tobias J. Osborne, Marvin Schwiering, René Schwonnek, Timo Ziegler

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, impossible-looking puzzle. You have a box of thousands of pieces, but only a tiny fraction of them actually fit together to make the picture. The rest are "fake" pieces that look similar but will ruin the whole image if you try to force them in. This is the daily struggle of combinatorial optimisation, a field of math and computer science that tries to find the absolute best solution among billions of possibilities. Think of it like planning the perfect delivery route for a truck, scheduling every class in a school, or packing a backpack with the most valuable items without breaking the weight limit.

For decades, we've used classical computers to tackle these puzzles, but they often get stuck. It's like trying to find the lowest point in a foggy mountain range by feeling your way down; you might get stuck in a small valley thinking it's the bottom, when a much deeper valley is just over the next ridge. Recently, scientists have been excited about quantum computers, which use the weird rules of quantum physics to explore many paths at once. However, these machines are still "noisy" and fragile. A major headache for researchers is that many quantum methods get stuck in a "barren plateau"—a flat, featureless landscape where the computer can't tell which way is down, so it stops learning. Furthermore, forcing a quantum computer to respect strict rules (like "don't break the backpack") is incredibly hard to program.

This is where a new paper from researchers at Leibniz University Hannover steps in. They have developed a clever new framework called One for All: A Universal Quantum Conic Programming Framework. Think of it as a master key that unlocks the door to solving these hard, rule-bound puzzles on quantum computers without getting lost in the fog.

The Problem: The "No-Go" Zones

Imagine you are playing a video game where you have to collect coins (the goal) but you must never step on a trap (the constraint). In the past, quantum algorithms tried to handle this by giving you a "soft" penalty: if you stepped on a trap, you lost some points. But this is tricky. If the penalty is too weak, you might still step on traps; if it's too strong, the game becomes impossible to play because the penalty drowns out the coins.

Other methods tried to build a game world where traps simply didn't exist, but this required designing a unique, custom-made game engine for every single puzzle. There was no "universal" way to do it. The researchers in this paper wanted to build a tool that works for any puzzle, no matter how strict the rules are, without needing a custom engine for each one.

The Solution: A Magic Filter and a Smart Map

The authors propose a method that combines a quantum computer with a classical computer in a very specific dance. Here is how it works, using a simple analogy:

The Quantum Mixer (The Magic Filter):
Imagine you have a bag of marbles. Some are gold (good solutions), and some are red (bad solutions that break the rules). In the past, you had to carefully pick out the gold ones one by one. This new method uses a "Linear Combination of Unitaries" (LCU). Think of this as a magic filter. You take a bunch of different ways to shuffle the marbles (quantum operations) and mix them together with specific weights. The magic is that even if some of the shuffling methods accidentally let red marbles through, the combination of all of them acts like a perfect filter that only lets gold marbles stay. This ensures that at every step, the quantum computer is only looking at valid solutions.
The Classical Brain (The Smart Map):
Usually, when a quantum computer tries to find the best solution, it has to guess and check, which is slow and prone to getting stuck in those "barren plateaus" (the foggy flatlands). This paper changes the game. Instead of guessing, the quantum computer takes a snapshot of the current situation and sends it to a classical computer. The classical computer doesn't just guess; it solves a specific type of math problem called a Generalised Eigenvalue Problem (GEP).

Imagine you are trying to find the lowest point in a valley. Instead of walking around blindly, you have a map that instantly tells you exactly which direction is down and how far you need to go. The GEP is that map. It guarantees that the computer finds the best possible answer within the group of solutions it is currently looking at. This avoids the "barren plateau" problem because the math is so structured that the computer never gets lost.
The Universal Rulebook:
The biggest breakthrough here is that this method doesn't care what the puzzle is. Whether you are solving a "Knapsack Problem" (packing a bag) or a "Traveling Salesperson Problem" (visiting cities), the framework uses the same basic steps. It takes the rules of the puzzle (the "hard constraints") and turns them into a single mathematical wall that the quantum computer cannot cross. This means you don't need to be a genius engineer to build a custom quantum circuit for every new problem; you just plug in the rules, and the framework handles the rest.

What They Found (and What They Didn't)

The researchers didn't just theorize this; they tested it. They ran simulations on a specific type of puzzle called the Knapsack Problem with 16 items. In these tests, their method successfully improved upon the best "greedy" (quick-and-dirty) classical solutions. For the hardest puzzles where the quick method failed, their quantum approach found solutions that were about 98% as good as the perfect answer, beating the classical method by a significant margin.

However, it is important to be clear about the limits. These results come from simulations on a classical computer that mimics a quantum one. They have not yet run this on a real, physical quantum computer in a lab. The paper proves mathematically that the method should work and that it avoids the "barren plateau" trap, but the real-world test on actual hardware is the next step.

Why It Matters

This paper is a big deal because it offers a "universal" way to handle strict rules in quantum computing. Before this, if you wanted to solve a hard, rule-bound problem on a quantum computer, you had to be an expert in that specific problem to design a custom solution. Now, the authors have shown a path where the computer can handle the rules automatically.

They also proved that even if the quantum computer is a bit "noisy" (which they all are right now), the method is robust enough to still find the best possible answer within its reach. It's like having a navigation system that works even if your car's GPS is slightly glitchy; it might not be perfect, but it will still get you to the right destination better than walking blind.

In short, this framework is a new, universal toolkit that lets quantum computers tackle the world's toughest puzzles without getting stuck, without needing custom-built engines for every job, and without losing their way in the fog. It's a step closer to turning the theoretical promise of quantum computing into a practical tool for solving real-world problems.

Technical Summary: One for All: A Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimisation Problems

1. Problem Statement

The paper addresses the challenge of solving NP-complete constrained combinatorial optimisation problems (CCOPs) on quantum hardware, specifically within the Noisy Intermediate-Scale Quantum (NISQ) era.

Current Variational Quantum Algorithms (VQAs), such as the Quantum Approximate Optimisation Algorithm (QAOA), face three primary hurdles when applied to hard-constrained problems:

Constraint Handling: Designing parameterised quantum circuits (PQCs) that strictly respect problem constraints is highly non-trivial and often requires problem-specific engineering of "mixers" and initial states.
Optimization Hardness: The classical parameter optimisation loop in VQAs is often as hard as the original problem and suffers from non-convex landscapes.
Barren Plateaus: Many VQAs suffer from vanishing gradients (barren plateaus), making convergence to even local optima difficult as the number of qubits increases.

While recent proposals like Quantum Conic Programming (QCP) have successfully mitigated barren plateaus and simplified parameter optimisation for unconstrained problems by mapping the task to a Generalised Eigenvalue Problem (GEP), they lacked a mechanism to handle hard constraints without resorting to soft-constraint penalties (which require careful hyperparameter tuning) or complex feasibility-preserving mixers.

2. Methodology

The authors propose One for All, a unified quantum-classical framework that generalises QCP to arbitrary hard-constrained problems. The methodology relies on the following components:

A. Parameterised Ansatz via Linear Combinations of Unitaries (LCU)

Instead of unitary evolution, the framework employs a non-unitary ansatz class constructed via Linear Combinations of Unitaries (LCU).

Ansatz: The state is defined as $|\psi\rangle = \frac{M_\alpha |\iota\rangle}{\|M_\alpha |\iota\rangle\|}$ , where $M_\alpha = \sum_{j=1}^\ell \alpha_j U_j$ . Here, $\{U_j\}$ are search unitaries, $|\iota\rangle$ is an initial state, and $\alpha \in \mathbb{C}^\ell$ are complex coefficients.
Feasibility Enforcement: Unlike soft-constraint approaches that penalise infeasible states in the objective function, this framework enforces hard constraints directly in the parameter optimisation. It requires the resulting state to be orthogonal to the infeasible subspace $S^\perp$ .

B. Sample Matrices and Measurement Protocol

To translate the quantum problem into a classical optimisation task, the authors define three sample matrices ( $F, G, H$ ) derived from the initial state and search unitaries:

$F$ : Encodes normalisation ( $\langle \psi | M_\alpha^\dagger M_\alpha | \psi \rangle$ ).
$G$ : Encodes feasibility ( $\langle \psi | M_\alpha^\dagger (1-P_S) M_\alpha | \psi \rangle$ , where $P_S$ projects onto the feasible subspace).
$H$ : Encodes the objective function ( $\langle \psi | M_\alpha^\dagger C M_\alpha | \psi \rangle$ ).

Key Innovation in Measurement: The paper details a specialised measurement protocol that does not require implementing the objective Hamiltonian $C$ or a quantum feasibility oracle on the QPU. Instead, it:

Uses LCU operations (controlled by ancilla qubits) to prepare superpositions of states like $(U_j \pm U_k)|\iota\rangle$ .
Measures bit strings in the computational basis.
Applies the classical objective function $c(b)$ and a classical feasibility oracle $d(b)$ to these sampled bit strings to estimate the matrix entries.

C. Reduction to Generalised Eigenvalue Problem (GEP)

The core theoretical contribution is the rigorous reduction of the doubly-constrained quadratic optimisation problem (minimising $H$ subject to $F=1$ and $G=0$ ) to a Generalised Eigenvalue Problem (GEP).

The authors prove that under minimal assumptions (linear independence of the generated states), the constrained optimisation is equivalent to finding the minimal generalised eigenvalue of a transformed pair of matrices.
This transformation fills gaps in previous derivations regarding degenerate cases and ensures the problem remains efficiently solvable on a classical CPU, avoiding the NP-hard parameter optimisation typical of standard VQAs.

D. Robustness to Noise

The framework is shown to remain valid even when the initial state is a mixed state (density operator) due to noise. The authors prove that the optimal solution to the resulting Semidefinite Program (SDP) is attained at a rank-one matrix, meaning the optimal solution can still be represented and implemented as a pure state update on the ancilla register, preserving the efficiency of the LCU implementation.

3. Key Contributions

Generalisation of QCP: The paper extends Quantum Conic Programming from unconstrained problems to arbitrary hard-constrained combinatorial optimisation problems without using soft constraints.
Unified Framework: It provides a "out-of-the-box" approach where the construction of the algorithm depends only on the classical objective function and a feasibility oracle, removing the need for problem-specific mixer design (a major bottleneck in QAOA).
Rigorous GEP Derivation: The authors provide a mathematically rigorous proof reducing the doubly-constrained parameter optimisation to a GEP, addressing and correcting gaps in prior literature regarding degenerate cases and strong duality.
Hardware-Efficient Protocol: A measurement protocol is introduced that avoids implementing complex Hamiltonians or oracles on the quantum device, relying instead on classical post-processing of sampled bit strings.
Noise Resilience: A proof is provided that the framework's parameterised ansatz class captures the optimum within its generated subcone even under the influence of noise (mixed states).

4. Results

The authors present a proof-of-concept numerical simulation on ten strongly correlated Pisinger knapsack instances ( $n=16$ items).

Performance: The method successfully improved upon a classical greedy baseline. For instances where the greedy solution was weak, the quantum optimiser converged to feasible superpositions with approximation ratios up to 0.98, gaining up to 0.09 over the greedy solution.
Mechanism: These gains were achieved through coherent superpositions of item exchanges that single-channel classical updates could not realise.
Implementation Probability: The probability of successfully implementing the LCU step remained within a factor of six of the warm-start value ( $2^{-16}$ ), demonstrating that the method does not suffer from exponentially vanishing success probabilities in this regime.
Convergence: The approximation ratio never fell below the greedy value, and the implementation probability decayed slowly as weights spread over more constituents.

5. Significance and Claims

The paper claims to establish a unified framework for addressing arbitrarily-constrained combinatorial optimisation problems on quantum devices with short to medium coherence times.

Mitigation of Barren Plateaus: By utilising non-unitary parameterised gates and mapping the optimisation to a GEP, the framework inherits the favourable property of preventing barren plateaus and avoiding NP-hard parameter optimisation.
Conceptual Independence from QAOA: While inspired by QAOA, the framework is conceptually independent. It restores the "out-of-the-box" applicability lost in generalised QAOA (which requires hand-crafted mixers) by integrating the classical objective and feasibility oracle directly into the optimisation loop.
Scalability: The approach is designed to be applicable to far-term devices, potentially outsourcing suitable subroutines to CPUs, and holds true for arbitrarily-constrained problems.

The authors conclude that while the current work provides a theoretical foundation and a proof of concept via simulation, further theoretical strengthening and extensive numerical experiments on larger problems (such as the Travelling Salesperson Problem) are necessary to fully gauge the framework's performance.