Whether quantum computers can surpass classical computers in specific problems is an important problem in quantum computing, it is known as "quantum advantage problem" (or "quantum supremacy" problem). In 2019, Google's quantum computing team released the Sycamore quantum circuit with 53 quantum bits and 20 cyclics of unitary operations, which can complete the approximate sampling task from the final state of the Sycamore quantum circuit in 200 seconds. Google estimated that if this task is completed using classical computing, it will take 10,000 years even on a supercomputer.

Theoretically, the sampling problem of quantum circuits can be completed in polynomial time using quantum computers, but for classical computers, its computational complexity is very high, especially for random quantum circuits. At present, the upper bound of classical computational complexity cannot be given for this problem, so the estimation of computational time can only rely on the speculation of specific algorithms. In the 2019 paper, Google selected the best classical method they thought at that time - Schr?dinger Feynmann algorithm, based on which it estimated the classical computing time, and reached the conclusion of "10000 years of supercomputing". This leaves a loophole: perhaps there is a better classical algorithm, whose calculation time is be much less than estimate of Google.

In the recently published work, Prof. Pan ZHANG, his Ph.D student Feng PAN, and master student Keyang CHEN, of the Institute of Theoretical Physics, proposed a new tensor network method, which greatly reduced the classical computational complexity of the random quantum circuit sampling task, reducing the expected calculation time of the sycamore sampling problem from 10000 years (estimated by Google) to tens of seconds, which is even faster than Google's quantum hardware.

Link: 

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.129.090502

Contact:
Institute of Theoretical Physics
Pan Zhang
Email: panzhang@itp.ac.cn