Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization

This paper introduces a novel, qubit- and gate-efficient logarithmic HUBO encoding with a lexicographic penalty system for quantum optimization of graph partitioning problems, which minimizes label counts without dedicated indicator variables and demonstrates superior solution quality and time-to-solution compared to traditional one-hot encodings.

The Gist

Imagine you are the head of a massive, chaotic party. You have a huge list of guests (the vertices of a graph) and a list of who hates whom (the edges). Your goal is to assign every guest to a "table" (a color or label) such that no two enemies sit at the same table.

But here's the twist: You don't just want any solution. You want to use the fewest number of tables possible to save money on catering. This is the classic Minimum Graph Coloring problem, a famous puzzle that is incredibly hard for computers to solve.

Now, imagine you want to solve this using a Quantum Computer. Quantum computers are like super-fast, magical dice rollers, but they have a catch: they are very fragile, have very limited "memory" (qubits), and get confused easily if you ask them too many complex questions at once.

The Old Way: The "One-Hot" Method

Traditionally, to tell a quantum computer about a party with 100 guests and 10 possible tables, researchers used a method called One-Hot Encoding.

Think of this like giving every guest a giant clipboard with 10 checkboxes (one for each table). To say "Guest Alice is at Table 3," you check the box for Table 3 and leave the other 9 blank.

• The Problem: If you have 100 guests, you need $100 \times 10 = 1,000$ checkboxes.
• The Quantum Cost: Quantum computers are like tiny, fragile houses. Fitting 1,000 checkboxes into a house with only 50 rooms is impossible. It's like trying to park a semi-truck in a compact car garage. The computer gets overwhelmed, the "garage" (the chip) breaks down, and the solution fails.

The New Way: The "Logarithmic" Method

The authors of this paper, Tristan, Prashanti, Vikram, Hausi, and Ulrike, invented a smarter way to pack the information. They call it Logarithmic Encoding.

Instead of giving every guest a 10-checkbox clipboard, they give them a binary ID card (like a zip code).

• To represent 10 tables, you only need 4 bits (since $2^4 = 16$, which covers 10).
• Now, for 100 guests, you only need $100 \times 4 = 400$ checkboxes.
• The Win: You just cut the memory requirement in half (or more, as the problem gets bigger). It's like swapping that semi-truck for a sleek motorcycle. Suddenly, the quantum computer can actually fit the problem in its garage.

The Secret Sauce: The "Lexicographic Penalty"

There was a big fear with this new method: How do we tell the quantum computer to use the fewest tables possible?

In the old method, you had to add extra "indicator" variables (like a separate counter for every table) to count how many were used. This added even more memory overhead.

The authors introduced a clever trick called a Lexicographic Penalty System.

• The Analogy: Imagine the tables are numbered 1, 2, 3, 4...
• The new system whispers to the quantum computer: "It is much more expensive to use Table 4 than Table 3. It is even more expensive to use Table 3 than Table 2."
• By making the "cost" of using higher-numbered tables skyrocket, the computer naturally tries to fill up Table 1, then Table 2, and so on, before ever touching Table 10.
• The Result: The computer automatically finds the solution with the fewest tables without needing any extra counters or indicators. It's like telling a child, "You get a cookie for every toy you put away, but you get a huge cookie for putting away the first toy, and a tiny cookie for the last one." They will naturally rush to put away the first toys first.

Why This Matters (The Results)

The team tested this on a real quantum machine (a D-Wave quantum annealer).

1. Speed: The new method found good solutions 10 to 100 times faster than the old method.
2. Scalability: As the party got bigger (more guests), the old method crashed and burned, while the new method kept getting better.
3. Stability: The new method created more uniform "chains" of data on the chip. Imagine the old method was like a wobbly tower of blocks that fell over easily; the new method was a sturdy, even stack that didn't wobble.

The Bottom Line

This paper is a breakthrough because it's the first time anyone has successfully taught a quantum computer to optimize (find the best number of tables) rather than just decide (can we do it with 5 tables?).

They managed to shrink a massive, clumsy problem into a tiny, elegant package that fits perfectly into today's fragile quantum hardware. It's like taking a mountain of luggage and compressing it into a single, efficient carry-on bag, allowing us to finally take the quantum flight to solve real-world problems like network security, scheduling, and logistics.

Technical Summary

1. Problem Statement

The paper addresses the challenge of encoding label-symmetric, pairwise-decomposable graph partitioning problems for quantum optimization. These problems involve assigning discrete labels (from a set of size $k$) to vertices in a graph such that specific constraints are met and the number of distinct labels used is minimized.

Key characteristics of the target problems include:

• Optimization vs. Decision: Unlike previous works that often focus on decision versions (e.g., "Can this graph be colored with $k$ colors?"), this work targets the optimization version (e.g., "What is the minimum number of colors needed?").
• Examples: Minimum Graph Coloring, Minimum $k$-Cut, and Community Detection.
• The Encoding Bottleneck: Standard quantum optimization algorithms (like QAOA or Quantum Annealing) operate on binary variables. The standard approach, one-hot encoding, represents each $k$-valued variable using $k$ binary bits. This results in a linear overhead of $O(|V| \cdot k)$ qubits and introduces a massive number of infeasible states, creating bottlenecks in qubit count, gate complexity, and penalty tuning.

