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)