Explicit lower bounds on strong quantum simulation
arXiv:1804.10368
Abstract
We consider the problem of strong (amplitude-wise) simulation of -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 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 must take at least time. Finally, we compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art SAT solving.
arXiv comment15 pages, comments welcome, updated affiliations
References in corpus (7)
- Quantum Computing in the NISQ era and beyond
- Quantum computing and the entanglement frontier
- 64-Qubit Quantum Circuit Simulation
- Simulation of low-depth quantum circuits as complex undirected graphical models
- Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral
- Quantum circuits and low-degree polynomials over F_2
- Non-Identity Check Remains QMA-Complete for Short Circuits