Additive-error fine-grained quantum supremacy

Tomoyuki Morimae; Suguru Tamaki

doi:10.22331/q-2020-09-24-329

Additive-error fine-grained quantum supremacy

Tomoyuki Morimae^1,2 and Suguru Tamaki³

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

Published:	2020-09-24, volume 4, page 329
Eprint:	arXiv:1912.06336v3
Doi:	https://doi.org/10.22331/q-2020-09-24-329
Citation:	Quantum 4, 329 (2020).

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

@article{Morimae2020additiveerrorfine,
  doi = {10.22331/q-2020-09-24-329},
  url = {https://doi.org/10.22331/q-2020-09-24-329},
  title = {Additive-error fine-grained quantum supremacy},
  author = {Morimae, Tomoyuki and Tamaki, Suguru},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {329},
  month = sep,
  year = {2020}
}

► 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

[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 Anticoncentrate in Log Depth", PRX Quantum 3 1, 010333 (2022).

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

[5] Martin Kliesch and Ingo Roth, "Theory of quantum system certification: a tutorial", arXiv:2010.05925, (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2024-08-08 10:15:42) and SAO/NASA ADS (last updated successfully 2024-08-08 10:15:43). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.