Q-score benchmark
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=6 10 to for n=16 | 1000 | / | QCE | Pasqal Pulser library | 18 | ||
| [3] | 2022/07 | x | MIS | UD G(n, p=1/2) | 500 for n=6 10 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 |
Q-score protocol
The Q-score protocol, introduced in [1], 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^R(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^R(n)}{C_{max}(n) - C^R(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 car be extended to other problems, it only depends on the ability of finding derivation of the values \(C_{max}(n)\) and \(C^R(n)\).
Some \(C^R(n)\) and \(C_{max}(n)\) based on specific graph classes for Max-Cut
\(C^R(n)\) and \(C_{max}(n)\) for Erdös-Renyi graphs \(G(n, p)\):
\[C^R(n) = \frac{pn^2}{4}\] \[C_{max}(n) = \frac{pn^2}{4} + \lambda_p n^{3/2}\]Ratio for \(k\)-regular graphs:
\[C^R(n) = \frac{nk}{4}\] \[C_{max}(n) = \frac{nk}{4} + \lambda_k n\]For these formulations, \(\lambda_p\) and \(\lambda_k\) values define the scaling factor of the optimal cut compared to a random average cut. These variables are defined analytically (see III.D of [1])
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
- no assumptions on error mitigation technique
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^R(n)\) is set to (proof in [4]):
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 to define \(C_{max}(n)\) from arbitrary problems by using exact methods. This method broadens the set of problems that can be evaluated of the Q-score at the expense of limiting the scalability of the method.
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.