Characterizing Beyond-Classical Computation in Near-Term Devices

A critical question for the field of quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of state-of-the-art classical computers, achieving beyond-classical computation. We study the computational task of sampling from the output distribution of random quantum circuits. We introduce the cross entropy difference as a useful benchmark of random quantum circuits which approximates the circuit fidelity. We show that the cross entropy can be efficiently measured when circuit simulations are available. Beyond the classically tractable regime, the cross entropy can be extrapolated and compared with theoretical estimates to define a practical demonstration. We study the computational cost of several classical algorithms, and compare with the estimated fidelity for state-of-the-art superconducting qubits. We conclude that beyond-classical computation can be achieved in the near-term with approximately fifty qubits.