⚛️ quantum physics

Cross-Platform Benchmarking of Near-Term Quantum Optimisation Algorithms

This paper presents an application-level benchmarking framework that evaluates the performance of near-term Variational Quantum Eigensolver and Quantum Annealing algorithms against classical methods on a dense QUBO materials science problem, revealing that current device connectivity, noise, and overheads limit effective scalability beyond 72 variables.

Original authors: Kieran McDowall, Theodoros Kapourniotis, Christopher Oliver, Phalgun Lolur, Konstantinos Georgopoulos

Published 2026-03-25

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Kieran McDowall, Theodoros Kapourniotis, Christopher Oliver, Phalgun Lolur, Konstantinos Georgopoulos

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 find the perfect seating arrangement for a massive, chaotic wedding. You have hundreds of guests (variables), and you need to seat exactly three people at the "empty" tables (vacancies) so that the remaining guests are sitting next to their best friends as much as possible. If they are next to friends, the party is happy (low energy). If they are isolated, the party is awkward (high energy).

This is the core problem the scientists in this paper are solving. They are testing Quantum Computers to see if they can solve this "seating chart" puzzle faster or better than our best classical computers.

Here is a breakdown of their experiment, explained simply:

1. The Setup: A Race Between Runners

The researchers set up a race between four different "runners" (algorithms) to see who can find the best seating arrangement:

The Brute Force Runner: This is a super-organized but slow librarian. They check every single possible seating arrangement one by one. They are guaranteed to find the perfect answer, but it takes them forever if the guest list gets too big.
The Simulated Annealing Runner: This is like a smart, experienced party planner. They start with a random seating chart and make small changes. If a change makes the party happier, they keep it. If it makes it worse, they might still keep it occasionally (to avoid getting stuck in a "good but not great" arrangement). They slowly "cool down" their search to settle on the best solution.
The Quantum Annealing Runner: This is a magic tunnel. You drop a marble (the problem) into a bumpy landscape. The marble naturally rolls down to the lowest point (the best solution). The quantum computer uses the laws of physics to help the marble tunnel through small hills instead of climbing over them.
The VQE Runner (Variational Quantum Eigensolver): This is a tuning fork. You have a quantum circuit that vibrates at a certain frequency. A classical computer acts as a tuner, tweaking the knobs on the circuit over and over, listening to the sound, and trying to find the exact frequency that produces the "lowest note" (the best solution).

2. The Obstacles: Noise and Traffic Jams

The paper highlights two major headaches the quantum runners faced:

The "Noise" Problem: Real quantum computers are like radios with static. They are very sensitive. When the quantum runners try to solve the puzzle, the "static" (noise) makes it hard to hear the right answer. It's like trying to tune a radio to a specific station while a storm is raging outside; sometimes you hear the music, but often you just hear static.
The "Traffic Jam" (Connectivity): This is a huge issue.
- The Problem: In our wedding analogy, imagine every guest needs to talk to every other guest. But the quantum computer is like a building where rooms are only connected to their immediate neighbors.
- The Fix: To make everyone talk, you have to build long, winding hallways (called chains) connecting the rooms.
- The Result: For the Quantum Annealing runner, building these hallways takes a lot of time and resources. It's like spending 90% of your time building the hallways and only 10% actually having the party. As the party gets bigger, the hallways get so long and tangled that the system breaks down.

3. The Results: Who Won?

The researchers tested these runners on problems ranging from small (18 guests) to medium-large (up to 72 guests).

The Classical Winner: The Simulated Annealing runner (the smart party planner) was the clear winner. It found the best solutions quickly and could handle huge parties (up to 338 guests) without breaking a sweat. It scales up nicely, like a well-oiled machine.
The Quantum Struggle:
- Quantum Annealing: It did okay on small problems, but as the party got bigger, the "hallway building" (embedding) took so long that it lost the race. It also struggled to find the perfect answer because of the noise.
- VQE (The Tuning Fork): This runner had a hard time. Because the quantum computer is noisy, the "tuner" (the classical computer) kept getting confused. It often got stuck in a "local minimum"—thinking it found the best note, but actually just finding a slightly lower note than the true lowest one. It also took a very long time to run because the computer had to check the tuning thousands of times.

