Cayley path and quantum computational supremacy: A proof of average-case #P-hardness of Random Circuit Sampling with quantified robustness
share
A one-parameter unitary-valued interpolation between any two unitary matrices (e.g., quantum gates) is constructed based on the Cayley transformation, which extends our previous work [15]. 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 previous work based on the truncations of the power series representation of the exponential function does not provide practical robustness. Explicit bound on noise resilience is proved, which for an n-qubit device with the near term experimental parameters is 2^-Θ(n^3.51) robustness with respect to additive error. Improving this to O(2^-n/poly(n)) would prove the quantum supremacy conjecture; and proving our construction optimal would disprove it
READ FULL TEXT