Built on

C. Huang, M. Newman, and M. Szegedy, Explicit lower bounds on strong simulation of quantum circuits in terms of T T -gate count. arXiv:1902.04764
Original
1902
Earlier work this paper cites.
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
Original
1902
Earlier work this paper cites.
R. Movassagh, Cayley path and quantum computational supremacy: A proof of average-case # P \#P -hardness of Random Circuit Sampling with quantified robustness. arXiv:1909.06210
Original
1909
Earlier work this paper cites.
E. Knill and R. Laflamme, Power of one bit of quantum information. Phys. Rev. Lett. 81
1998
Earlier work this paper cites.
R. Impagliazzo and R. Paturi, On the complexity of k k -SAT. J. Comput. Syst. Sci. 62
2000
Earlier work this paper cites.
R. Impagliazzo, R. Paturi, and F. Zane, Which problems have stronly exponential complexity? J. Comput. Syst. Sci. 63
2001
Earlier work this paper cites.
B. M. Terhal and D. P. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quant. Inf. Comput. 4
2004
Earlier work this paper cites.
O. Goldreich, Computational Complexity: a conceptual perspective. Cambridge University Press (2008)
Original
2008
Earlier work this paper cites.
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
2010
Earlier work this paper cites.

Similar

S. Aaronson and A. Arkhipov, The computational complexity of linear optics. Theory of Computing 9
2013
Cited alongside, same era.
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). 10.4230/LIPIcs.TQC.2013.80
Original
2013
Cited alongside, same era.
T. Morimae, K. Fujii, and J. F. Fitzsimons, Hardness of classically simulating the one clean qubit model. Phys. Rev. Lett. 112
2014
Cited alongside, same era.
M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117
2016
Cited alongside, same era.

Then

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
2018
Later among the works it cites.
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
2018
Later among the works it cites.
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). 10.1145/3188745.3188920
2018
Later among the works it cites.
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
2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2019

Additive-error fine-grained quantum supremacy

Morimae, Tomoyuki, Tamaki, Suguru

Understand

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.

Built on

C. Huang, M. Newman, and M. Szegedy, Explicit lower bounds on strong simulation of quantum circuits in terms of T T -gate count. arXiv:1902.04764
Original
1902
Earlier work this paper cites.
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
Original
1902
Earlier work this paper cites.
R. Movassagh, Cayley path and quantum computational supremacy: A proof of average-case # P \#P -hardness of Random Circuit Sampling with quantified robustness. arXiv:1909.06210
Original
1909
Earlier work this paper cites.
E. Knill and R. Laflamme, Power of one bit of quantum information. Phys. Rev. Lett. 81
1998
Earlier work this paper cites.
R. Impagliazzo and R. Paturi, On the complexity of k k -SAT. J. Comput. Syst. Sci. 62
2000
Earlier work this paper cites.
R. Impagliazzo, R. Paturi, and F. Zane, Which problems have stronly exponential complexity? J. Comput. Syst. Sci. 63
2001
Earlier work this paper cites.
B. M. Terhal and D. P. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quant. Inf. Comput. 4
2004
Earlier work this paper cites.
O. Goldreich, Computational Complexity: a conceptual perspective. Cambridge University Press (2008)
Original
2008
Earlier work this paper cites.
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
2010
Earlier work this paper cites.

Similar

S. Aaronson and A. Arkhipov, The computational complexity of linear optics. Theory of Computing 9
2013
Cited alongside, same era.
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). 10.4230/LIPIcs.TQC.2013.80
Original
2013
Cited alongside, same era.
T. Morimae, K. Fujii, and J. F. Fitzsimons, Hardness of classically simulating the one clean qubit model. Phys. Rev. Lett. 112
2014
Cited alongside, same era.
M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117
2016
Cited alongside, same era.

Then

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
2018
Later among the works it cites.
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
2018
Later among the works it cites.
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). 10.1145/3188745.3188920
2018
Later among the works it cites.
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
2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

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

2016

Cited alongside, same era.

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

2016

Cited alongside, same era.

T. Morimae, Hardness of classically sampling one clean qubit model with constant total variation distance error. Phys. Rev. A 96

2017

Cited alongside, same era.

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

2017

Cited alongside, same era.

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

2017

Cited alongside, same era.

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

Original

Cited in the paper.

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

Original

Cited in the paper.

L. Trevisan, Lecture notes on computational complexity

Cited in the paper.

A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sampling. Nature Phys. 15

2019

Closest in time.

T. Morimae and S. Tamaki, Fine-grained quantum computational supremacy. Quant. Inf. Comput. 19

2019

Closest in time.

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

2020

Closest in time.

A. Lincoln and A. Yedidia, Faster random k k -CNF satisfiability. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). DOI:10.4230/LIPIcs.ICALP.2020.78

2020

Closest in time.