4. The "Post-Selection" Trick

One clever trick the researchers used was Post-Selection.
Imagine the runners sometimes give you a seating chart where they accidentally put 4 people at the empty tables instead of 3.

The Trick: Instead of letting the computer try to fix this, the researchers just threw those bad charts in the trash and only looked at the ones that followed the rules.
The Catch: They found that using a "gentle penalty" (a small fine for breaking the rules) actually worked better than a "heavy penalty" (a huge fine). Why? Because a huge fine makes the energy landscape so bumpy that the quantum runners get confused. A gentle fine lets them explore, and then they just throw away the bad results at the end.

5. The Big Takeaway

"We are not there yet, but we are learning."

Current State: For this specific type of problem, classical computers (specifically Simulated Annealing) are still better, faster, and more reliable than today's quantum computers.
The Future: The quantum computers are improving. The researchers found that if we can fix the "noise" and make the "hallways" (connectivity) more efficient, quantum computers might eventually win.
The Framework: The most important part of this paper isn't just the result; it's the rulebook they created. They showed how to fairly compare these different technologies. Before, people were comparing apples to oranges. Now, we have a standard way to measure who is actually getting better.

In a nutshell: Quantum computers are like a brand-new, incredibly fast sports car that is currently driving on a dirt road full of potholes. Classical computers are a reliable, slightly slower sedan on a smooth highway. Right now, the sedan wins the race. But the scientists are mapping out the potholes and building better roads, hoping that one day, that sports car will zoom past everything else.

1. Problem Statement

The paper addresses the challenge of benchmarking near-term quantum optimization algorithms against classical counterparts to determine if a "quantum advantage" exists for practical combinatorial optimization problems.

Test Case: The authors utilize a materials science problem: finding the lowest-energy configuration of defective graphene structures. Specifically, the task is to remove a fixed number of atoms (vacancies) from a hexagonal graphene lattice to maximize the remaining carbon-carbon bonds.
Mathematical Formulation: This is modeled as a Densest $k$ -Subgraph (DkS) problem, which is NP-hard. It is encoded as a Quadratic Unconstrained Binary Optimization (QUBO) problem.
- Constraints: The problem requires a fixed number of vacancies (3 in this study). This is handled via a penalty term ( $\lambda$ ) in the QUBO cost function rather than hard constraints.
- Density: The resulting QUBO matrices are fully connected (100% density), which poses significant challenges for quantum hardware due to limited qubit connectivity.
Scale: The study investigates fully connected QUBOs ranging from 18 variables up to 72 variables on quantum hardware, and up to 388 variables on classical hardware.

2. Methodology

The authors developed a rigorous, cross-platform benchmarking framework comparing three classical algorithms and two quantum algorithms across different hardware architectures.

A. Algorithms Compared

Classical Baselines:
- Brute Force: Exhaustive search (exact solution).
- Simulated Annealing (SA): A probabilistic heuristic.
- Random Sampling: A baseline to measure the difficulty of the search space.
Quantum Algorithms:
- Variational Quantum Eigensolver (VQE): Executed on a gate-based QPU (IBM ibm_fez, 156 qubits) and a noiseless state-vector simulator. It uses a hybrid classical-quantum loop with a RealAmplitudes ansatz and the COBYLA optimizer. The objective function utilizes Conditional Value at Risk (CVaR) to improve convergence.
- Quantum Annealing (QA): Executed on a quantum annealer (D-Wave Advantage 6.4, 5612 physical qubits).

B. Benchmarking Framework & Metrics

To ensure fair comparison, the authors defined hardware-agnostic metrics:

Optimal Solution Probability ( $P_s$ ): The likelihood of finding the ground state.
Approximation Ratio (AR): Measures the quality of the solution relative to the theoretical min/max energy range.
Runtime Metrics:
- User Runtime: Total time including encoding, latency, and device execution.
- QPU Time: Specific time the quantum hardware is occupied (excluding classical compilation/encoding).
Post-Selection: A critical step where solutions violating the vacancy constraint are filtered out classically. The authors found that using a small penalty coefficient ( $\lambda$ ) combined with post-selection yields better results than using a large $\lambda$ , which can distort the energy landscape.

