{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T07:00:59Z","timestamp":1648882859142},"reference-count":29,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,9,24]],"date-time":"2020-09-24T00:00:00Z","timestamp":1600905600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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+<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>T<\/mml:mi><\/mml:math> circuits. Similar results should hold for other sub-universal models.<\/jats:p>","DOI":"10.22331\/q-2020-09-24-329","type":"journal-article","created":{"date-parts":[[2020,9,24]],"date-time":"2020-09-24T13:46:15Z","timestamp":1600955175000},"page":"329","source":"Crossref","is-referenced-by-count":2,"title":["Additive-error fine-grained quantum supremacy"],"prefix":"10.22331","volume":"4","author":[{"given":"Tomoyuki","family":"Morimae","sequence":"first","affiliation":[{"name":"Yukawa Institute for Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japan"},{"name":"JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama, 332-0012, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suguru","family":"Tamaki","sequence":"additional","affiliation":[{"name":"School of Social Information Science, University of Hyogo, 8-2-1, Gakuennishi-machi, Nishi-ku, Kobe, Hyogo 651-2197, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2020,9,24]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.26421\/QIC4.2"},{"key":"1","doi-asserted-by":"publisher","unstructured":"S. Aaronson and A. Arkhipov, The computational complexity of linear optics. Theory of Computing 9, 143 (2013). DOI:10.1145\/1993636.1993682.","DOI":"10.1145\/1993636.1993682"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1098\/rspa.2010.0301"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.117.080501"},{"key":"4","doi-asserted-by":"publisher","unstructured":"E. Knill and R. Laflamme, Power of one bit of quantum information. Phys. Rev. Lett. 81, 5672 (1998). DOI:10.1103\/PhysRevLett.81.5672.","DOI":"10.1103\/PhysRevLett.81.5672"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.112.130502"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.96.040302"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.120.200502"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.4230\/LIPIcs.ICALP.2016.13"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2018-11-15-106"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41567-018-0318-2"},{"key":"11","unstructured":"R. Movassagh, Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling. arXiv:1810.04681."},{"key":"12","unstructured":"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."},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2020-05-11-264"},{"key":"14","unstructured":"A. M. Dalzell, Bachelor thesis, MIT (2017). https:\/\/dspace.mit.edu\/handle\/1721.1\/111859."},{"key":"15","unstructured":"C. Huang, M. Newman, and M. Szegedy, Explicit lower bounds on strong quantum simulation. arXiv:1804.10368."},{"key":"16","unstructured":"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."},{"key":"17","doi-asserted-by":"publisher","unstructured":"T. Morimae and S. Tamaki, Fine-grained quantum computational supremacy. Quant. Inf. Comput. 19, 1089 (2019). DOI:10.26421\/QIC19.13-14.","DOI":"10.26421\/QIC19.13-14"},{"key":"18","unstructured":"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."},{"key":"19","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.4230\/LIPIcs.CCC.2016.2"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1145\/3188745.3188920"},{"key":"21","doi-asserted-by":"publisher","unstructured":"R. Williams, Counting solutions to polynomial systems via reductions. Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA 2018).","DOI":"10.4230\/OASIcs.SOSA.2018.6"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1137\/1.9781611974782.143"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.4230\/LIPIcs.TQC.2013.80"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1006\/jcss.2001.1774"},{"key":"25","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1006\/jcss.2000.1727"},{"key":"26","doi-asserted-by":"publisher","unstructured":"A. Lincoln and A. Yedidia, Faster random $k$-CNF satisfiability. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).","DOI":"10.4230\/LIPIcs.ICALP.2020.78"},{"key":"27","unstructured":"L. Trevisan, Lecture notes on computational complexity."},{"key":"28","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Computational Complexity: a conceptual perspective. Cambridge University Press (2008).","DOI":"10.1017\/CBO9780511804106"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-09-24-329\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,9,24]],"date-time":"2020-09-24T13:46:27Z","timestamp":1600955187000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-09-24-329\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,24]]},"references-count":29,"URL":"https:\/\/doi.org\/10.22331\/q-2020-09-24-329","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,24]]},"article-number":"329"}}