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.

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 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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
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.
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.
https:/​/​doi.org/​10.22331/​q-2020-05-11-264

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

[16] C. Huang, M. Newman, and M. Szegedy, Explicit lower bounds on strong quantum simulation. arXiv:1804.10368.
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.
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.
https:/​/​doi.org/​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.
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).
https:/​/​doi.org/​10.4230/​LIPIcs.CCC.2016.2

[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).
https:/​/​doi.org/​10.1145/​3188745.3188920

[22] R. Williams, Counting solutions to polynomial systems via reductions. Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA 2018).
https:/​/​doi.org/​10.4230/​OASIcs.SOSA.2018.6

[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.
https:/​/​doi.org/​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).
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2013.80
arXiv:1304.5164

[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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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).
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2020.78

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

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

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2020-10-23 05:24:10). On SAO/NASA ADS no data on citing works was found (last attempt 2020-10-23 05:24:10).