⚛️ quantum physics

Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

This paper benchmarks quantum, classical, and hybrid solvers on Max-Cut problems across 139 instances, revealing that while hybrid and classical simulated annealing methods consistently find global optima for smaller instances, the simulated bifurcation machine and slower classical variants offer superior solution quality for larger instances where global optima are unknown.

Original authors: Jaka Vodeb, Vid Eržen, Timotej Hrga, Janez Povh

Published 2026-07-07

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Jaka Vodeb, Vid Eržen, Timotej Hrga, Janez Povh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, incredibly complex puzzle. The goal is to cut a group of connected dots (like a social network or a circuit board) into two separate groups so that the number of connections between the groups is as high as possible. This is called the Max-Cut problem. It's a famous type of puzzle that is notoriously difficult for computers to solve perfectly, especially when the puzzle gets huge.

This paper is essentially a "race report." The authors gathered a group of different "racers" (computer algorithms) to see who could solve these puzzles the best and the fastest. They tested three types of racers:

The Quantum Racer (D-Wave QPU): A brand-new, high-tech machine that uses the weird laws of quantum physics (like tunneling through walls) to find answers.
The Hybrid Racer (D-Wave Hybrid): A smart team captain that uses the Quantum machine for the hard parts but relies on classical computers for the rest.
The Classical Racer (Simulated Annealing & SBM): Old-school, proven methods that have been refined over years. Think of them as very experienced, methodical hikers.

Here is how the race played out, broken down by the size of the puzzle:

The Small Puzzles (100 to 151 dots)

For these smaller puzzles, the authors knew the perfect solution (the "Global Optimum") because they had solved them with a super-precise, slow calculator beforehand.

The Result: The Hybrid Racer and the Classical Racers were perfect. They found the exact right answer every single time.
The Quantum Racer: It stumbled. While it was fast, the answers it gave were often far from perfect. It was like a sprinter who runs very quickly but keeps tripping over their own shoelaces, missing the finish line by a few steps.

The Medium Puzzles (250 to 500 dots)

These puzzles were too big for the Quantum Racer to even enter the race.

The Result: The Hybrid Racer and the Classical Racers continued to dominate, finding the best possible answers known to science. They were like a well-oiled machine, hitting the target every time.

The Giant Puzzles (800 to 10,000 dots)

These puzzles were so massive that no one knew the perfect answer. The authors had to rely on the "best guess" found in previous research.

The Result: This is where things got interesting.
- The Toshiba SBM (a specialized classical machine) and the slow, careful Classical Racer (SA2) were the champions. They found the highest-quality solutions, beating everyone else. However, the "slow" racer took a long time to think, like a chess grandmaster calculating every move.
- The Hybrid Racer was a close second in quality but was much faster, finishing in a time similar to the Toshiba machine.
- The fast Classical Racer (SA1) was quick but gave up on quality, finding solutions that were noticeably worse.
- The Quantum Racer couldn't even run this race; the puzzles were simply too big for its current hardware.

The Big Takeaways

Speed vs. Accuracy: The new Quantum machine is fast, but for these specific puzzles, it isn't accurate enough yet. It's like a sports car that drives fast but can't navigate the turns well.
The "Black Box" Problem: The Hybrid solver (the team captain) is incredibly effective and can handle huge puzzles quickly. However, it's a "black box." The researchers can't see inside to understand how it works or exactly when it uses the quantum part. It just gives a great answer, but the "how" remains a mystery.
Old Dogs, New Tricks: The classic, transparent methods (Simulated Annealing), when tuned carefully, are still beating the fancy quantum hardware in terms of finding the best answers. Sometimes, a slow, thoughtful approach (SA2) beats a fast, flashy one.

In summary: The paper concludes that while quantum technology is exciting and improving, for the specific task of solving these Max-Cut puzzles right now, a mix of classical computing and smart hybrid strategies is outperforming the pure quantum machine in both accuracy and the ability to handle large problems. The quantum machine is a promising sprinter, but it hasn't yet learned to run the marathon perfectly.

Technical Summary: Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem

Problem Definition
This study addresses the NP-hard Max-Cut problem and its equivalent formulation, the Quadratic Unconstrained Binary Optimization (QUBO) problem. The objective is to partition the vertices of a weighted undirected graph into two disjoint sets such that the sum of the weights of the edges connecting the sets is maximized. The paper evaluates the ability of various solvers to find solutions close to the global optimum, acknowledging that for large instances, exact solutions are often computationally intractable, necessitating approximate heuristics.

