Explicit Lower Bounds on Strong Quantum Simulation

Abstract

We consider the problem of classical strong (amplitude-wise) simulation of <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an <italic>unconditional</italic> (i.e. without relying on any complexity-theoretic assumptions) and <italic>explicit</italic> <inline-formula> <tex-math notation="LaTeX">$(n-2)(2^{n-3}-1)$ </tex-math></inline-formula> lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing <italic>any</italic> amplitude to precision <inline-formula> <tex-math notation="LaTeX">$2^{-n}/2$ </tex-math></inline-formula> must take at least <inline-formula> <tex-math notation="LaTeX">$2^{n - o(n)}$ </tex-math></inline-formula> time. We then compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art general SAT solving. Finally, we investigate Clifford+<inline-formula> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> quantum circuits with <inline-formula> <tex-math notation="LaTeX">$t~T$ </tex-math></inline-formula>-gates. Using the sparsification lemma, we identify a time complexity lower bound of <inline-formula> <tex-math notation="LaTeX">$2^{2.2451\times 10^{-8}t}$ </tex-math></inline-formula> below which a strong simulator would improve on state-of-the-art 3-SAT solving. This also yields a conditional exponential lower bound on the growth of the stabilizer rank of magic states.