Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut

This paper demonstrates that the Quantum Approximate Optimization Algorithm (QAOA), when applied to integer graph problems like Max-$k$-Cut using qudit encodings, can surpass both established semi-definite programming guarantees and new classical heuristics in specific parameter regimes, suggesting that extending quantum optimization beyond binary variables offers promising avenues for quantum advantage.

The Gist

Imagine you are a city planner trying to organize a massive festival. You have thousands of booths (vertices) connected by walkways (edges). Your goal is to assign each booth to one of k different zones (like "Food," "Music," "Games," etc.) so that the most walkways connect booths in different zones. This is the Max-k-Cut problem.

If you have only two zones (Food vs. Music), it's like a simple binary choice. But what if you have 3, 4, or even 8 zones? That turns the problem into an integer optimization challenge, which is much harder for computers to solve.

This paper is about testing a new type of computer—a Quantum Computer—to see if it can solve these complex zoning problems better than our best classical computers.

Here is the breakdown of their journey, using some everyday analogies:

1. The Problem: The "Coloring" Puzzle

Think of the graph as a giant map of a city. You want to paint the buildings with k different colors.

• The Goal: Paint the map so that the most roads connect buildings of different colors.
• The Difficulty: As the number of colors ($k$) and the number of roads per building (degree $d$) increase, the number of possible ways to paint the city explodes. It's like trying to find the perfect seating arrangement for a wedding with 1,000 guests where everyone has specific preferences about who they sit next to.

2. The Contenders: The Race for the Best Solution

The authors set up a race between three competitors to see who can find the best "painting" (solution):

• Competitor A: The "Frieze-Jerrum" Algorithm (The Classic Mathematician)
  This is the current gold standard for classical computers. It uses a sophisticated technique called Semidefinite Programming (SDP). Think of it as a very smart, slow-moving librarian who checks every possible book in the library to find the perfect one. It's guaranteed to be "good enough" in the worst-case scenario, but it's heavy and slow.

• Competitor B: The "DSatur" Heuristic (The Experienced Architect)
  The authors invented a new, faster classical algorithm. Imagine a construction foreman who looks at the most crowded intersections first and assigns colors based on what's already there. It's fast, intuitive, and in their tests, it actually beat the "Classic Mathematician" (SDP) in many cases.

• Competitor C: QAOA (The Quantum Explorer)
  This is the Quantum Approximate Optimization Algorithm. Instead of checking one solution at a time, a quantum computer can explore many possibilities simultaneously, like a swarm of bees searching for flowers.

  • The Twist: Usually, quantum computers are tested on simple "Yes/No" (binary) problems. This paper tests them on "Integer" problems (choosing from 3, 4, or more options), which is like asking a quantum computer to choose a color from a palette of 8 instead of just Black or White.

3. The Secret Weapon: The "Tree" Shortcut

Calculating how well a quantum computer will perform is usually impossible because the math gets too heavy. The authors developed a magic formula (an iterative formula).

• The Analogy: Imagine trying to predict the weather for a whole continent. Usually, you need to simulate every single cloud. But if the continent is made of perfect, repeating islands (high-girth graphs), you only need to simulate one small island and a few layers of trees around it.
• The Result: They found a way to predict the quantum computer's performance on a massive graph by only looking at a tiny, tree-like piece of it. This allowed them to run simulations on a regular laptop that would otherwise require a supercomputer.

4. The Results: Who Won?

The race happened in two stages:

Stage 1: Shallow Depth (The Sprint)
The quantum computer was given a very short time to think (low "depth" or $p=4$).

