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)xsqrt(n) qubits with circuit depth sqrt(n) is 2^O(-n^3), and with constant-depth it is 2^O(-n^2). Improvements to O(2^(−n)/poly(n)) would prove the quantum supremacy conjecture, which may be false. *The Frontiers Foundation and the MIT-IBM collaborative grant