Q-score benchmark
Benchmarking results
List of acronyms:
AC: Advanced Compilation method
CE: Constructor Evaluation (checked if the evaluation is done by the chip manufacturer)
EM: Error mitigation
ER: Erdös-Renyi
HS: Hybrid Solver
QA: Quantum Annealer
QC: Quantum Circuit
QCE: Quantm Computer Emulation
SA: Simulated Annealing
SP: Scientific paper (checked if a scientific paper explain the results)
TS: Tabu Search
UD: Unit Disk
| Date & Ref | CE | SP | Problem | Graph class | #Instances | Shots | Time limit | Method | CPU / QPU | Score | Comment |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 2021/02 [1] | x | Max-Cut | ER G(n, p=1/2) | 100 | 2048 | / | QCE | Grid connectivity Depolarizing noise $$\epsilon_1=0.4 %$$$$\epsilon_2=2 %$$ | 11 | ||
| 2021/02 [1] | x | Max-Cut | ER G(n, p=1/2) | 100 | 2048 | / | QCE | Full connectivitydepolarizing noise$$\epsilon_1=0.4 %$$$$\epsilon_2=2 %$$ | 21 | ||
| 2022/08 [2] | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | TS | i7-7600u | 2300 | |||
| 2022/08 [2] | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | SA | i7-7600u | 5800 | |||
| 2022/08 [2] | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave 2000Q | 70 | |||
| 2022/08 [2] | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave Advantage | 140 | |||
| 2022/08 [2] | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave hybrid solver | 12500 | |||
| 2022/07 [3] | x | Max-Cut | ER G(n, p=1/2) | 500 for n=610 to for n=16 | 1000 | / | QCE | Pasqal Pulser library | 18 | ||
| 2022/07 [3] | x | MIS | UD G(n, p=1/2) | 500 for n=610 to for n=16 | 1000 | / | QCE | Pasqal Pulser library | 18 | ||
| 2023/02 [4] | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | TS | i7-7600u | 4900 | |||
| 2023/02 [4] | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | SA | i7-7600u | 9100 | |||
| 2023/02 [4] | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave 2000Q | 70 | |||
| 2023/02 [4] | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave Advantage | 110 | |||
| 2023/02 [4] | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | HS | D-Wave hybrid solver | 12500 | |||
| 2023/02 [4] | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | QC | QuTech Starmon-5 | 5 | |||
| 2023/02 [4] | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | QC | IBM Gadalupe | 5 | |||
| 2023/10 [5] | x | Max-Cut | ER G(n, p=1/2) | 100 | / | QC | IQM-20 | 8 | |||
| 2024/02 [6] | x | x | Max-Cut | ER G(n, p=1/2) | 100 | 2048 | / | QC | IQM Spark | 6 | |
| 2024/02 [7] | x | Max-Cut | ER G(n, p=1/2) | 100 | 2048 | / | QC | IQM-20 | 11 | ||
| 2024 [8] | x | Max-Cut | / | / | QC | Quandela Altaïr | 6 | EM & AC |
Motivation
The Q-score protocol, introduced by S. Martiel et al. in 2021 [1] aims to establish an application-centric, hardware agnostic, and scalable figure of merit for assessing the performance of quantum computers. A key motivation behind this protocol is to identify challenging real-world optimization problems whose solution processes could be accelerated through quantum computing.
Protocol
The Q-score protocol measures the maximum size of Maxcut instances that can be solved effectively on a quantum computer. The main idea is to pick a class of random graphs (e.g., Erdös-Renyi graphs with \(n\) nodes and a specific edge probability) and to analytically derive the maximum cut size \(C_{max}(n)\) and average random cut size \(C_{rand}(n)\) for this class. The average expectation value obtained from the sampling of the quantum computer \(C^Q(n)\) is used to compute the ratio \(\beta(n)\):
\[\beta(n) = \frac{C^Q(n) - C_{rand}(n)}{C_{max}(n) - C_{rand}(n)}\]The quantum computer passes the Q-score for instances of size \(n\) if \(\beta(n) > \beta^*\) (\(\beta^* \in ]0,1[\)), where \(\beta^*\) represents the level of difficulty of the test. The formula used to compute the ratio depends on the class of studied graphs. For their experiments, the authors arbitrarily set \(\beta^*=0.2\).
The final value of the score is defined by:
\[n^* = \max \{ n \in \mathbb{N}, \beta(n) > \beta^* \}\]This score can be extended to other problems, it only depends on the ability of finding derivation of the values \(C_{max}(n)\) and \(C_{rand}(n)\).
Assumptions
- The Q-score does not have runtime limit, but considers that the classical algorithm implementation runs in polynomial time. Subsequent studies has proposed a 60s runtime limit for each instance (see [4]).
- no assumptions on compilation processing (but the implementation should run in polynomial time).
- no assumptions on error mitigation technique (but the implementation should run in polynomial time).
Configuration of experiments
- Size of instance set recommended: 100
- Number of shots recommended: 2048
- Default level of difficulty: \(\beta^* = 0.2\)
Implementations
Several implementations of the Q-Score are available on GitHub:
- The initial implementation created by the authors of the Q-score is available here.
- A tutorial implementation from the QCMet software repository [9] is available here.
- An implementation from the IQM Benchmarks suite is available here.
Extensions to the Q-score
Max-clique extension
In [4], the authors extend the Q-Score to the Max-clique problem. For Erdös-Renyi graphs \(G(n, p)\), the average random cost \(C_{rand}(n)\) is set to (proof in [4]):
\[C_{rand}(n) = \sum_{i=1}^n i \times (1-p^i)p^{i(i-1)/2}\]For this kind of problem, \(C_{max}\) is set to (proof in [10]):
\[C_{max}(n) = 2 \log_2(n) - 2 \log_2(\log_2(n)) + 2 \log_2\left(\frac{e}{2}\right) +1\]An implementation of the Q-score Max-clique is available here.
Empirical optimal and random average cost
In [3], the authors propose determining \(C_{max}(n)\) for arbitrary problems using exact methods, thereby circumventing the need to derive theoretical bounds for both \(C_{max}\) and \(C_{rand}\). While this approach expands the range of problems to which the Q-score can be applied, it does so at the cost of reduced scalability.
References
- [1]S. Martiel, T. Ayral, and C. Allouche, “Benchmarking quantum coprocessors in an application-centric, hardware-agnostic, and scalable way,” IEEE Transactions on Quantum Engineering, vol. 2, pp. 1–11, 2021.
- [2]W. van der Schoot, D. Leermakers, R. Wezeman, N. Neumann, and F. Phillipson, “Evaluating the Q-score of Quantum Annealers,” in 2022 IEEE International Conference on Quantum Software (QSW), 2022, pp. 9–16.
- [3]W. da S. Coelho, M. D’Arcangelo, and L.-P. Henry, “Efficient protocol for solving combinatorial graph problems on neutral-atom quantum processors,” arXiv preprint arXiv:2207.13030, 2022.
- [4]W. van der Schoot, R. Wezeman, N. M. P. Neumann, F. Phillipson, and R. Kooij, “Q-score Max-Clique: The First Quantum Metric Evaluation on Multiple Computational Paradigms,” arXiv preprint arXiv:2302.00639, 2023.
- [5]IQM, “Finland launches a 20-qubit quantum computer - development towards more powerful quantum computers continues.” 2023 [Online]. Available at: https://www.meetiqm.com/newsroom/press-releases/finland-launches-a-20-qubit-quantum-computer
- [6]J. Rönkkö et al., “On-premises superconducting quantum computer for education and research,” EPJ Quantum Technology, vol. 11, no. 1, p. 32, 2024.
- [7]IQM, “IQM quantum computers achieves a new benchmark result on 20-qubit quantum computer.” 2024 [Online]. Available at: https://www.meetiqm.com/newsroom/press-releases/iqm-achieves-20-qubit-benchmark-result
- [8]Quandela, “Introducing Quandela cloud 2.0.” 2024 [Online]. Available at: https://www.quandela.com/cloud/
- [9]D. Lall et al., “A review and collection of metrics and benchmarks for quantum computers: definitions, methodologies and software,” arXiv preprint arXiv:2502.06717, 2025.
- [10]D. W. Matula, The largest clique size in a random graph. Department of Computer Science, Southern Methodist University Dallas, Texas …, 1976.