• The Outcome: The Quantum Explorer (QAOA) managed to beat the "Classic Mathematician" (SDP) in specific scenarios (like when there are 3 or 4 zones and the city isn't too crowded).
• The Catch: The new "Experienced Architect" (the authors' own heuristic) was still faster and found better solutions than the quantum computer at this stage.

Stage 2: Deep Depth (The Marathon)
The authors asked: "What if we let the quantum computer think longer?" (increasing the depth to $p=20$).

• The Prediction: Since they can't actually run a quantum computer that deep yet, they used their "Tree Shortcut" formula to extrapolate (predict) the future.
• The Verdict: The math suggests that if the quantum computer is allowed to run deeper (around 20 layers), it will eventually overtake the best classical human-made algorithm.

5. Why This Matters

For a long time, people thought quantum computers would only be useful for simple "on/off" switches (binary problems). This paper says: "Wait a minute! The real world is full of choices with many options (integers)."

By showing that quantum algorithms can handle these "multi-choice" problems and potentially beat the best classical methods, the authors have opened a new door. They suggest that the "Quantum Advantage" (where quantum computers win) might not just be about speed, but about finding better quality solutions for complex, real-world integer problems like logistics, finance, and network design.

In a nutshell:
The authors built a crystal ball (the formula) to see the future of quantum computing. They found that while classical "smart guessers" are currently winning, the quantum explorer is training hard and is predicted to cross the finish line first if given enough time to think. This proves that quantum computers might soon be the best tool for solving complex, multi-option puzzles.

Technical Summary

1. Problem Statement

The paper addresses the application of quantum algorithms to integer optimization problems on graphs, a domain less explored than binary optimization. The specific focus is the Max-$k$-Cut problem, which involves partitioning the vertices of a graph into $k$ disjoint subsets to maximize the number of edges connecting vertices in different subsets.

• Challenge: Max-$k$-Cut is APX-hard. While classical algorithms like the Frieze-Jerrum algorithm (based on Semidefinite Programming, SDP) provide the best known worst-case approximation guarantees, they are computationally expensive for large graphs.
• Gap: Existing Quantum Approximate Optimization Algorithm (QAOA) studies have largely focused on binary variables (qubits, $k=2$). Extending QAOA to integer variables ($k > 2$) requires encoding labels into qudits (quantum systems with $k$ levels) and developing new analytical tools to evaluate performance without running on noisy hardware.

2. Methodology

A. Qudit QAOA Formulation

The authors map the integer labeling of graph vertices to quantum states $|a\rangle$ where $0 \le a \le k-1$. The QAOA circuit consists of $p$ layers alternating between:

1. Phaser ($U_C$): Encodes the cost function (penalizing edges within the same subset).
2. Mixer ($U_M$): Enables exploration of the solution space. The paper analyzes three mixers:
   • Transverse Field (TF): Requires $k$ to be a power of 2; maps qudits to qubits.
   • BKKT Mixer: A specific mixer from prior literature requiring $k$ parameters per layer.
   • Grover Mixer: Generated by a Hamiltonian projecting onto the uniform superposition state.

B. Analytical Framework: High-Girth Graphs

To evaluate QAOA performance on large graphs without running the circuit, the authors derive an instance-independent iterative formula.

• Key Assumption: The graphs are $d$-regular with high girth (length of the shortest cycle $\ge 2p+2$).
• Locality Argument: Due to the locality of QAOA operations, the expectation value of an edge cost depends only on a tree-like subgraph of depth $2p+1$ surrounding that edge.
• Tensor Network Contraction: The expectation value is computed by contracting a tree tensor network.
  • General Complexity: $O(p k^{4p+4})$ time and $O(k^{2p+2})$ memory.
  • Optimized Complexity: For cost functions that are translation-invariant in $\mathbb{Z}_k$ (like Max-$k$-Cut), the authors utilize the Hadamard transform to reduce the time complexity to $O(p^2 k^{2p+2} \log k)$. This improvement is independent of the graph degree $d$.

C. Classical Baselines

To rigorously test quantum advantage, the authors compare QAOA against:

1. Frieze-Jerrum SDP: The standard worst-case optimal classical algorithm using SDP relaxation and randomized rounding.
2. New Heuristic (DSatur-inspired): A greedy algorithm based on "degree of saturation" (selecting vertices with the most distinct neighbor labels) followed by local improvement (1-opt hill climbing). This heuristic runs in $O(k|E|^2)$ and empirically outperforms SDP on random regular graphs.

3. Key Contributions

1. Generalized Iterative Formula: Derivation of a closed-form iterative formula for QAOA expectation values on high-girth graphs for arbitrary $k$ (qudits), $d$ (degree), and $p$ (depth). This allows for parameter optimization across all graphs of a given degree without simulating specific instances.
2. Complexity Reduction: Introduction of a Hadamard-transform-based acceleration for translation-invariant cost functions, making the evaluation of deep QAOA circuits feasible for larger $k$.
3. Strong Classical Baseline: Development of a new heuristic algorithm that empirically surpasses the Frieze-Jerrum SDP algorithm on random regular graphs, setting a higher bar for quantum algorithms to beat.
4. Quantum Advantage Evidence: Identification of specific parameter regimes where QAOA outperforms the best-known classical worst-case guarantees (SDP) and shows potential to surpass strong heuristics at moderate depths.

4. Key Results

Performance vs. SDP

• Regime of Advantage: For random $d$-regular graphs, QAOA with depth $p=4$ outperforms the Frieze-Jerrum SDP algorithm in the following regimes:
  • $k=3$: Graph degrees $d \le 10$.
  • $k=4$: Graph degrees $d \le 40$.
• This represents the first rigorous demonstration of a quantum algorithm surpassing the best worst-case classical guarantees for an integer combinatorial optimization problem at scale.

Performance vs. New Heuristic

• At shallow depths ($p \le 4$), the new classical heuristic outperforms QAOA.
• Extrapolation: By fitting performance curves to the function $F(p) = m/(p^a + c) + b$, the authors extrapolate that QAOA may overtake the strong heuristic at depths $p \lesssim 20$ for $k=3$ and $k=4$.
• Mixer Comparison: For $k=3$, the BKKT mixer effectively reduces to the Grover mixer after optimization. For $k=4$, the Grover and BKKT mixers significantly outperform the Transverse Field mixer.

Scalability

• The analysis holds for $k \in \{3, 4, \dots, 8\}$. The trend of QAOA surpassing SDP but lagging behind the heuristic at low depths remains consistent as $k$ increases.

5. Significance and Conclusion

• Beyond Binary Optimization: The paper demonstrates that moving from binary (qubit) to integer (qudit) optimization opens new avenues for quantum advantage. Integer problems often map more naturally to real-world constraints (e.g., portfolio allocation, scheduling).
• Theoretical Validation: The work provides a robust theoretical framework for analyzing qudit QAOA, proving that quantum algorithms can achieve better approximation ratios than the best-known classical worst-case bounds (SDP) for integer problems.
• Practical Implications: While current hardware is limited, the results suggest that with sufficient circuit depth ($p \approx 20$), qudit-based QAOA could solve integer graph problems better than the strongest classical heuristics.
• Future Work: The authors note that verifying the extrapolation to $p \approx 20$ requires either more efficient classical simulation techniques or actual quantum hardware capable of handling deep qudit circuits. They also suggest generalizing explicit vector algorithms (like Thompson-Parekh-Marwaha for Max-Cut) to Max-$k$-Cut to further strengthen classical baselines.

In summary, this paper establishes that qudit-based QAOA is a viable candidate for achieving quantum advantage in integer optimization, specifically showing superior performance to SDP on high-girth regular graphs for Max-$k$-Cut and offering a pathway to outperform strong classical heuristics with increased circuit depth.