The Quest for Quantum Advantage in Combinatorial Optimization: End-to-end Benchmarking of Quantum Solvers vs. Multi-core Classical Solvers

This paper presents an end-to-end benchmark demonstrating that a hybrid sequential quantum solver executed on IBM Heron processors can achieve sub-second runtimes and solution quality competitive with strong multi-core classical solvers, including those utilizing 128 vCPUs or 8 NVIDIA A100 GPUs, for higher-order unconstrained binary optimization problems.

The Gist

Imagine you are trying to solve a massive, incredibly complex jigsaw puzzle. But this isn't a normal puzzle; the pieces are shaped like 3D Tetris blocks, they change shape when you touch them, and there are millions of them. Your goal is to find the perfect arrangement where every piece fits without a single gap.

This is what Combinatorial Optimization is: finding the best possible solution among a dizzying number of options. It's used for everything from routing delivery trucks to designing new drugs.

For years, scientists have been asking: "Can quantum computers (the super-fast, futuristic machines) actually beat our best classical computers (the powerful servers we use today) at solving these puzzles right now?"

This paper is the answer to that question, but with a very important twist: They didn't just compare the engines; they compared the whole car.

The Race: A Hybrid Quantum Car vs. A Fleet of Classical Trucks

The researchers set up a race between two teams:

1. The Quantum Team (HSQC): They used a new "Hybrid Sequential Quantum Computing" car. Think of this car as having a human driver (classical computer) who does the heavy lifting, a magic teleporter (the quantum processor) that takes a few giant, lucky leaps to skip over traffic jams, and then the human driver again to fine-tune the final parking spot.

   • The Magic: The quantum part doesn't solve the whole puzzle. It just takes a few "quantum leaps" to jump out of local dead ends that trap normal computers.
   • The Hardware: They used a real quantum computer from IBM (the "Heron" chip) located in a data center.

2. The Classical Team: This wasn't just one computer. It was a massive fleet.

   • Some used 128 powerful CPU cores (like a server room full of brains).
   • Others used 8 top-tier NVIDIA A100 GPUs (like a supercomputer designed for graphics and AI, which are also great at math).
   • They used different strategies: some were like "Simulated Annealing" (trying random moves and slowly cooling down), others were "Memetic Tabu Search" (learning from past mistakes), and others were "Parallel Tempering" (running many different versions of the puzzle at once).

The Rules of the Race: The "Wall-Clock" Timer

Here is the most important part of the paper: They timed the entire process, not just the quantum leap.

In many previous studies, researchers would say, "Look! The quantum part took 1 millisecond!" But they ignored the time it took to:

• Prepare the puzzle.
• Send the data to the quantum computer.
• Wait for the quantum computer to finish.
• Send the data back.
• Clean up the results.

This paper used a "Wall-Clock" timer. It started the stopwatch the moment the puzzle was handed to the system and stopped it the moment the final answer was ready. This includes all the waiting, the networking, and the setup.

The Result:

• The Quantum Car: It finished the race in less than one second (about 0.8 seconds).
• The Classical Fleet: Even with 128 CPUs or 8 GPUs, most of the classical methods could not reach the same quality of solution in that same one-second window. They were still searching for the answer.

The "Sweet Spot" Analogy

Imagine you are looking for a specific needle in a haystack.

• Classical Solvers are like a team of people with metal detectors. They are very thorough. If you give them 10 minutes, they will find the needle. But if you only give them 1 second, they might only scan the top layer of the hay.
• The Quantum Hybrid is like a team that uses a metal detector plus a drone that can instantly hover over the most likely spots.
• The Discovery: In the "1-second window" (which is crucial for real-time applications like stock trading or traffic control), the Quantum Hybrid found a better needle than the metal detectors could find in the same time.

However, the paper is honest: If you give the classical team 10 seconds, they eventually catch up and sometimes even beat the quantum team. The quantum advantage here isn't about being infinitely faster; it's about being faster right now when time is tight.

