⚛️ quantum physics

Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem

This paper introduces Quantum WalkScore (QWS), a scalable, application-oriented benchmark that evaluates the performance of NISQ and future fault-tolerant quantum computers by measuring their ability to solve the graph nodefinding problem using discrete-time quantum walks and amplitude amplification, validated through both simulations and experiments on IBM quantum processors.

Original authors: Noé Olivier, Michel Nowak

Published 2026-09-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Noé Olivier, Michel Nowak

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

In the quest to build machines that can solve problems beyond the reach of today's supercomputers, scientists are racing to develop quantum computers. These devices do not rely on the simple on-off switches of classical bits but instead use quantum bits, or qubits, which can exist in multiple states at once. This unique property allows them to explore vast possibilities simultaneously. However, building a machine that can reliably hold these fragile quantum states is incredibly difficult. Current devices are often plagued by noise and errors, leading researchers to ask a critical question: how do we know if a quantum computer is actually working, and how good is it at solving real-world tasks? To answer this, the scientific community needs more than just a list of error rates; they need a practical test that measures whether a machine can successfully navigate a complex problem.

A team of researchers at CortAIx Labs in France has proposed a new way to measure this capability, called Quantum WalkScore. Instead of testing abstract mathematical properties, their benchmark asks the computer to perform a specific, useful task: finding a hidden target within a network. Imagine a traveler trying to find a specific city in a vast map of connected roads. A classical computer would check the roads one by one, but a quantum computer can explore many paths at once. The researchers focused on two powerful tools that quantum computers use for this kind of search: a method called a discrete-time quantum walk, which acts like a sophisticated way of moving through the network, and a technique called amplitude amplification, which boosts the chances of finding the right answer. By combining these tools, the team created a test that measures how large a network a quantum computer can search before the noise in the machine causes it to fail.

The benchmark is designed to be scalable, meaning it can start with a very small network and grow larger and more complex as the hardware improves. The researchers tested this protocol on two types of network shapes: a simple ring, where every point connects to two neighbors, and a more complex grid that wraps around on itself, like the surface of a donut. They defined a clear goal: the computer must find the hidden target with a success rate higher than what would be expected by pure luck. If the computer succeeds, the test moves to a slightly larger or more difficult version of the problem. The final score is simply the size of the largest network the computer managed to solve before it could no longer find the target reliably. This approach gives a concrete number that anyone can understand, representing the practical limit of the machine's current ability.

To see how this works in practice, the researchers ran their tests on several generations of real quantum processors provided by IBM, including models named Heron and Nighthawk. They also ran simulations on a perfect, noiseless computer to see what the results should look like in an ideal world. The simulations showed that with the right settings, the quantum algorithms could theoretically solve very large problems, finding the target with high confidence. However, when the team ran the same tests on the actual physical machines, the results were much more modest. The noise and errors inherent in today's hardware meant that the computers could only successfully solve very small networks. For the ring-shaped networks, the best-performing machines managed to find the target in networks of a specific small size, but as the network grew, the success rate dropped to the level of a random guess.

The study highlights a significant gap between what quantum algorithms can do in theory and what current hardware can actually achieve. The researchers found that the complexity of the circuit required to run the search grows rapidly as the problem gets bigger. On the machines they tested, circuits that were too deep or complex became overwhelmed by errors, causing the quantum information to degrade before the answer could be found. Even with the most advanced processors available at the time of the study, the team could only demonstrate a proof-of-concept score, proving that the method works but also revealing just how much the hardware needs to improve. The results suggest that while the mathematical tools are ready, the physical machines are still in the early stages of being able to handle the demanding tasks required for real-world applications like logistics or database searching.

This new benchmark, Quantum WalkScore, offers a clear and honest way to track progress. It does not rely on theoretical potential or idealized simulations but measures the actual performance of the machine in a controlled, repeatable way. By establishing a standard that requires the computer to beat random chance on a specific graph problem, the researchers provide a yardstick for the entire field. As quantum hardware continues to evolve, becoming more stable and less prone to errors, this score will naturally increase. The work serves as a reminder that the path to powerful quantum computing is a gradual climb, where each step up in performance must be verified by successfully solving a problem that was previously out of reach. The researchers have laid out a map for this journey, showing exactly where the machines stand today and what they must overcome to reach the future.

Technical Summary: Quantum WalkScore (QWS)

Problem Definition
The paper addresses the need for application-oriented benchmarks to evaluate the maturity of Noisy Intermediate-Scale Quantum (NISQ) and future fault-tolerant quantum computers. While existing benchmarks focus on physical gate fidelity or random circuit sampling, there is a scarcity of benchmarks utilizing promising quantum routines, specifically Discrete-Time Quantum Walks (DTQW) and Quantum Amplitude Amplification (AA), to solve practical graph problems. The authors focus on the graph nodefinding problem: identifying a specific "marked" target node $v_t$ within an undirected graph starting from a source node $v_0$ . This problem serves as a fundamental building block for real-world applications such as telecommunications routing, database search, and complex network analysis.

