Quantum computing is touted as a game changer that can potentially dramatically increase our computational capabilities despite the death of Moore’s law. We are still at the early stage of developing quantum technologies, and celebrated ‘killer-apps’ such as Shor’s algorithm (the culprit behind security concerns around breaking encryptions with quantum computers) are impossible to execute with current technologies. This, however, did not stop scientists from trying to demonstrate that their quantum devices are already capable of doing things impossible to do with a classical computer.
The first demonstration is Google’s quantum supremacy experiment using superconducting qubits [1], where a 53-qubit quantum computer is programmed to generate random outcomes that have non-trivial quantum correlations (random circuit sampling). Later, scientists at the University of Science and Technology of China (USTC) repeated the same scheme with more in 2021 [2] and 2022 [3] with 56 and 60 qubits, and Google recently increased their system size to 70 qubits in 2023 [4]. Using a different technology, scientists at USTC [5] and Xanadu [6] performed similar sampling tasks using optical devices (Gaussian boson sampling) in 2020 and 2022, respectively. USTC’s most recent boson sampling quantum supremacy experiment is performed in 2023 [7]. All of the experiments are believed to require an astronomical amount of time to simulate on the most powerful classical supercomputer. However, other scientists immediately started to build better classical algorithms to simulate these quantum experiments and challenged the quantum supremacy claims to vary degrees. Specifically, our recent work shows that Gaussian boson sampling quantum supremacy experiments can in fact be simulated fairly quickly on a classical supercomputer, and the quality of the simulation is higher than the experiment under all thus far testable metrics [8].
The reason why these quantum supremacy experiments might admit efficient classical simulation is that experiments are imperfect. Initially, theoretical analyses of quantum supremacy experimental proposals assume that the quantum devices are perfect. Another common assumption is that the quantum computer is able to explore to full space of possible quantum states (Hilbert space), which, as one may have heard, is exponentially large. In both random circuit sampling and Gaussian boson sampling, the device is randomly configured so that the system can reach a random quantum state from which outputs are sampled. The initial state is a simple state which gets ‘scrambled’ with quantum operations, and qubits or photons become quantumly correlated (entangled). The quantum state can potentially explore the entire Hilbert space if sufficiently many quantum operations are performed. Both assumptions are commonly used in the derivation of the hardness of classical simulation, which is not true in reality and makes the hardness of classical simulation of noisy quantum experiments an open question.
Experimental imperfections also come in multiple flavors, all of which can help classical simulation to defeat them. The first one is noise, which corrupts the quantum state and makes qubits or photons less entangled¹. As a result, scrambling quantum operations also add noise, and cannot be increased without limit if one wants to preserve some quantum entanglement. Interactions between arbitrary qubits or photons are also impossible due to device connectivity limitations. Together, these factors limit the quantum states that can be explored by the system, which means that not the full Hilbert space has to be considered if one wants to simulate it with a classical computer. Lastly, imperfect control also penalizes the experiment², which classical simulation does not suffer from.
However, our Gaussian boson sampling simulation exploits all of the above experimental imperfections, and we simulate the noisy quantum state (which has a lower cost than a noiseless state). For example, Xanadu’s largest experiment uses 288 optical modes with 407.64 and 147.65 average input and output photons. With our novel decomposition technique, it turns out that out of the 147.65 output photons, only 10.687 need to be simulated fully quantum mechanically, and the rest can be added to the quantum state later with minimal cost. Further, the severe connectivity limitation of the Xanadu experiments means that the entanglement is small, reducing the computational cost even further. The USTC experiments have better connectivity, but the photon number is smaller. Overall, our largest simulations of the largest quantum supremacy experiments [5,6,7] obtain the quantum state in 10 minutes and produces 10 million samples in 1 hour. Further, the simulations have better results than the experiments on all thus-far testable metrics³.
On the other hand, the philosophy of simulating random circuit sampling is to observe the fact that these experimental imperfections make the quantum states deviate rather far from the ground truth. Therefore, classical simulations that also deviate far from the ground truth (but are not necessarily close to the experiment) can potentially defeat the experiment. Thanks to many previous advancements in simulation techniques, Kalachev et al. and Pan et al. simulated the 2019 Google quantum supremacy experiments in 14.5 days in 2021 and 15 hours in 2022, respectively⁴. Further, in the most recent experiment from Google in 2023 [4], they combined and optimized numerous techniques, estimating that simulation on the most powerful supercomputers would take 6.18 seconds of their 2019 results. The more recent USTC experiments in 2021 [2] and 2022 [3] can be simulated in 25.3 minutes and 38.7 days, respectively. The 2023 experiment itself would take 47.2 years.
In conclusion, Google’s and USTC’s initial random circuit sampling and USTC’s and Xanadu’s Gaussian boson sampling quantum supremacy experiments no longer satisfy the original supremacy criteria proposed in these papers due to improved classical simulations, while the more recent Google and USTC random circuit sampling experiments remain hard to simulate. However, the standard of quantum supremacy could be adapted to rescue the claims of the older experiments⁵, future improvements in classical simulation could once again challenge the latest experiments, and future experiments will increase the system size and go beyond the simulable regime. The debate around the meaning of quantum supremacy as well as the extent to which it is realized or challenged will remain multifaceted, subjective, and provocative in the near future.
Footnotes:
- Noise can be understood as the system interacting with an unpredictable environment. If say qubit 1 interacts and correlates with something in the environment (for example, qubit 1 flips if only the environment is in state a), then the state of qubit 1 will depend on an environment that experimentalists have no knowledge of. This makes the state of qubit 1 completely random. In the extreme case where all qubits are randomized due to such interaction with the environment, the qubits do not share any entanglement and can be approximated as random bits easily.
- An example of imperfect control is rotating a state too much or too little due to calibration error. This means that (even in the noiseless case) the quantum state we get does not agree perfectly with what we think we will get (the ground truth). Since the measure of quality is how close the generated results are to the ground truth, this deviation will penalize the experiment.
- It is important to note that our work is inspired by numerous previous works, which contain various ingredients that our algorithm shares similarities with. A previous work (before Xanadu’s and USTC’s most recent experiments) also simulate the earlier USTC boson sampling experiments while obtaining better results on some metrics, but the simulation run time is not discussed in detail and the simulation cannot outperform the experiment on higher-order correlations [9].
- Many previous works also simulate this experiment with varying degrees of quality and caveats.
- One can propose an alternative benchmark that may highlight the differences between experiment and simulation. For example, [9] provides evidence that their samples have better third-order correlation and marginal distributions, which is argued to be sufficient evidence that their simulation should also perform better on ‘gold-standard’ benchmarks that are too hard to compute. In light of this, experimentalists can argue that the goal can be changed to getting good fourth and fifth-order correlations. As long as something is hard classically, there is quantum advantage. In the case of our boson sampling simulation, although we can generate millions of samples in an hour, resulting in a very high average rate, there is a 10-minute cost to first generate the quantum state before any samples can be generated. If the problem of boson sampling changes from producing millions of samples to producing only a few samples, then the rate of the classical simulation will be limited by the 10-minute cost, whereas the quantum experiment can still generate thousands of samples per second. This setup could be useful in the case of verifiable random number generation, whose proof is known for random circuit sampling but not boson sampling.
References
[1]: Arute, F., Arya, K., Babbush, R. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019).
[2]: Wu, Y., Bao, W., Cao, S. et al. Strong quantum computational advantage using a superconducting quantum processor. Phys. Rev. Lett. 127, 180501 (2021).
[3]: Zhu, Q., Cao, S., Chen, F. et al. Quantum computational advantage via 60-qubit 24-cycle random circuit sampling. Science Bulletin 67, 240 (2022)
[4]: Google Quantum AI and Collaborators. Phase transition in Random Circuit Sampling. Arxiv preprint 2304.11119 (2023).
[5]: Zhong, H., Wang, H., Deng, Y. et al. Quantum computational advantage using photons. Science370,1460–1463(2020).
[6]: Madsen, L.S., Laudenbach, F., Askarani, M.F. et al. Quantum computational advantage with a programmable photonic processor. Nature 606, 75–81 (2022).
[7]: Deng, Y., Gu, Y., Liu, H. et al. Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage. Arxiv preprint 2304.12240 (2023).
[8]: Oh, C., Liu, M., Alexeev, Y. et al. Tensor network algorithm for simulating experimental Gaussian boson sampling. Arxiv preprint 2306.03709 (2023).
[9]: Villalonga, B., Niu, M., Li, L. et al. Efficient approximation of experimental Gaussian boson sampling. Arxiv preprint 2109.11525 (2022).