  Fine-grained quantum supremacy is a study of proving (nearly) tight time
lower bounds for classical simulations of quantum computing under "fine-grained
complexity" assumptions. We show that under conjectures on Orthogonal Vectors
(OV), 3-SUM, All-Pairs Shortest Paths (APSP) and their variants, strong and
weak classical simulations of quantum computing are impossible in certain
exponential time with respect to the number of qubits. Those conjectures are
widely used in classical fine-grained complexity theory in which polynomial
time hardness is conjectured. All previous results of fine-grained quantum
supremacy are based on ETH, SETH, or their variants that are conjectures for
SAT in which exponential time hardness is conjectured. We show that there exist
quantum circuits which cannot be classically simulated in certain exponential
time with respect to the number of qubits first by considering a Quantum Random
Access Memory (QRAM) based quantum computing model and next by considering a
non-QRAM model quantum computation. In the case of the QRAM model, the size of
quantum circuits is linear with respect to the number of qubits and in the case
of the non-QRAM model, the size of the quantum circuits is exponential with
respect to the number of qubits but the results are still non-trivial.
