Depth-scaling fine-grained quantum supremacy based on SETH and qubit-scaling fine-grained quantum supremacy based on Orthogonal Vectors and 3-SUM

02/22/2019
by   Tomoyuki Morimae, et al.
0

We first show that under SETH and its variant, strong and weak classical simulations of quantum computing are impossible in certain double-exponential time of the circuit depth. We next show that under Orthogonal Vectors, 3-SUM, and their variants, strong and weak classical simulations of quantum computing are impossible in certain exponential time of the number of qubits.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset