Quantum supremacy

The comparison between quantum and classical computers can be based on various criteria, such as processing time, computational accuracy, and energy consumption. Quantum supremacy refers to experiments demonstrating that a quantum computer can solve a specific computational task significantly faster than a classical computer. These tasks are typically designed to be exceptionally challenging for classical systems, requiring exponentially scaling resources with the problem size. While such tasks may not have practical applications, they serve as a proof of concept for the superior computational power of quantum systems.

Protocols

Random Circuit Sampling (RCS)
Boson Sampling (BS)
In a nutshell, boson sampling is a protocol used to benchmark the performance of Boson-based QPUs (photons in this case). The task consists of running a randomly generated quantum circuit of optical elements (beam splitters and phase shifters) with a specific initial state several times. It is then possible to build an output distribution from these samples, representing the experimental probability output associated with each quantum state. This sampling task is hard for classical computers: it requires exponential resources to get approximately the same output distribution as the quantum computer. Resources required by classical systems to emulate the quantum computer are usually interpolated for large experiments. For these experiments, quantum systems are expected to work correctly (there is, unfortunately, no direct means to check that the QPU is doing everything right).
Quantum simulation (Qsim)
In a nutshell, quantum simualtion tasks attempt to simulate a continuous time quantum system evolution. It can be done either using an analog machine that simulates the whole process or using a digital quantum computer implementing unitaries that are built from an approximation (Trotterization) of the initial quantum evolution. In this frame, the performance test consits in sampling the probability distribution corresponding to the quantum evolution with a quantum computer faster than a classical emulation of this evolution.

Experiments

This summary is an adaptation of the table provided by R. Larose in [1] (Table 1.). We follow the terminology exposed by R. Larose to define experiments that have been challenged, weakly refuted and strongly refuted:

Challenged: Any work that present a significant improvement in the classical simulation time.
Weak refutation: Any work that present an improved classical simulation which reasonably demonstrates that the quantum computing claim could be classically simulated in the near future.
Strong refutation: Any work that present a classical simulation of the quantum supremacy experiment faster than the quantum computer.

List of acronyms:
RCS: Random Circuit Sampling.
GBS: Gaussian Boson Sampling.
Qsim: Quantum simulation.
n: Number of qubits involved in the experiment.
m: Number of layers for the RCS experiments, Number of modes for GBS experiments.
Challenged: Litterature that either improve the classical simulation or question some parts of the claim.
Weakly refuted: Litterature improving classical simulation with new algorithms suggesting classical computers powerfull enough could break the claim.
Refuted: Litterature providing classical experiments that surpasses the supremacy claim.

Date & Ref.	Pb.	n	m	Group & Chip	Type	Challenged Ref.	Weakly Refuted Ref.	Refuted Ref.
2019/10 [2]	RCS	53	20	Google Sycamore	Superconducting	[3], [4], [5], [6], [7], [8], [9]	[10], [11]	[12]
2020/03 [13]	GBS	50	100	USTC Jiuzhang	Photonic		[14]
2021/06 [15]	RCS	56	20	USTC Zuchongzhi	Superconducting	[11], [16]
2021/06 [17]	GBS	50	144	USTC Jiuzhang 2.0	Photonic		[14]
2021/09 [18]	RCS	60	24	USTC Zuchongzhi	Superconducting	[16], [9]
2022/06 [19]	GBS	216	216	Xanadu Borealis	Photonic		[14]
2023/04 [16]	RCS	67	32	Google Sycamore	Superconducting
2023/04 [16]	RCS	70	24	Google Sycamore	Superconducting
2023/04 [20]	GBS	50	144	USTC Jiuzhang 3.0	Photonic		[14]
2023/06 [21]	Qsim	127	60	IBM Kyiv	Superconducting	[22]		[23], [24], [25], [26], [27], [28], [27]
2024/03 [29]	Qsim	567	-	D-Wave ADV1/2	Superconducting Annealing	[30], [31]
2024/12 [32]	RCS	83	32	USTC Zuchongzhi 3.0	Superconducting

References

[1]R. LaRose, “A brief history of quantum vs classical computational advantage,” arXiv preprint arXiv:2412.14703, 2024.
[2]F. Arute et al., “Quantum supremacy using a programmable superconducting processor,” Nature, vol. 574, no. 7779, pp. 505–510, Oct. 2019, doi: 10.1038/s41586-019-1666-5. [Online]. Available at: http://dx.doi.org/10.1038/s41586-019-1666-5
[3]E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, and R. Wisnieff, “Leveraging secondary storage to simulate deep 54-qubit sycamore circuits,” arXiv preprint arXiv:1910.09534, 2019.
[4]J. Gray and S. Kourtis, “Hyper-optimized tensor network contraction,” Quantum, vol. 5, p. 410, 2021.
[5]Y. Zhou, E. M. Stoudenmire, and X. Waintal, “What limits the simulation of quantum computers?,” Physical Review X, vol. 10, no. 4, p. 041038, 2020.
[6]C. Huang et al., “Classical simulation of quantum supremacy circuits,” arXiv preprint arXiv:2005.06787, 2020.
[7]F. Pan and P. Zhang, “Simulating the Sycamore quantum supremacy circuits,” arXiv preprint arXiv:2103.03074, 2021.
[8]Y. Liu et al., “Closing the’ quantum supremacy’ gap: achieving real-time simulation of a random quantum circuit using a new sunway supercomputer,” in Proceedings of the international conference for high performance computing, networking, storage and analysis, 2021, pp. 1–12.
[9]X. Liu et al., “Redefining the quantum supremacy baseline with a new generation sunway supercomputer,” arXiv preprint arXiv:2111.01066, 2021.
[10]F. Pan, K. Chen, and P. Zhang, “Solving the sampling problem of the sycamore quantum circuits,” Physical Review Letters, vol. 129, no. 9, p. 090502, 2022.
[11]G. Kalachev, P. Panteleev, P. F. Zhou, and M.-H. Yung, “Classical sampling of random quantum circuits with bounded fidelity,” arXiv preprint arXiv:2112.15083, 2021.
[12]X.-H. Zhao et al., “Leapfrogging Sycamore: Harnessing 1432 GPUs for 7\times faster quantum random circuit sampling,” National Science Review, p. nwae317, 2024.
[13]H.-S. Zhong et al., “Quantum computational advantage using photons,” Science, vol. 370, no. 6523, pp. 1460–1463, 2020.
[14]C. Oh, M. Liu, Y. Alexeev, B. Fefferman, and L. Jiang, “Classical algorithm for simulating experimental Gaussian boson sampling,” Nature Physics, vol. 20, no. 9, pp. 1461–1468, 2024.
[15]Y. Wu et al., “Strong quantum computational advantage using a superconducting quantum processor,” Physical review letters, vol. 127, no. 18, p. 180501, 2021.
[16]A. Morvan et al., “Phase transitions in random circuit sampling,” Nature, vol. 634, no. 8033, pp. 328–333, 2024.
[17]H.-S. Zhong et al., “Phase-programmable gaussian boson sampling using stimulated squeezed light,” Physical review letters, vol. 127, no. 18, p. 180502, 2021.
[18]Q. Zhu et al., “Quantum computational advantage via 60-qubit 24-cycle random circuit sampling,” Science bulletin, vol. 67, no. 3, pp. 240–245, 2022.
[19]L. S. Madsen et al., “Quantum computational advantage with a programmable photonic processor,” Nature, vol. 606, no. 7912, pp. 75–81, 2022.
[20]Y.-H. Deng et al., “Gaussian boson sampling with pseudo-photon-number-resolving detectors and quantum computational advantage,” Physical review letters, vol. 131, no. 15, p. 150601, 2023.
[21]Y. Kim et al., “Evidence for the utility of quantum computing before fault tolerance,” Nature, vol. 618, no. 7965, pp. 500–505, 2023.
[22]K. Kechedzhi et al., “Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments,” Future Generation Computer Systems, vol. 153, pp. 431–441, 2024.
[23]J. Tindall, M. Fishman, E. M. Stoudenmire, and D. Sels, “Efficient tensor network simulation of ibm’s eagle kicked ising experiment,” Prx quantum, vol. 5, no. 1, p. 010308, 2024.
[24]E. G. D. Torre and M. M. Roses, “Dissipative mean-field theory of IBM utility experiment,” arXiv preprint arXiv:2308.01339, 2023.
[25]H.-J. Liao, K. Wang, Z.-S. Zhou, P. Zhang, and T. Xiang, “Simulation of IBM’s kicked Ising experiment with projected entangled pair operator,” arXiv preprint arXiv:2308.03082, 2023.
[26]S. Anand, K. Temme, A. Kandala, and M. Zaletel, “Classical benchmarking of zero noise extrapolation beyond the exactly-verifiable regime,” arXiv preprint arXiv:2306.17839, 2023.
[27]T. Begušić, J. Gray, and G. K.-L. Chan, “Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance,” Science Advances, vol. 10, no. 3, p. eadk4321, 2024.
[28]T. Begušić and G. K. Chan, “Fast classical simulation of evidence for the utility of quantum computing before fault tolerance,” arXiv preprint arXiv:2306.16372, 2023.
[29]A. D. King et al., “Computational supremacy in quantum simulation,” arXiv preprint arXiv:2403.00910, 2024.
[30]J. Tindall, A. Mello, M. Fishman, M. Stoudenmire, and D. Sels, “Dynamics of disordered quantum systems with two-and three-dimensional tensor networks,” arXiv preprint arXiv:2503.05693, 2025.
[31]L. Mauron and G. Carleo, “Challenging the Quantum Advantage Frontier with Large-Scale Classical Simulations of Annealing Dynamics,” arXiv preprint arXiv:2503.08247, 2025.
[32]D. Gao et al., “Establishing a new benchmark in quantum computational advantage with 105-qubit zuchongzhi 3.0 processor,” Physical Review Letters, vol. 134, no. 9, p. 090601, 2025.