Fine-grained quantum supremacy and stabilizer rank



Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other compatible player.


Recording Details

Speaker(s): 
Scientific Areas: 
PIRSA Number: 
19110131

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.