Additive-error fine-grained quantum supremacy
arXiv:1912.06336 · doi:10.22331/q-2020-09-24-329
Abstract
It is known that several sub-universal quantum computing models, such as the IQP model, the Boson sampling model, the one-clean qubit model, and the random circuit model, cannot be classically simulated in polynomial time under certain conjectures in classical complexity theory. Recently, these results have been improved to "fine-grained" versions where even exponential-time classical simulations are excluded assuming certain classical fine-grained complexity conjectures. All these fine-grained results are, however, about the hardness of strong simulations or multiplicative-error sampling. It was open whether any fine-grained quantum supremacy result can be shown for additive-error sampling. In this paper, we show the additive-error fine-grained quantum supremacy. As examples, we consider the IQP model, a mixture of the IQP model and log-depth Boolean circuits, and Clifford+ circuits. Similar results should hold for other sub-universal models.
arXiv comment12 pages, no figure. Published version. See also an independent result by Dalzell et al., arXiv:1805.05224
References in corpus (12)
- On the Power of One Bit of Quantum Information
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Average-case complexity versus approximate simulation of commuting quantum computations
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- On the hardness of classically simulating the one clean qubit model
- How many qubits are needed for quantum computational supremacy?
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- Hardness of classically sampling one clean qubit model with constant total variation distance error
- Power of Quantum Computation with Few Clean Qubits
- Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
- Fine-grained reductions from approximate counting to decision
- Dequantizing read-once quantum formulas