Explicit Lower Bounds on Strong Quantum Simulation

DOI10.1109/TIT.2020.3004427zbMATH Open1448.68243arXiv1804.10368OpenAlexW3037871222MaRDI QIDQ5124525FDOQ5124525

Author name not available (Why is that?)

Publication date: 29 September 2020

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We consider the problem of 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. 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.

Full work available at URL: https://arxiv.org/abs/1804.10368

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12)

Cited In (3)

• Gauging tensor networks with belief propagation
• Trading locality for time: certifiable randomness from low-depth circuits
• Post-quantum simulatable extraction with minimal assumptions: black-box and constant-round

This page was built for publication: Explicit Lower Bounds on Strong Quantum Simulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124525)