Why This Matters

1. It's Real, Not Theoretical: They didn't simulate a quantum computer on a normal laptop. They used a real, physical quantum chip.
2. It's a Fair Fight: By including the "overhead" (the time to send data back and forth), they showed that quantum computers are finally fast enough to be useful in the real world, even with current limitations.
3. The "Hybrid" Future: The paper suggests that the future isn't "Quantum vs. Classical." It's Quantum + Classical. The classical computer does the boring, heavy work, and the quantum computer does the tricky, "leapfrog" moves that classical computers struggle with.

The Bottom Line

This paper is a milestone. It proves that for certain types of difficult puzzles, a hybrid system (using a quantum chip for a split second) can solve problems faster and better than even the most powerful supercomputers, if you need the answer in under a second.

It's like saying: "We haven't built a spaceship that can go to Mars yet, but we just proved that our new hybrid rocket can get to the moon faster than a jet plane can get to the next city, including the time it takes to board and taxi."

It's a small step, but it's a step that shows the technology is finally ready to leave the lab and start doing real work.

Technical Summary

1. Problem Statement

The paper addresses the challenge of Higher-Order Unconstrained Binary Optimization (HUBO), a class of combinatorial optimization problems where the objective function involves interactions between three or more binary variables simultaneously. These problems are often formulated as finding the ground state of an Ising model with multi-spin interactions.

• The Gap: While quantum algorithms theoretically offer advantages, current hardware is limited by connectivity, coherence times, and significant classical pre/post-processing overheads. Most existing benchmarks fail to account for the full end-to-end pipeline (preprocessing, QPU execution, and postprocessing) or compare against only weak classical baselines.
• The Goal: To determine if current quantum hardware, when integrated into a hybrid workflow, can achieve practical, sub-second performance competitive with strong classical solvers running on multi-core CPUs and GPUs.

2. Methodology

A. The Hybrid Sequential Quantum Computing (HSQC) Workflow

The authors propose and benchmark a proprietary hybrid workflow developed by Kipu Quantum, executed on IBM Heron r3 quantum processors (specifically the ibm_boston device). The workflow consists of three sequential stages:

1. Classical Warm Start: Uses Simulated Annealing (SA) to generate a high-quality initial solution.
2. Quantum Evolution: Executes a Bias-Field Digitized Counterdiabatic Quantum Optimization (BF-DCQO) circuit. This non-variational algorithm uses short digitized evolutions to navigate the energy landscape, avoiding the barren plateau issues common in variational algorithms like QAOA.
3. Classical Refinement: Uses Memetic Tabu Search (MTS) to refine the quantum output, escaping local minima.

B. Benchmark Design

• Instance Generation: The study uses two families of instances (3S and 4S) with $N=156$ variables. These are constructed via swap-layer densification on the heavy-hex coupling graph of the IBM quantum processor. This ensures the problems are "hardware-native," minimizing embedding overhead.
• Problem Characteristics: The instances feature rugged, frustrated energy landscapes generated by sampling coupling strengths from a Cauchy distribution (heavy-tailed), making them difficult for local search heuristics.
• Metrics:
  • Wall-Clock Time ($T_{wall}$): Includes all overheads: SA preprocessing, QPU transpilation, submission, execution, data return, and MTS postprocessing.
  • Time-to-Solution (TTS): Calculated for a target success probability ($p_{target} = 0.99$) of reaching a target energy $E_{target}$.
  • Closeness-to-Target ($C(t)$): The ratio of the best energy found to the target energy at a specific time.

C. Classical Baselines

The HSQC pipeline is compared against five strong classical solvers running on identical or superior hardware:

• SA & MTS: Run on AWS bare-metal instances (128 vCPUs).
• PT+ (Parallel Tempering): An enhanced, in-house implementation of Parallel Tempering with local search refinements, running on 128 vCPUs.
• EasySolve: A C++ library solver running on 128 vCPUs.
• ABS3: A GPU-accelerated solver running on 8 NVIDIA A100 GPUs.

