Depth-scaling fine-grained quantum supremacy based on SETH and qubit-scaling fine-grained quantum supremacy based on Orthogonal Vectors and 3-SUM
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