Resource-Efficient Quantum Optimization via Higher-Order Encoding

This paper demonstrates that Higher-Order Unconstrained Binary Optimization (HUBO) offers a significantly more resource-efficient alternative to traditional QUBO formulations for combinatorial optimization problems, achieving substantial reductions in qubit and CNOT gate counts while providing an open-source library to facilitate its adoption on near-term quantum devices.

The Gist

Imagine you are trying to solve a massive, complicated puzzle. In the world of quantum computing, this puzzle is called a Combinatorial Optimization Problem. It's like trying to figure out the perfect way to assign airplanes to airport gates, color a map so no touching countries share a color, or schedule a factory's production line to save the most money.

For a long time, scientists have tried to solve these puzzles using a specific method called QUBO (Quadratic Unconstrained Binary Optimization). Think of QUBO as a very strict, rigid way of translating your puzzle into a language a quantum computer understands.

The Problem with the Old Way (QUBO)

The paper argues that the QUBO method is like trying to pack a suitcase by forcing every single item into its own individual, oversized box.

• Too many boxes (Qubits): If you have a variable that can take 10 different values (like 10 different airport gates), QUBO forces you to use 10 separate "boxes" (quantum bits or qubits) just to represent that one choice.
• Too much glue (Penalty Terms): To make sure the computer doesn't pick two boxes at once (which would be a mistake), you have to add heavy "glue" called penalty terms. This glue makes the instructions (the quantum circuit) incredibly long and complex.
• The Result: The quantum computer gets overwhelmed. It needs too many parts (qubits) and has to perform too many complicated moves (gates) just to solve a problem that isn't that big.

The New Solution: HUBO

The authors of this paper introduce a smarter way called HUBO (Higher-Order Unconstrained Binary Optimization).

Think of HUBO as packing that same suitcase using compression bags. Instead of giving every item its own huge box, you use a compact binary code (like a digital zip file) to represent the choices.

• Fewer boxes: If you have 10 options, HUBO doesn't need 10 boxes. It only needs about 4 boxes (because $2^4 = 16$, which covers 10). It uses the natural "binary" language of computers much more efficiently.
• No extra glue: Because the encoding is so smart, the computer naturally understands that it can only pick one value at a time. You don't need to add those heavy, expensive penalty terms to stop it from making mistakes.
• The Result: The instructions become much shorter, and the quantum computer needs far fewer parts to do the job.

What They Actually Did

The researchers didn't just talk about this; they tested it on three real-world types of puzzles:

1. Gate Assignment (GAP): Assigning planes to airport gates to minimize walking time for passengers.
2. Graph Coloring (MkCS): Coloring a map so no neighbors share a color.
3. Integer Programming (IP): A general math problem for optimizing resources.

They compared the old "QUBO" method against their new "HUBO" method using a popular quantum algorithm called QAOA.

The Results: A Massive Win

The findings were dramatic. By switching to HUBO:

• Fewer Parts Needed: They needed significantly fewer qubits (the basic building blocks of the computer).
• Drastically Fewer Moves: The most important finding was in the number of "CNOT gates" (a specific type of move quantum computers have to make). The HUBO method reduced the number of these moves by at least 89.6% across all tests. In some cases, it was nearly a 100% reduction.
• Better Solutions: Not only was it cheaper to run, but the HUBO method also found better answers to the puzzles than the QUBO method did, even when both were given the same amount of time to run.

The Takeaway

The paper concludes that for the quantum computers we have today (and the ones coming soon), the old QUBO method is too heavy and wasteful. The new HUBO method is a "lightweight" alternative that fits better on current hardware.

To help everyone else use this, the authors also released a free, open-source software tool (a Python library called PyHUBO) that automatically translates these complex problems into the efficient HUBO format, so other scientists and engineers can start using this resource-saving method immediately.

In short: They found a way to shrink the quantum instructions for solving complex puzzles, making it much more likely that we can actually solve real-world problems on today's quantum computers.

Technical Summary

Technical Summary: Resource-Efficient Quantum Optimization via Higher-Order Encoding

Problem Statement
Combinatorial optimization problems (COPs) are central to fields ranging from logistics to computational biology but are often NP-hard, making them computationally intractable for classical solvers as problem sizes grow. Quantum algorithms, particularly the Quantum Approximate Optimization Algorithm (QAOA), offer a potential pathway to address these challenges. However, current quantum approaches are frequently bottlenecked by the resource demands of Quadratic Unconstrained Binary Optimization (QUBO) formulations. Standard QUBO encodings, such as One-Hot encoding, require a number of qubits linear in both the number of variables ($n$) and the number of possible values per variable ($m$), resulting in $n \times m$ qubits. Furthermore, enforcing constraints in QUBO typically necessitates large penalty terms, which increase circuit depth and the count of two-qubit CNOT gates, rendering many practical problems infeasible on near-term quantum hardware.