Methodology and Experimental Setup
The authors conducted a comprehensive benchmarking study using three distinct datasets comprising 139 problem instances with sizes ranging from 100 to 10,000 nodes.

Datasets:
1. Billionnet and Elloumi (be): 50 instances with $n \in \{101, 121, 151\}$ . Global optima were computed using exact solvers BiqBin and MADAM.
2. Beasley collection (bqp): 20 instances with $n \in \{251, 501\}$ . Optima for $n=251$ were computed exactly; for $n=501$ , best-known values from literature were used.
3. G-dataset (G): 69 instances with $n \in \{800, 1000, 2000, 3000, 5000, 7000, 8000, 9000, 10000\}$ . Global optima are unknown; best-known solutions from literature were used as benchmarks.
Solvers Evaluated:
- Quantum Annealing (QPU): D-Wave Advantage system utilizing a "fast annealing" feature to isolate qubits from environmental effects. Limited to instances with $n \le 151$ .
- Hybrid Solver: D-Wave's cloud-based "LeapHybridSampler," which iteratively combines classical methods (interruptable simulated annealing, tabu search, parallel tempering) with QPU calls. Capable of handling all instance sizes.
- Classical Simulated Annealing (SA): Two variants of the algorithm from [3] were implemented:
  - SA1: Aggressive step size, initial temperature 10,000 (optimized for runtime comparable to QPU).
  - SA2: Conservative step size, initial temperature 40,000 (optimized for solution quality).
- Simulated Bifurcation Machine (SBM): Toshiba's hardware solver. Results were taken from existing literature [4] as the authors did not have direct access to the solver.

Key Results

Small Instances ( $n \le 151$ ): The Hybrid solver and both SA variants (SA1, SA2) consistently achieved the global optimum for all instances. The QPU, however, consistently produced solutions significantly far from the global optimum.
Medium Instances ( $n = 251, 501$ ): The Hybrid solver and SA variants again matched the global optima (for $n=251$ ) or the best-known values (for $n=501$ ). The QPU could not be tested due to capacity limits.
Large Instances ( $n \ge 800$ ):
- Solution Quality: The SBM and SA2 produced the highest quality solutions, often finding the best-known values. The Hybrid solver performed noticeably worse than SBM and SA2, while SA1 produced the lowest quality solutions among the tested methods.
- Computational Time: The Hybrid solver and SBM demonstrated efficient computation times (seconds to tens of seconds). SA2 required significantly more time (hundreds of seconds, roughly 1000x slower than Hybrid/SBM in some comparisons) to achieve superior solution quality. SA1 had a runtime comparable to the Hybrid solver but yielded inferior solutions.

Significance and Claims
The paper claims to advance the understanding of quantum-assisted optimization by rigorously testing the new D-Wave fast annealing QPU and Hybrid solver against state-of-the-art classical methods on a standardized, publicly available set of Max-Cut instances.

The authors conclude that:

QPU Limitations: The D-Wave QPU, even with fast annealing, fails to find optimal solutions for the tested instances and is limited by problem size ( $n \le 151$ ).
Hybrid Efficacy: The D-Wave Hybrid solver is highly efficient in terms of speed and scalability (handling up to 10,000 nodes) and produces near-optimal solutions for smaller instances. However, for the largest instances, it is outperformed in solution quality by classical SA (specifically SA2) and SBM.
Classical Competitiveness: Transparent, classical simulated annealing algorithms (specifically the SA2 variant) remain highly competitive, often outperforming the black-box Hybrid solver in solution quality, albeit at a higher computational cost.
Transparency Gap: The authors express frustration regarding the "black-box" nature of the Hybrid solver, noting that the lack of insight into its internal workflow and quantum resource utilization hinders scientific analysis.

The study does not claim a quantum advantage for the specific solvers and problem instances tested; rather, it highlights that for Max-Cut, current classical heuristics (when tuned for quality) and specialized hardware like SBM can outperform or match the performance of the tested quantum and hybrid approaches.

The Small Puzzles (100 to 151 dots)

The Medium Puzzles (250 to 500 dots)

The Giant Puzzles (800 to 10,000 dots)

The Big Takeaways

More like this