2. Methodology

The authors propose a novel Higher-Order Unconstrained Binary Optimization (HUBO) formulation that utilizes logarithmic encoding combined with a lexicographic penalty system.

A. Logarithmic Encoding

Instead of using $k$ bits per vertex (one-hot), the authors use $\lceil \log_2 k \rceil$ bits per vertex to represent the label.

• Qubit Reduction: This reduces the qubit requirement from $O(|V| \cdot k)$ to $O(|V| \cdot \log k)$.
• Higher-Order Terms: This encoding naturally leads to higher-order interactions (degree $2\lceil \log_2 k \rceil$) in the Hamiltonian, which must be handled by gate-based algorithms (via phase gadgets) or reduced to quadratic form (QUBO) for annealers.

B. Lexicographic Penalty System

A major challenge in optimization is minimizing the count of used labels without introducing auxiliary indicator variables (which would negate qubit savings). The authors introduce a lexicographic penalty to solve this:

• Mechanism: They assign a hierarchy to the bits of the binary representation. The penalty function is designed such that solutions using "smaller" binary values (e.g., 00, 01) are energetically preferred over "larger" values (e.g., 10, 11).
• Implicit Minimization: By enforcing a strict hierarchy where $P_1 < P_2 < \dots < P_L$ (where $L = \lceil \log_2 k \rceil$), the system implicitly minimizes the number of distinct labels used. If a solution can be achieved using only labels 0 and 1, it will have a lower energy than a solution requiring label 2, even if the adjacency constraints are satisfied in both.
• No Indicator Variables: This eliminates the need for extra "count" registers required in one-hot formulations.

C. Theoretical Guarantees

The paper derives provably sufficient conditions for all penalty coefficients to ensure that the ground state of the Hamiltonian corresponds to a valid, optimal solution:

1. Feasibility: Ensures no adjacent vertices share the same label (for coloring) or satisfy other hard constraints.
2. Optimality: Ensures the solution uses the minimum number of distinct labels.
3. Quadratization: For hardware requiring quadratic interactions (like D-Wave), the authors apply the Rosenberg reduction method to convert HUBO to QUBO. They derive specific bounds for the auxiliary variable penalties to ensure the reduction does not introduce spurious low-energy states.

D. Gate Complexity Analysis

The authors analyze the 2-qubit gate count (specifically CNOTs) for a single QAOA layer:

• One-Hot: $\Theta(|V|k^2 + |E|k)$
• Logarithmic: $\Theta(|E| \cdot k \cdot \lceil \log_2 k \rceil)$
• Result: For sparse graphs, the logarithmic encoding offers a near-exponential reduction in gate count compared to one-hot encoding.

3. Key Contributions

1. First Optimization-Focused Quantum Encoding: This is the first work to address the optimization versions of label-symmetric graph partitioning problems (minimizing partition count) in a quantum setting, rather than just decision problems.
2. Novel Lexicographic Penalty: Introduction of a penalty system that implicitly minimizes the number of used labels without dedicated indicator variables, preserving the qubit efficiency of the logarithmic encoding.
3. Rigorous Penalty Bounds: Derivation of explicit, sufficient mathematical conditions for all penalty coefficients (including those for Rosenberg quadratization) to guarantee the correctness of the lowest-energy solution.
4. Gate Efficiency: Demonstration that the logarithmic encoding significantly reduces the 2-qubit gate count per QAOA layer, making it more suitable for gate-based quantum computers.

4. Experimental Results

The authors benchmarked their approach against the standard one-hot encoding on the D-WAVE Advantage2_1.11 quantum annealer using 350 randomly generated graphs.

• Time-to-Solution (TTS): The logarithmic encoding achieved a TTS one to two orders of magnitude lower than the one-hot encoding for graphs with $|V| \approx 20$. The advantage grew as problem size increased.
• Qubit Counts:
  • Logical Qubits: Pre-quadratization, the logarithmic encoding used exponentially fewer qubits.
  • Post-Quadratization: Due to auxiliary variables introduced by Rosenberg reduction, some dense graphs required more logical qubits than one-hot. However, the performance advantage persisted.
• Chain Length Variance: A critical finding was that the logarithmic encoding produced more uniform chain lengths after minor embedding.
  • Significance: In quantum annealing, non-uniform chain lengths distort the problem Hamiltonian. The logarithmic encoding's uniformity allowed for better chain strength tuning, preserving problem fidelity and reducing thermal noise susceptibility, which was the primary driver of the improved TTS.

5. Significance

This work provides a scalable pathway for solving NP-hard graph partitioning problems on near-term quantum hardware.

• Scalability: By reducing qubit requirements from linear to logarithmic in the number of labels, it allows larger problems to be mapped onto current hardware.
• Hardware Agnostic: The formulation is compatible with both Quantum Annealing (via QUBO reduction) and Gate-Based models (via HUBO and phase gadgets).
• Practical Impact: The results demonstrate that encoding efficiency is not just about raw qubit count; the structure of the encoding (specifically chain length uniformity) significantly impacts solution quality and speed on real hardware. This suggests that future quantum algorithm design must prioritize encoding strategies that minimize hardware-specific artifacts like chain breaks.