Methodology
The authors propose a systematic framework utilizing Higher-Order Unconstrained Binary Optimization (HUBO) to mitigate these resource constraints. The methodology involves three primary components:

1. Binary Encoding vs. One-Hot Encoding: Instead of using One-Hot encoding (where each variable-value pair is a distinct qubit), the authors employ a Binary encoding. Here, each variable $i$ is represented by a compact binary register of $d = \lceil \log_2(m) \rceil$ bits. This reduces the qubit requirement from $n \times m$ to $n \times \lceil \log_2(m) \rceil$.
2. HUBO Hamiltonian Construction: The authors demonstrate that this binary encoding naturally leads to HUBO Hamiltonians containing higher-order interaction terms (up to order $2 \times d$). Unlike QUBO, which requires penalty terms to enforce the "one-hot" constraint (that a variable takes only one value), the binary encoding inherently respects the single-value assignment. Constraints (e.g., $s_i \neq s_j$) are incorporated directly into the Hamiltonian or via penalty terms that do not require expanding the variable space.
3. Circuit Compilation: While higher-order terms formally imply multi-qubit interactions, the authors show that these can be compiled entirely into standard single- and two-qubit gates. They utilize a Gray-code based circuit synthesis (following Welch et al.) to implement the cost unitary $e^{-i\gamma \hat{H}_C}$. This approach minimizes redundant operations by leveraging parity states generated for one term to assist in constructing others, ensuring the asymptotic CNOT gate count scales as $O(n^2 m^2)$, comparable to QUBO but with significantly lower constant factors in practice.

The authors also introduce PyHUBO, an open-source Python library that automates the construction of HUBO Hamiltonians and the calculation of their coefficients using Walsh-Hadamard transforms, ensuring numerical complexity scales polynomially with problem size.

Key Contributions

• Systematic Framework: A general method for mapping COPs to HUBO Hamiltonians using binary encodings, applicable to problems with one-hot or related constraints.
• Resource Reduction: A demonstration that HUBO formulations significantly reduce qubit counts and, crucially, the total number of CNOT gates required for QAOA execution compared to QUBO.
• Software Tool: The release of PyHUBO to facilitate the adoption of HUBO models in the quantum community.
• Benchmarking: Comprehensive evaluation across three distinct COP classes: Gate Assignment Problem (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP).

Results
The authors benchmarked QAOA using both QUBO and HUBO encodings on the three selected problem classes. The results indicate substantial resource savings for HUBO:

• Qubit Efficiency: HUBO reduces qubit requirements from $O(nm)$ to $O(n \log m)$.
• Gate Count Reduction: For all tested instances, HUBO reduced the total CNOT gate count by at least 89.6%. In specific cases, such as Integer Programming benchmarks, reductions reached up to 97.1%.
• Solution Quality: For a fixed number of QAOA layers, HUBO-QAOA consistently achieved better approximation ratios (closer to the optimal solution) than QUBO-QAOA. For example, in the GAP benchmark, HUBO achieved an average objective value of 12.1 minutes versus 15.8 minutes for QUBO.
• Convergence: HUBO-QAOA reached target approximation ratios with significantly fewer total gates. In the IP benchmark, HUBO achieved a target ratio of 0.60 with 1 layer, whereas QUBO required 10 layers, resulting in QUBO consuming 31.6 times more CNOT gates and 24.5 times more RZ gates.
• Scalability: The resource advantage of HUBO persisted and often increased as problem sizes grew, with HUBO remaining tractable for problem sizes where QUBO-QAOA became computationally infeasible due to excessive resource requirements.

Significance
The paper argues that HUBO formulations offer a practical alternative for quantum optimization on near-term devices. Contrary to the intuition that higher-order interactions would increase hardware demands, the authors show that the elimination of penalty terms and the compression of variable representation lead to a net reduction in circuit complexity. By significantly lowering qubit and CNOT requirements, HUBO encoding helps mitigate the resource bottlenecks that currently limit the application of quantum algorithms to real-world industrial problems. The authors conclude that these resource-efficient methods are increasingly vital as quantum technology advances and problem sizes scale, enabling more feasible applications in industry and research.