Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem

@misc{olivier2026quantum,
  title = {{Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem}},
  author = {Noé Olivier and Michel Nowak},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.19931},
  eprint = {2609.19931},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.19931},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem
AU  - Noé Olivier
AU  - Michel Nowak
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2609.19931
UR  - https://arxiv.org/abs/2609.19931
AB  - Recent advances in quantum computing hardware toward fault-tolerance have increased interest in evaluating near-term quantum platforms on application-relevant quantum algorithms. In this work, we introduce Quantum WalkScore (QWS), a scalable application-oriented benchmark designed to assess the performance of NISQ and future fault-tolerant quantum computers in executing essential quantum routines --discrete-time quantum walks and quantum amplitude amplification-- to solve the graph nodefinding problem (marked-vertex search). QWS quantifies performance by scoring the largest problem size for which a designated target node can be found with success probability above a defined threshold. In addition to the complete protocol description, we provide example parameter-selection scenarios designed from noiseless simulation results and demonstrate QWS evaluation through experimental runs on multiple generations of IBM real quantum processors.
ER  -