# Additive-error fine-grained quantum supremacy

Article · Tomoyuki Morimae, Suguru Tamaki

- Archive id: arxiv:1912.06336
- Published: 2019-12-13
- Venue: Quantum 4, 329 (2020)
- DOI: https://doi.org/10.22331/q-2020-09-24-329
- arXiv: https://arxiv.org/abs/1912.06336
- Citations: 4
- Source URL: https://arxiv.org/abs/1912.06336
- PDF: https://arxiv.org/pdf/1912.06336
- Provenance: arxiv

## 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+$T$ circuits. Similar results should hold for other sub-universal models.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Algorithms & Quantum Advantage](https://space-kitty.com/topics/quantum-algorithms-advantage)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.