Quantum optimization beyond QUBO for industrial logistics and scheduling

This paper investigates Higher-Order Unconstrained Binary Optimization (HUBO) formulations for industrial logistics and scheduling, demonstrating that while they offer more compact binary encodings with reduced qubit requirements compared to standard QUBO models, their practical implementation on current hardware is limited by increased circuit depth, suggesting that hybrid quantum-classical workflows and early fault-tolerant systems are the most viable paths forward.

The Gist

Imagine you are trying to solve a massive, complex puzzle. In the world of industrial logistics—like figuring out how to deliver thousands of packages or how to assemble cars on a factory line—this puzzle is incredibly difficult. For a long time, scientists have tried to use Quantum Computers to solve these puzzles faster than regular computers.

However, there's a catch: most quantum computers today are like "square pegs" trying to fit into "round holes." They are designed to solve problems written in a specific, simple language called QUBO (Quadratic Unconstrained Binary Optimization). Think of QUBO as a language where you can only describe relationships between two things at a time (like "If A is here, then B must be there").

But real-world problems are messy. They often involve complex rules where three, four, or even more things depend on each other simultaneously. Trying to force these complex rules into the simple "two-at-a-time" QUBO language is like trying to describe a symphony by only talking about pairs of notes. It works, but you have to break the music down so much that the puzzle becomes huge, requiring more pieces (qubits) than the quantum computer has available.

The New Approach: Speaking the "Native" Language

This paper proposes a different strategy. Instead of forcing the complex problem into the simple QUBO language, the researchers suggest using HUBO (Higher-Order Unconstrained Binary Optimization).

The Analogy:
Imagine you are packing a suitcase.

• The QUBO way: You have to write a note for every single pair of items to see if they fit together. If you have 100 items, you have to write thousands of notes. This takes up a lot of space (memory/qubits).
• The HUBO way: You write a single, slightly more complex note that says, "These five items fit together perfectly." This is much more compact. You need far fewer notes (fewer qubits) to describe the same suitcase.

The researchers applied this "HUBO" approach to three real-world industrial scenarios:

1. Windbreakers and Surfers (QUEST): Matching cars driving on a highway so one car can draft behind another to save fuel.
2. Delivery Trucks (CVRP): Figuring out the best routes for a fleet of trucks with limited cargo space to deliver goods to many customers.
3. Car Assembly Lines: Deciding the order in which cars with different options (sunroofs, leather seats) should go down the line to avoid bottlenecks.

The Trade-Off: Saving Space vs. Building a Taller Tower

The paper highlights a crucial trade-off, like choosing between a wide, flat building and a tall, narrow skyscraper.

• The Benefit (Fewer Qubits): By using HUBO, the researchers successfully shrank the size of the puzzle. They needed significantly fewer "quantum bits" (qubits) to represent the problem. This is great because current quantum computers are very small and have very few qubits.
• The Cost (Deeper Circuits): However, to make that "single complex note" work, the quantum computer has to perform a much more complicated dance. In quantum terms, this means the "circuit depth" (the number of steps the computer must take) gets much deeper.

The Metaphor:
Think of the quantum computer as a tightrope walker.

• QUBO is a short, wide tightrope. It's easy to balance on, but you need a very long rope (many qubits) to reach the other side.
• HUBO is a very short, narrow tightrope. You need very little rope (few qubits), but it is incredibly difficult to balance on because it requires complex, high-speed moves (deep circuits).

What the Results Show

The researchers tested these ideas using simulations and classical computers to see how well the HUBO approach works.

1. It Works (in Theory): For small problems, the HUBO method successfully found the best solutions. It proved that you can describe these complex logistics problems much more efficiently in terms of the number of "ingredients" (qubits) needed.
2. The Hardware Bottleneck: The problem is that current quantum computers are "noisy." They are like a tightrope walker trying to balance in a hurricane. Because the HUBO method requires a longer, more complex sequence of steps (a deeper circuit), the noise causes the computer to lose its balance before it finishes the puzzle.
3. The Verdict:
   • Today (Noisy Era): The "tall tower" (HUBO) is too shaky for current hardware. The "wide building" (QUBO) is actually easier to build right now, even though it takes up more space.
   • Tomorrow (Fault-Tolerant Era): The paper suggests that once we have better, error-corrected quantum computers (the "fault-tolerant" regime), the HUBO approach will likely win. These future machines will be stable enough to handle the complex, deep circuits required by HUBO, allowing us to solve much larger problems with fewer qubits.

The Hybrid Solution

Since we can't wait for perfect future computers, the paper suggests a "hybrid" approach for the near future. Instead of trying to solve the whole giant puzzle on the quantum computer at once, we break the puzzle into small, manageable chunks. We use classical computers to handle the big picture and the easy parts, and we send just the tiny, difficult chunks to the quantum computer to refine.

In Summary:
This paper argues that while the "compact" HUBO language is the most efficient way to describe complex industrial logistics, current quantum computers are too fragile to handle the complexity it requires. We need to wait for better hardware or use a mix of classical and quantum computing to make this powerful method practical.

Technical Summary

Technical Summary: Quantum Optimization Beyond QUBO for Industrial Logistics and Scheduling

