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
| Ref | Year | CE | SP | Problem | Graph class | #Instances | Shots | Time limit | Method | CPU / QPU | Score | Comment |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| [1] | 2021/02 | x | Max-Cut | ER G(n, p=1/2) | 100 | 2048 | / | QCE | Grid connectivity Depolarizing noise $$\epsilon_1=0.4 %$$$$\epsilon_2=2 %$$ | 11 | ||
| [1] | 2021/02 | x | Max-Cut | ER G(n, p=1/2) | 100 | 2048 | / | QCE | Full connectivity depolarizing noise $$\epsilon_1=0.4 %$$$$\epsilon_2=2 %$$ | 21 | ||
| [2] | 2022/08 | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | TS | i7-7600u | 2300 | |||
| [2] | 2022/08 | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | SA | i7-7600u | 5800 | |||
| [2] | 2022/08 | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave 2000Q | 70 | |||
| [2] | 2022/08 | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave Advantage | 140 | |||
| [2] | 2022/08 | x | Max-Cut | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave hybrid solver | 12500 | |||
| [3] | 2022/07 | x | Max-Cut | ER G(n, p=1/2) | 500 for n=610 to for n=16 | 1000 | / | QCE | Pasqal Pulser library | 18 | ||
| [3] | 2022/07 | x | MIS | UD G(n, p=1/2) | 500 for n=610 to for n=16 | 1000 | / | QCE | Pasqal Pulser library | 18 | ||
| [4] | 2023/02 | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | TS | i7-7600u | 4900 | |||
| [4] | 2023/02 | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | SA | i7-7600u | 9100 | |||
| [4] | 2023/02 | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave 2000Q | 70 | |||
| [4] | 2023/02 | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | QA | D-Wave Advantage | 110 | |||
| [4] | 2023/02 | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | HS | D-Wave hybrid solver | 12500 | |||
| [4] | 2023/02 | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | QC | QuTech Starmon-5 | 5 | |||
| [4] | 2023/02 | x | Max-clique | ER G(n, p=1/2) | 100 | 60s | QC | IBM Gadalupe | 5 | |||
| [5] | 2023/10 | x | Max-Cut | ER G(n, p=1/2) | 100 | / | QC | IQM-20 | 8 | |||
| [6] | 2024/02 | x | x | Max-Cut | ER G(n, p=1/2) | 100 | 2048 | / | QC | IQM Spark | 6 | |
| [7] | 2024/02 | x | Max-Cut | ER G(n, p=1/2) | 100 | 2048 | / | QC | IQM-20 | 11 | ||
| [8] | 2024 | 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\)
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 [9]):
\[C_{max}(n) = 2 \log_2(n) - 2 \log_2(\log_2(n)) + 2 \log_2\left(\frac{e}{2}\right) +1\]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. W. Matula, The largest clique size in a random graph. Department of Computer Science, Southern Methodist University Dallas, Texas …, 1976.