(英) |
Recently, Google's research team has succeeded in sampling the output of a randomly given 53-qubit quantum circuit 1 million times in 200 seconds.
This sampling problem is called quantum random circuit sampling (RCS),
and it is important to prove the hardness of RCS for classical computers .
Movassagh showed that RCS within $ 2^{-Omega (m^2)} $ additive error, is hard on classical computers, assuming that the polynomial hierarchy does not collapse
where $m$ is the number of gates in the quantum circuit.
In this study, we improve Movassagh's proof, and show the classical hardness of RCS within $ 2^{-Omega (mlog m)} $ additive error. |