Additive-error fine-grained quantum supremacy

Tomoyuki Morimae1,2 and Suguru Tamaki3

1Yukawa Institute for Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japan
2JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama, 332-0012, Japan
3School of Social Information Science, University of Hyogo, 8-2-1, Gakuennishi-machi, Nishi-ku, Kobe, Hyogo 651-2197, Japan

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


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 a more realistic setup, namely, additive-error sampling. In this paper, we show the additive-error fine-grained quantum supremacy (under certain complexity assumptions). 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.

► BibTeX data

► References

[1] B. M. Terhal and D. P. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quant. Inf. Comput. 4, 134 (2004). DOI:10.26421/​QIC4.2.

[2] S. Aaronson and A. Arkhipov, The computational complexity of linear optics. Theory of Computing 9, 143 (2013). DOI:10.1145/​1993636.1993682.

[3] M. J. Bremner, R. Jozsa, and D. J. Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. A 467, 459 (2011). DOI:10.1098/​rspa.2010.0301.

[4] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016). DOI:10.1103/​PhysRevLett.117.080501.

[5] E. Knill and R. Laflamme, Power of one bit of quantum information. Phys. Rev. Lett. 81, 5672 (1998). DOI:10.1103/​PhysRevLett.81.5672.

[6] T. Morimae, K. Fujii, and J. F. Fitzsimons, Hardness of classically simulating the one clean qubit model. Phys. Rev. Lett. 112, 130502 (2014). DOI:10.1103/​PhysRevLett.112.130502.

[7] T. Morimae, Hardness of classically sampling one clean qubit model with constant total variation distance error. Phys. Rev. A 96, 040302(R) (2017). DOI:10.1103/​PhysRevA.96.040302.

[8] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Impossibility of classically simulating one-clean-qubit model with multiplicative error. Phys. Rev. Lett. 120, 200502 (2018). DOI:10.1103/​PhysRevLett.120.200502.

[9] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Power of quantum computation with few clean qubits. Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp.13:1-13:14 (2016). DOI:10.4230/​LIPIcs.ICALP.2016.13.

[10] T. Morimae, Y. Takeuchi, and H. Nishimura, Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy. Quantum 2, 106 (2018). 10.22331/​q-2018-11-15-106.

[11] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sampling. Nature Phys. 15, 159 (2019). DOI:10.1038/​s41567-018-0318-2.

[12] R. Movassagh, Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling. arXiv:1810.04681.

[13] R. Movassagh, Cayley path and quantum computational supremacy: A proof of average-case $\# P$-hardness of Random Circuit Sampling with quantified robustness. arXiv:1909.06210.

[14] A. M. Dalzell, A. W. Harrow, D. E. Koh, and R. L. La Placa, How many qubits are needed for quantum computational supremacy? Quantum 4, 264 (2020). DOI:10.22331/​q-2020-05-11-264.

[15] A. M. Dalzell, Bachelor thesis, MIT (2017). https:/​/​​handle/​1721.1/​111859.

[16] C. Huang, M. Newman, and M. Szegedy, Explicit lower bounds on strong quantum simulation. arXiv:1804.10368.

[17] C. Huang, M. Newman, and M. Szegedy, Explicit lower bounds on strong simulation of quantum circuits in terms of $T$-gate count. arXiv:1902.04764.

[18] T. Morimae and S. Tamaki, Fine-grained quantum computational supremacy. Quant. Inf. Comput. 19, 1089 (2019). DOI:10.26421/​QIC19.13-14.

[19] R. Hayakawa, T. Morimae, and S. Tamaki, Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths. arXiv:1902.08382.

[20] R. R. Williams, Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. Proceedings of the 31st Conference on Computational Complexity (CCC'16), pages 1-17 (2016).

[21] Dell and Lapinskas, Fine-grained reductions from approximate counting to decision. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pages 281-288 (2018).

[22] R. Williams, Counting solutions to polynomial systems via reductions. Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA 2018).

[23] D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, and H. Yu, Beating brute force for systems of polynomial equations over finite fields. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.2190-2202 (2017). DOI:10.1137/​1.9781611974782.143.

[24] A. Cosentino, R. Kothari, and A. Paetznick, Dequantizing read-once quantum formulas. arXiv:1304.5164; 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), Leibniz International Proceedings in Informatics (LIPIcs) 22, pp. 80-92 (2013).

[25] R. Impagliazzo, R. Paturi, and F. Zane, Which problems have stronly exponential complexity? J. Comput. Syst. Sci. 63(4), 512-530 (2001). DOI:10.1006/​jcss.2001.1774.

[26] R. Impagliazzo and R. Paturi, On the complexity of $k$-SAT. J. Comput. Syst. Sci. 62(2), 367-375 (2001). DOI:10.1006/​jcss.2000.1727.

[27] A. Lincoln and A. Yedidia, Faster random $k$-CNF satisfiability. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).

[28] L. Trevisan, Lecture notes on computational complexity.

[29] O. Goldreich, Computational Complexity: a conceptual perspective. Cambridge University Press (2008).

Cited by

[1] Martin Kliesch and Ingo Roth, "Theory of Quantum System Certification", PRX Quantum 2 1, 010201 (2021).

[2] Alexander M. Dalzell, Aram W. Harrow, Dax Enshan Koh, and Rolando L. La Placa, "How many qubits are needed for quantum computational supremacy?", Quantum 4, 264 (2020).

[3] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão, "Random quantum circuits anti-concentrate in log depth", arXiv:2011.12277.

The above citations are from Crossref's cited-by service (last updated successfully 2021-04-21 18:36:28) and SAO/NASA ADS (last updated successfully 2021-04-21 18:36:29). The list may be incomplete as not all publishers provide suitable and complete citation data.