3. Key Contributions

1. Strict End-to-End Benchmarking: Unlike previous studies that often isolate QPU execution time, this work accounts for the complete system latency, including transpilation, network transfer, and classical overheads.
2. Hardware-Native HUBO: The use of swap-layer densification allows for testing higher-order interactions directly on gate-model hardware without the massive overhead of minor embedding typically required for QUBO/HUBO mapping.
3. Sub-Second Latency Regime: The study identifies a specific "latency window" (under 1 second) where the hybrid quantum approach is competitive, a regime critical for real-time applications.
4. System-Level Comparison: It compares a single QPU against massive classical clusters (128 vCPUs and 8 A100 GPUs), providing a realistic view of the current "quantum advantage" landscape.

4. Key Results

A. Performance at Sub-Second Latency

• HSQC Performance: The HSQC pipeline achieves high-quality solutions in less than 1 second (mean runtime: ~757 ms for 3S, ~841 ms for 4S).
• Ground State Matching: In 14 out of 20 instances, the HSQC pipeline matched the independently verified ground-state energy ($E_{GS}$) within this single-second window.
• Comparison: At this same 1-second mark:
  • SA, MTS, and EasySolve (running on 128 vCPUs) failed to reach the target energy, achieving only ~99.7% to 99.9% of the target value.
  • PT+ and ABS3 (8x A100 GPUs) were the only classical solvers to match or slightly surpass the HSQC target energy at this specific time point.

B. Time-to-Solution (TTS) Analysis

• vs. SA and MTS: HSQC significantly outperforms standard SA and MTS.
  • 3S Family: HSQC TTS range (3.87s – 43.77s) vs. SA (9.80s – 426.74s). HSQC offers up to a 14.26x speedup in worst-case latency.
  • 4S Family: HSQC offers up to a 13.73x speedup over SA.
  • Reliability: HSQC has a much tighter TTS distribution (lower variance) compared to SA and MTS, which suffer from frequent failures (infinite TTS) on harder instances.
• vs. PT+ and ABS3:
  • PT+ (128 vCPUs) remains the strongest classical baseline, achieving the lowest overall TTS (geometric mean ~1.87s for 3S) and outperforming HSQC in total time-to-solution.
  • ABS3 (8x A100 GPUs) is highly competitive, often matching HSQC in the matched-time comparison but showing broader variance in TTS.

C. Latency vs. Throughput

The results indicate that while classical solvers (especially SA) have high throughput (billions of bit-flips per second), they struggle to find the global optimum within the strict sub-second latency budget. The HSQC pipeline leverages the coordinated effect of warm starts, shallow quantum evolution, and refinement to find high-quality solutions faster in this specific "near-optimal" regime.

5. Significance and Conclusion

• Practical Quantum Advantage: The paper does not claim a broad asymptotic quantum advantage. Instead, it demonstrates a practical, system-level advantage in a specific operating regime: solving complex HUBO problems with high reliability and low latency (<1s) on a single QPU.
• Competitiveness: A single QPU executing the HSQC workflow can compete with classical solvers running on 128 vCPUs and approaches the performance of 8 NVIDIA A100 GPUs in terms of time-to-target for near-optimal solutions.
• Future Outlook: The study suggests that the path to quantum advantage lies in hybrid workflows and system-level optimization rather than isolated algorithmic speedups. It highlights that as quantum hardware improves (better coherence, connectivity) and orchestration overheads decrease, the hybrid approach could scale to outperform even the strongest classical baselines.
• Benchmarking Standard: The authors provide a reproducible framework for future benchmarking that emphasizes full pipeline accounting, setting a new standard for evaluating quantum optimization claims.

In summary, this work provides evidence that hybrid quantum-classical solvers, when rigorously benchmarked against strong classical baselines with full latency accounting, can already deliver competitive performance for combinatorial optimization in latency-sensitive applications.