Cayley path and quantum computational supremacy: A proof of average-case #P-hardness of Random Circuit Sampling with quantified robustness

Abstract

A one-parameter unitary-valued interpolation between any two unitary matrices is constructed based on the Cayley transformation, which extends our work. The entries of the interpolated unitaries are shown to be low-degree rational functions in the parameter, which we proved can be efficiently determined using an extension of the Berlekamp-Welch algorithm. We prove that this path provides scrambled unitaries with probability distributions arbitrarily close to the Haar measure. We then prove the simplest known average-case #$P$-hardness of random circuit sampling (RCS), which is the task of sampling from the output distribution of a quantum circuit whose local gates are random Haar unitaries, and is the lead candidate for demonstrating quantum supremacy in the NISQ era. We show that a previous work based on the truncations of the power series representation of the exponential function does not provide practical robustness. Explicit bounds on noise resilience are proved, which on a grid of $\sqrt{n}\times\sqrt{n}$ qubits with circuit depth $\sqrt{n}$ is $2^{-\tilde{O}(n^{3})}$, and with constant-depth it is $2^{-\tilde{O}(n^{2})}$. Improvements to $O(2^{-n}/\text{poly}(n))$ would prove the quantum supremacy conjecture, which may be false.