Problem Statement
Industrial scheduling and transport routing problems are increasingly complex, often possessing natural mathematical structures that lead to Higher-Order Unconstrained Binary Optimization (HUBO) formulations rather than purely quadratic ones. While the field of quantum optimization has predominantly focused on Quadratic Unconstrained Binary Optimization (QUBO) due to its native mapping to Ising Hamiltonians and compatibility with current quantum annealers, this focus imposes significant limitations. Reducing HUBO problems to QUBO via auxiliary variables often inflates problem size (qubit count), obscuring key dependencies and failing to faithfully represent intricate operational constraints. Conversely, while digital quantum algorithms like the Quantum Approximate Optimization Algorithm (QAOA) can theoretically handle higher-order interactions, near-term implementations on noisy hardware are often depth-limited as interaction orders increase. This paper investigates the trade-off between the representational compactness of HUBO formulations and their implementation costs on current and emerging quantum hardware.

Methodology
The authors propose and analyze HUBO formulations for three representative industrial use cases:

1. QUEST (Quantum-Enhanced Shared Transportation): A vehicle matching problem where "breakers" are paired with "surfers" to minimize aerodynamic drag and time/speed mismatches.
2. CVRP (Capacitated Vehicle Routing Problem): A fleet routing problem with capacity constraints, extending the Traveling Salesman Problem.
3. Automotive Assembly Scheduling: A car sequencing problem involving gap, group, and storage lane constraints on an assembly line.

For each use case, the authors reformulate the problem as a HUBO using compact binary encodings (logarithmic scaling in variables) rather than standard one-hot encodings (linear scaling). These formulations are validated using classical solvers, including Simulated Annealing (SA) and Memetic Tabu Search (MTS), and benchmarked against Integer Linear Programming (ILP) and brute-force solutions.

To assess quantum feasibility, the authors employ the Bias-Field Digitized Counterdiabatic Quantum Optimization (BF-DCQO) algorithm. This protocol extends standard DCQO by introducing an iterative feedback mechanism using longitudinal bias fields derived from previous measurement outcomes to guide the system toward lower-energy configurations. The authors estimate resource requirements (qubit count, two-qubit gate count, circuit depth) and circuit fidelity under various hardware connectivity assumptions (all-to-all, heavy-hex, square-lattice) and noise models.

Key Contributions

• Formulation of HUBO Models: The paper provides explicit HUBO formulations for QUEST, CVRP, and automotive scheduling, demonstrating how compact binary encodings reduce the number of binary variables from $O(N)$ or $O(N^2)$ to $O(N \log N)$.
• Trade-off Analysis: The work systematically highlights the central trade-off: HUBO formulations significantly reduce qubit requirements (qubit scaling) but introduce higher-order interaction terms that necessitate deeper circuits with more two-qubit gates.
• Resource and Scalability Analysis: The authors provide detailed estimates of circuit fidelity and runtime for BF-DCOQ. They demonstrate that while HUBO reduces the qubit footprint, the exponential decay of circuit fidelity with increasing two-qubit gate counts poses a critical bottleneck for current noisy intermediate-scale quantum (NISQ) devices.
• Hybrid Workflow Proposal: For large-scale instances (e.g., automotive scheduling) where full quantum execution is infeasible, the paper proposes and evaluates a hybrid rolling-horizon workflow. This approach decomposes the global problem into localized subproblems solvable by classical or near-term quantum solvers while preserving the higher-order structure of the full objective.

Results

• QUEST and CVRP Validation: For small instances (up to 6 breakers/surfers for QUEST and small CVRP instances), BF-DCQO simulations recover optimal solutions, validating the HUBO encoding. However, as problem size increases, the approximation ratio for BF-DCQO degrades faster than classical Simulated Annealing on quadratized HUBO, consistent with the rapid increase in circuit complexity.
• Hardware Constraints: The analysis reveals that for current hardware (e.g., IBM heavy-hex or square-lattice), QUBO encodings often remain more feasible due to lower two-qubit gate counts, despite requiring more qubits. HUBO formulations only become competitive in terms of gate counts on architectures with all-to-all connectivity (e.g., trapped-ion) and even then, are limited to very small instances (e.g., 4 customers in CVRP) due to coherence time and error accumulation.
• Scalability Limits: For a representative large-scale CVRP instance (100 customers), the authors estimate that a faithful implementation of DCQO circuits would require average two-qubit gate error rates below $10^{-10}$, a level only achievable in the logical-qubit regime enabled by quantum error correction.
• Scheduling Performance: In the automotive scheduling case, classical solvers (MTS and ILP) were used to benchmark the HUBO formulation. MTS effectively reduced FIFO (First-In-First-Out) violations but struggled with higher-order group constraints as problem size grew. The hybrid rolling-horizon approach using SA provided a balanced reduction in both local and global violations.

Significance and Claims
The paper modestly claims that its primary contribution is not the demonstration of quantum advantage on industrial-scale instances, but rather a clarification of when higher-order formulations offer a meaningful representational advantage and how that advantage is constrained by quantum resource requirements.

The authors conclude that:

1. HUBO vs. QUBO: HUBO formulations offer superior qubit scaling, making them potentially more attractive than QUBO in early fault-tolerant settings where qubit counts are limited but gate fidelities are high.
2. Current Limitations: Practical implementation on current NISQ hardware is constrained by gate fidelity, coherence times, and circuit depth. The increased two-qubit gate requirements of HUBO often outweigh the benefits of reduced qubit counts on present-day devices.
3. Future Pathways: The most plausible setting for practical use of these formulations is a sequential hybrid quantum-classical workflow. In this paradigm, quantum routines act as refinement steps for localized subproblems within a predominantly classical optimization pipeline. This approach leverages the favorable qubit scaling of HUBO while mitigating the prohibitive runtimes and error accumulation associated with end-to-end quantum optimization, even in early fault-tolerant regimes.

The work underscores that the viability of quantum optimization in industry depends on aligning problem structure with hardware capabilities, suggesting that hybrid strategies are essential for bridging the gap between theoretical HUBO advantages and practical implementation.