C. Embedding Strategies

For Quantum Annealing, two embedding techniques were tested to map the fully connected QUBO graph to the D-Wave hardware topology:

Minor Embedding: The default heuristic mapping.
Clique Embedding: A specialized algorithm for fully connected graphs (cliques) that produces uniform chain lengths.

3. Key Contributions

Unified Benchmarking Framework: Introduced a transparent methodology for comparing gate-based variational algorithms, quantum annealing, and classical methods on the same QUBO instances, including full disclosure of metrics, hyperparameters, and runtime breakdowns.
Large-Scale Dense QUBOs: Successfully solved fully connected QUBOs up to 72 variables on real quantum hardware, a significant scale for dense problems which typically require extensive SWAP gates or chaining.
Scaling Analysis:
- Demonstrated that Simulated Annealing scales polynomially with system size ( $N$ ) for this specific problem, solving instances up to 388 variables.
- Provided provisional evidence that Quantum Annealing (with clique embedding) exhibits polynomial scaling on feasible hardware sizes, though performance degrades as $N$ increases.
Technical Insights:
- Penalty Coefficients: Showed that small $\lambda$ values combined with post-selection outperform large $\lambda$ values by preserving the spectral gap.
- Embedding Overhead: Identified that embedding time is the dominant factor in QA user runtime for minor embedding, whereas clique embedding offers more consistent scaling.
- VQE Limitations: Highlighted that VQE on current hardware is severely limited by noise, barren plateaus, and classical optimization overheads (compilation time), preventing it from scaling effectively beyond 50 variables.

4. Key Results

Performance on 18 Variables:
- Simulated Annealing was the clear winner, achieving $P_s \approx 0.99$ with a user runtime of ~0.34s.
- Quantum Annealing achieved $P_s \approx 0.40$ (post-selected) with a QPU time of ~0.4s, but a total user runtime of ~2.5s due to embedding.
- VQE (QPU) achieved $P_s \approx 0.60$ (post-selected) but suffered from a massive user runtime (~2540s) dominated by classical compilation and optimization loops.
Scaling Behavior:
- Classical: Simulated Annealing maintained high solution quality and polynomial runtime scaling up to 338 variables.
- Quantum Annealing: Could solve up to 72 variables (minor embedding) and 50 variables (clique embedding) with non-zero success probability. However, success probability dropped significantly as $N$ increased.
- VQE: Failed to converge to non-zero success probabilities for problems larger than 50 variables on the QPU. The 72-variable run found sub-optimal solutions but failed to meet convergence criteria within the allocated time.
Error Sources: The study quantified errors arising from shot noise (statistical) and state preparation variance (due to random initial parameters in VQE and noise).

5. Significance and Outlook

Realism over Theory: The paper emphasizes that for near-term algorithms (heuristic), asymptotic complexity arguments are insufficient; rigorous experimental benchmarking on real hardware is required.
Hardware Bottlenecks: The results highlight that current quantum advantage is not yet realized for dense optimization problems. The primary bottlenecks are device connectivity (requiring long qubit chains), noise/decoherence, and classical overheads (compilation and optimization loops).
Future Directions: The authors suggest that future improvements should focus on:
- Error Mitigation: Techniques to reduce noise impact.
- Advanced Embedding: Moving beyond minor embedding to more efficient topological mappings.
- Algorithmic Tweaks: Using "warm starts" (classical solutions to initialize quantum parameters), parameter concentration, and recursive problem reduction.
- Hardware Evolution: The framework is designed to be reusable as hardware improves (e.g., IBM's Nighthawk processor with square lattice connectivity or D-Wave's Advantage2).

In conclusion, while current quantum hardware does not yet outperform classical heuristics like Simulated Annealing for dense QUBO problems, this work provides a vital, reproducible framework for tracking progress and identifying the specific technical hurdles (connectivity, noise, overhead) that must be overcome to achieve quantum advantage in optimization.