⚛️ quantum physics

Optimized QUBO formulation methods for quantum computing

This paper introduces novel iterative quadratic polynomial and master-satellite methods to drastically reduce the variable count in QUBO formulations for NISQ devices, demonstrating their superior efficiency over standard approaches on the NP-hard Max-Profit Balance Settlement problem using D-Wave quantum annealers.

Original authors: Dario De Santis, Salvatore Tirone, Stefano Marmi, Vittorio Giovannetti

Published 2026-02-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dario De Santis, Salvatore Tirone, Stefano Marmi, Vittorio Giovannetti

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, intricate jigsaw puzzle. But there's a catch: you are trying to solve it on a tiny, fragile table that can only hold a few pieces at a time. If you try to force too many pieces onto the table, the whole thing collapses, and you can't find the picture.

This is the current situation with Quantum Computers (specifically the ones we have right now, called NISQ devices). They are powerful, but they are "noisy" and have very limited space (qubits) to work with.

The paper you're asking about is like a brilliant new folding technique for that puzzle. It shows how to shrink the puzzle down so it fits on the tiny table without losing any of the picture's details.

Here is the breakdown of their discovery, using simple analogies:

1. The Problem: The "Slack" Overload

To make a real-world problem (like optimizing a bank's payments) work on a quantum computer, scientists have to translate it into a specific language called QUBO (Quadratic Unconstrained Binary Optimization). Think of QUBO as a strict, rigid grid where every piece must fit perfectly.

However, real-world problems have rules (constraints). For example: "You can't spend more money than you have," or "You must receive a payment before you send one."

The Old Way: To force the quantum computer to follow these rules, scientists used to add "helper pieces" called Slack Variables.
- The Analogy: Imagine you are trying to fit a large sofa (the rule) into a small room (the quantum computer). The old method was to build a giant scaffolding around the sofa just to hold it in place. This scaffolding took up so much space that the room was full, and you couldn't fit the sofa in at all.
- The Result: For complex problems, the "scaffolding" (slack variables) became 10 times bigger than the actual problem. The quantum computer ran out of space immediately.

2. The Solution: Two New Tools

The authors, Dario De Santis and his team, invented two new methods to build a much smaller, smarter scaffolding. They call them the Iterative Quadratic Polynomial (IQP) and the Master-Satellite methods.

Tool A: The "Smart Sculptor" (Iterative Quadratic Polynomial)

Instead of building a giant scaffolding for every single rule, this tool acts like a sculptor who carves the rule directly into the shape of the sofa.

How it works: It looks at a rule and asks, "What is the absolute minimum amount of 'helper' material I need to make this rule work?"
The Magic: It often finds that for simple rules, you need zero extra pieces. For slightly complex rules, you only need one or two. It stops adding "slack" the moment the rule is satisfied.

Tool B: The "Boss and the Sidekick" (Master-Satellite Method)

Sometimes, you have multiple rules that apply to the same group of variables (like a group of friends who all need to follow the same schedule).

The Old Way: You treated every rule as a separate, heavy boss, requiring its own massive scaffolding.
The New Way: You pick one rule to be the "Master" and the others to be "Satellites."
- The Master is enforced strictly for everyone.
- The Satellites only need to be enforced if the Master is already happy.
- The Analogy: Imagine a bouncer at a club (the Master). If you don't have a ticket, you can't get in, so the security guard doesn't even need to check your ID (the Satellite rule). By realizing the Satellite rule only matters after the Master rule is passed, you save a huge amount of security checks (slack variables).

3. The Real-World Test: The "Bank Transfer" Puzzle

To prove this works, they applied it to a real financial problem called Max-Profit Balance Settlement (MPBS).

The Scenario: Imagine a bank has thousands of people who owe each other money. The goal is to cancel out as many debts as possible so everyone ends up with the right amount of money, without anyone going into the red.
The Challenge: This is a "NP-Hard" problem, meaning it's incredibly difficult to solve.
The Result:
- Using the Old Method, the "scaffolding" was so huge that the quantum computer could barely handle small examples.
- Using the New Method, they reduced the number of required "helper pieces" by about 90%.
- The Metaphor: They turned a puzzle that required a warehouse-sized table into one that fits on a coffee table.

4. The Outcome: Faster and Better

They tested this on two different quantum computers (D-Wave machines).

Success Rate: When using their new "folding technique," the quantum computers found the correct answer 7 to 184 times more often than when using the old method.
Scalability: As the problems got bigger, the old method's success rate crashed to near zero. The new method stayed strong, proving it can handle much larger, real-world problems.

Summary

This paper is a breakthrough in efficiency. It doesn't make the quantum computer faster in terms of speed; instead, it makes the problem smaller so the computer can actually solve it.

Before: Trying to fit a whale into a bathtub by building a giant tank around it.
After: Realizing the whale can actually fit in the bathtub if you just squeeze it into the right shape, removing all the unnecessary water (slack variables).

This allows us to use today's imperfect quantum computers to solve real, valuable problems in finance and logistics that were previously impossible to tackle.

1. Problem Statement

The paper addresses a critical bottleneck in solving combinatorial optimization problems on Noisy Intermediate-Scale Quantum (NISQ) devices, specifically quantum annealers.

The Challenge: Many NP-hard problems (e.g., Max-Profit Balance Settlement) must be reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems to run on these devices.
The Bottleneck: Standard QUBO reformulation techniques require a large number of slack variables to enforce constraints (especially inequality constraints).
- Slack variables increase the total number of logical variables, requiring more physical qubits.
- They often necessitate high connectivity between variables, which exceeds the limited connectivity of current quantum hardware (e.g., D-Wave's Pegasus or Zephyr topologies).
- This limits the size of problems that can be solved and degrades solution quality as problem size increases.
The Goal: To drastically reduce the number of slack variables required for QUBO reformulations without approximating the original problem or solving preliminary QUBOs, thereby enabling the solution of larger, real-world instances on NISQ devices.

2. Methodology

The authors introduce two novel, independent techniques that can be used separately or in conjunction (referred to as IQPMS):

A. Iterative Quadratic Polynomial (IQP) Method

Concept: Instead of using the standard method of converting inequalities to equalities via a linear sum of slack variables (which requires $\lceil \log_2(\text{range}) \rceil$ variables), the IQP method constructs a generic quadratic polynomial $P(x, s)$ directly.
Mechanism:
- The method seeks coefficients for a quadratic polynomial such that $P(x, s) = 0$ when constraints are satisfied and $P(x, s) \le -1$ when violated.
- It uses an iterative approach: It starts with zero slack variables. If a solution for the polynomial coefficients cannot be found (due to insufficient degrees of freedom), it adds one slack variable and re-evaluates.
- Key Insight: Inequality constraints are less restrictive than equality constraints. The method exploits this by requiring $P(x, s) \le -1$ for violations (allowing different penalty values for different slack configurations) rather than a fixed value, often allowing the constraint to be satisfied with fewer or zero slack variables.
Applicability: Particularly effective for constraints defined over a small number of binary variables (e.g., local node constraints). It works for both linear and non-linear constraints, and integer or non-integer parameters.

B. Master-Satellite (MS) Method

Concept: This method exploits the synergy between multiple constraints that share the same set of binary variables.
Mechanism:
- Constraints are divided into Master and Satellite.
- Master Constraints: Enforced for all possible combinations of binary variables.
- Satellite Constraints: Enforced only for combinations that already satisfy the Master constraints.
- Penalty Tuning: Because satellite constraints are not enforced when the Master is violated, they may accidentally provide positive incentives (reducing the penalty) for invalid states. The authors introduce a relative multiplier ( $\lambda_{MC} > 1$ ) for the Master constraint to amplify its penalty, ensuring that even if a satellite constraint provides an accidental incentive, the net penalty for violating the Master remains negative.
Concatenation: For three or more constraints, a "concatenated" hierarchy is used (e.g., $C_1$ is master to $C_2$ , $C_1 \land C_2$ is master to $C_3$ ), further reducing the number of sub-constraints that need to be satisfied.

C. Application to Locally-Constrained Problems

The authors apply these methods to Locally-Constrained Optimization Problems, where constraints are defined node-by-node (e.g., constraints on incoming/outgoing arcs for a specific node in a graph). This structure allows the IQP and MS methods to be applied efficiently to each node independently.

3. Case Study: Max-Profit Balance Settlement (MPBS)

The authors validate their methods using the MPBS problem, an NP-hard financial optimization problem involving settling receivables in a network.

Constraints:
1. CAP/FLOOR: The net balance of each user must remain within a specific range $[FL, CAP]$.
2. IN/OUT: If a user participates in the settlement, they must have at least one incoming and one outgoing transaction.
Standard Approach: Requires slack variables proportional to the range of the CAP/FLOOR constraint (often $\sim 16+$ variables per node for realistic financial data) and logarithmic variables for IN/OUT.
Proposed Approach (IQPMS):
- IN/OUT: Treated as the Master constraint. For nodes with $\le 4$ arcs, 0 slack variables are needed. For 5 arcs, only 1 or 2 are needed.
- CAP/FLOOR: Treated as the Satellite constraint. Since it is only enforced when IN/OUT is satisfied, the range of values to cover is drastically reduced.
- Result: For nodes with $\le 4$ arcs, 0 slack variables are needed for CAP/FLOOR. For 5 arcs, only 0–2 are needed.

4. Key Results

The authors tested their approach on 20 instances of MPBS using two D-Wave quantum annealers: Advantage_system4.1 (Adv1) and the next-gen prototype Advantage2_prototype1.1 (Adv2).

Slack Variable Reduction:
- The IQPMS methods reduced the number of slack variables by approximately 90% compared to standard methods.
- For the largest instances ( $N=18$ arcs), the standard method required ~90 QUBO variables, while IQPMS required only ~28.
Qubit Efficiency:
- Standard method: Required $\approx 10.5$ physical qubits per arc added to the graph.
- IQPMS method: Required $\approx 2$ physical qubits per arc.
Solution Quality (Success Rates):
- The success rate of finding the optimal solution using IQPMS was significantly higher than the standard method.
- Gain Factor: The ratio of successful runs (IQPMS vs. Standard) ranged from 7x (smallest instances on Adv1) to 184x (largest instances on Adv2).
- Unlike the standard method, where success rates dropped rapidly as problem size increased, the IQPMS method maintained high success rates even for larger inputs.
Hardware Comparison: The newer Advantage2 prototype (higher connectivity, lower noise) outperformed Advantage_system4.1, but the relative improvement provided by the IQPMS formulation was consistent across both devices.

5. Significance and Conclusion

Scalability: The work demonstrates that by optimizing the formulation of the problem (reducing slack variables and connectivity requirements), current NISQ devices can solve significantly larger instances of NP-hard problems than previously thought possible.
Hardware Agnosticism: The method improves performance on both current and next-generation annealers by reducing the burden on qubit connectivity and count.
No Approximation: Unlike other methods (e.g., ADMM or approximate rescaling), this approach provides an exact reformulation of the original problem without approximations or preliminary classical solving steps.
Future Outlook: The authors suggest these techniques are applicable to a wide range of locally-constrained problems (e.g., Knapsack variants, Subset Sum) and could be combined with hybrid solvers or variable reduction techniques to push the boundaries of near-term quantum optimization.

In summary, the paper provides a paradigm shift in QUBO formulation, moving from "brute-force" slack variable expansion to a sophisticated, iterative, and hierarchical constraint enforcement strategy that unlocks the potential of current quantum hardware for real-world financial optimization.