IF-QAOA: A Faster Approach to Constrained Quantum Optimization

We’re excited to introduce Indicator Function QAOA (IF-QAOA), an efficient approach for handling inequality constraints in quantum optimization. Our recent research demonstrates that IF-QAOA significantly outperforms traditional penalty-based methods for complex optimization problems like the Knapsack problem. By eliminating penalty terms and leveraging quantum oracle techniques, IF-QAOA provides more accurate results while using comparable quantum resources. These findings represent a major step toward practical quantum utility for real-world optimization challenges faced by industries across all domains.

Motivation: Driven by Real-World Problems

Our team approaches quantum computing from a problem-first perspective. Rather than developing technologies in search of applications, we identify real-world industrial challenges and build quantum solutions specifically designed to address them.

Constrained optimization problems appear everywhere in industry—from maximizing manufacturing efficiency while staying within resource limits to optimizing investment portfolios within risk parameters. These problems are notoriously difficult to solve classically, especially as they scale up.

The paper we’re sharing today marks the first step in our ongoing work to make quantum optimization practical for these industry use cases. In the coming weeks, we’ll share more results from our research, demonstrating how these techniques can be applied to real business problems.

Quantum Optimization and the Challenge of Constraints

Most real-world optimization problems come with constraints. Think of a logistics company trying to maximize delivery values while respecting vehicle weight limits—a classic Knapsack problem. Quantum algorithms like QAOA (Quantum Approximate Optimization Algorithm) are inherently working on unconstrained optimization problems. Thus, the constraint—respecting the vehicle weight limit—has traditionally been addressed by penalizing constraint violations.

But, penalty methods face some significant challenges: In the case of Knapsack constraints, they often require extra slack variables that expand the search space and increase computational complexity. Furthermore, the common implementation through quadratic penalties skews the energy spectrum, increasing the difficulty of finding ideal solutions.

IF-QAOA takes a different approach to constraint handling. Instead of adding penalties, we use a quantum oracle technique to selectively apply the cost function only to solutions that satisfy all constraints. This creates a step-function effect that cleanly separates feasible from infeasible solutions.

IF-QAOA Explained

IF-QAOA is an extension to the well-known unconstrained QAOA algorithm, which tackles optimization problems by a alternating application of cost and mixer layer operations.

A single cost function layer of IF-QAOA is constructed by computing constraint satisfaction information onto an ancillary qubit, called indicator qubit. Subsequently, the state of this qubit controls the application of the normal cost function, meaning only feasible solution candidates will get a phase in this step. Finally we uncompute the indicator qubit, to reuse the ancillary variables in the next iteration.

Mathematically, this approach implements the objective function: \tilde{f}(x) = f(x)\Theta[g(x)], where \Theta is the Heaviside step function that equals 1 when g(x) \geq 0 (constraint satisfied) and 0 otherwise, assuming f(x) \leq 0.

The technical implementation uses Quantum Phase Estimation to evaluate constraints without requiring extra optimization variables but ancillary qubits. This maintains the original problem structure and enables more effective optimization.

Impressive Results

Our numerical experiments on 1152 Knapsack problems demonstrate significant advantages of IF-QAOA compared to penalty methods in simulation:

• ✅ Higher Solution Quality: We measure Solution Quality in terms of RAAR (Random-Adjusted Approximation Ratio, 1 → optimal solution, 0 → random sampling). At 16 layers, IF-QAOA achieves much higher solution quality (RAAR > 0.8) compared to penalty methods (RAAR ≈ 0.4-0.6) across all tested problem sizes. With increasing QAOA layers IF-QAOA approaches near perfect solution quality in comparison to the penalty methods.
• ⚡ Faster Solution Times: The Time-to-Solution (TTS) is measured from estimating how many Circuit Layer Operations (CLOPS) are required to obtain the optimal solution once. This holistic figure of merit contains both solution quality and circuit complexity. In 82% of the tested Knapsack Instances, IF-QAOA arrived at solutions faster, with the share increasing as the problem size grows.
• 📈 Better Scaling: The TTS for IF-QAOA scales significantly more favorable ($\propto 1.30^N$) than penalty methods ($\propto 1.63^N$), marking a distinctive advantage as the problems scale.

Moving Forward

IF-QAOA represents a significant advancement in quantum optimization, offering a cleaner, more effective approach to handling inequality constraints. By preserving the original energy spectrum of the problem, our method focuses the quantum algorithm on finding high-quality solutions rather than just satisfying constraints.

As part of our research, we have also developed an approximate version within for non-resolvable constraints with limited ancillary qubits. Our results show that the method delivers excellent performance across a wide range of problem instances even with a modest number of ancillary qubits.

In the coming weeks, we’ll share more exciting results, including applications to multi-constraint problems and implementations on real quantum hardware. Stay tuned for more updates as we continue translating real-world problems into quantum solutions—step by step.

This work was supported by the German Federal Ministry of Research, Technology and Space (BMFTR) under the funding program “Förderprogramm Quantentechnologien – von den Grundlagen zum Markt” (funding program quantum technologies — from basic research to market), project QuCUN.

About Aqarios

Aqarios, headquartered in Munich, Germany, is a leading provider of quantum computing solutions across industries such as energy, aerospace, logistics, finance, manufacturing and many more. The company delivers advanced quantum software that focuses on optimization, machine learning, and simulation, offering practical tools that address critical business challenges. Aqarios has collaborated with globally recognized organizations to deliver tailored quantum solutions that drive efficiency and innovation.

Founded in 2021 by three professors and seasoned business professionals, Aqarios is a spin-off from the QAR-Lab at LMU Munich, a globally renowned hub for quantum computing research that ranks among the world’s top quantum computing institutes. With nearly a decade of experience in quantum applications, Aqarios is at the forefront of quantum innovation, leveraging its deep expertise to bridge the gap between theoretical quantum research and real-world applications.