Explicit Lower Bounds on Strong Quantum Simulation

• Published in: IEEE transactions on information theory 2020-09, Vol.66 (9), p.5585-5600
• Main Authors: Huang, Cupjin, Newman, Michael, Szegedy, Mario
• Format: Article
• Language: English
• Subjects: Amplitudes; circuit simulation; Circuits; Complexity; Complexity theory; computational complexity; Computational modeling; Computer simulation; Integrated circuit modeling; Logic gates; Lower bounds; Quantum computing; Quantum mechanics; Qubits (quantum computing); Simulation; Simulators; Solvers; Tensors
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2020.3004427

We consider the problem of classical strong (amplitude-wise) simulation of n -qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity-theoretic assumptions) and explicit (n-2)(2^{n-3}-1) 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 any amplitude to precision 2^{-n}/2 must take at least 2^{n - o(n)} 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+ T quantum circuits with t~T -gates. Using the sparsification lemma, we identify a time complexity lower bound of 2^{2.2451\times 10^{-8}t} 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.