Methodology: The Quantum WalkScore (QWS) Protocol
The authors propose Quantum WalkScore (QWS), a scalable benchmark protocol designed to measure the largest problem size a quantum computer can solve successfully.

Graph Families: The benchmark utilizes two specific graph topologies to balance simplicity, scalability, and hardware applicability:
1. Cycle Graphs: 1D structures with $2^n$ nodes, where each node connects to two neighbors.
2. 2D-Torus Graphs: 2D structures with $2^n \times 2^n$ nodes, where each node connects to four neighbors (periodic boundary conditions).
Problem Instance: Defined by $(n, d)$ , where $n$ is the number of qubits and $d$ is the distance (shortest path edges) between the source and target nodes.
Algorithmic Routine:
1. Initialization: The system is initialized in the state $|v_0\rangle$ .
2. Discrete-Time Quantum Walk (DTQW): The walker evolves for $num\_w$ steps. The protocol requires $num\_w \ge d$ and $num\_w \equiv d \pmod 2$ to ensure reachability. A Hadamard coin is used for an unbiased walk.
3. Amplitude Amplification (AA): The DTQW routine is embedded within an AA framework (Brassard et al.) to boost the probability of measuring the target state. This involves $num\_aa$ iterations of reflection about the target and the initial state.
4. Measurement: The success probability $p_{exp}$ is measured as the probability of observing the target node state.
Scoring Criteria:
- Threshold Probability ( $p^*$ ): A dynamic threshold is defined to ensure success is significantly better than random guessing. For distance $d \le 2$ , $p^* = 1/3$ . For $d > 2$ , $p^* = 1/5 + 1/2^d$ .
- Metric: The success probability is averaged over multiple batches (4 batches of 1000 shots) and multiple target node instances (2 for cycles, 4 for torus).
- QWS Score: The score is the largest problem size $(n, d)$ for which the measured success probability exceeds $p^*$ before the first failure. The score is calculated as $QWS_{cycle} = 2^{e_n-1} + e_d$ and $QWS_{torus} = 2^{e_n} + e_d$ , where $(e_n, e_d)$ is the last successful instance.

Key Contributions

Protocol Design: Introduction of a complete, application-oriented benchmark protocol that integrates DTQW and AA, two routines critical for future quantum algorithms.
Scalability and Reproducibility: The protocol is designed to be applicable to any gate-based quantum computer, with standardized experimental parameters (shot counts, batching) and flexible algorithmic parameters ( $num\_w$ , $num\_aa$ ) left to the end-user to optimize.
Theoretical and Empirical Analysis: The paper provides theoretical guarantees for the existence of parameters that can theoretically solve any problem size, alongside detailed resource estimation (circuit depth scaling) for both algorithmic and native hardware implementations.
Experimental Validation: The protocol is executed on three generations of IBM quantum processors (Heron r2, Heron r3, and Nighthawk r1), providing a proof-of-concept evaluation of current hardware capabilities.

Results

Noiseless Simulations: Simulations on an ideal quantum computer demonstrate that the benchmark is solvable for large problem sizes. In the "suff-perf" scenario (minimizing AA iterations), success probabilities remain close to the threshold. In the "best-perf" scenario, success probabilities approach 1, though this requires higher circuit depths.
Circuit Depth Scaling: Theoretical algorithmic depth scales as $O(nd)$. However, when transpiled to IBM's Heron architecture, the native depth scales as $O(n^{3.45}d)$ for cycle graphs and $O(n^{2.2}d)$ for 2D-torus graphs, highlighting the significant overhead of hardware mapping.
Experimental Performance on IBM Hardware:
- Experiments on the ibm_kingston (Heron r2) processor showed that success probabilities drop rapidly as problem size increases due to noise and decoherence.
- The system successfully passed the threshold only up to problem size (3, 1). The success probability plummeted to results similar to random guesses for subsequent sizes, with the exception of problem size (4, 1), which did not constitute a continuous success sequence. Consequently, the Quantum WalkScore for cycle graphs was determined to be 5 under the "suff-perf" scenario.
- For larger instances (e.g., depth > 700 gates), the results degraded to levels indistinguishable from random guessing.
- Comparisons across Heron r2, Heron r3, and Nighthawk r1 showed similar trends, with Heron r3 offering slightly better accuracy, but all current architectures struggled with circuits exceeding ~1000 gates.

Significance and Claims
The paper claims that QWS serves as a necessary tool to bridge the gap between abstract hardware metrics and practical application performance. By focusing on the graph nodefinding problem, it directly evaluates a hardware's ability to execute essential quantum primitives (DTQW and AA) required for optimization and search tasks.

The authors emphasize that the benchmark highlights the interplay between algorithmic parameters and hardware limitations. The results demonstrate that while the theoretical framework allows for solving large problems, current NISQ devices are limited by circuit depth and error accumulation. The paper concludes that QWS provides a meaningful, interpretable score for tracking the maturation of quantum computers, distinguishing performance across NISQ and future Fault-Tolerant Quantum Computing (FTQC) devices. The modest score of 5 achieved on current hardware underscores the significant technological challenges remaining before these algorithms can be applied to large-scale practical problems.

Technical Summary: Quantum WalkScore (QWS)

More like this