Select All
PIRSA:19110131

Fine-grained quantum supremacy and stabilizer rank

APA

Morimae, T. (2019). Fine-grained quantum supremacy and stabilizer rank. Perimeter Institute for Theoretical Physics. https://pirsa.org/19110131

Tomoyuki Morimae Kyoto University

Talk numberPIRSA:19110131
Talk Type Conference
Subject

Abstract

It is known that several sub-universal quantum computing models 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. I also show the stabilizer rank conjecture under fine-grained complexity conjectures.