Fine-grained quantum supremacy

Monday, November 25, 2019 12:00 pm - 12:00 pm EST (GMT -05:00)

Tomoyuki Morimae, Kyoto University

It is known that several sub-universal quantum computing models, such as the IQP model, Boson sampling model, and the one-clean qubit model, cannot be classically simulated unless the polynomial-time hierarchy collapses. However, these results exclude only polynomial-time classical simulations. In this talk, based on fine-grained complexity conjectures, I show more ``fine-grained" quantum supremacy results that prohibit certain exponential-time classical simulations. (Morimae and Tamaki, arXiv:1901.01637)