PIRSA:19110131

Fine-grained quantum supremacy and stabilizer rank

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

Morimae, Tomoyuki. Fine-grained quantum supremacy and stabilizer rank. Perimeter Institute, Nov. 27, 2019, https://pirsa.org/19110131 

          @misc{ pirsa_PIRSA:19110131,
            doi = {10.48660/19110131},
            url = {https://pirsa.org/19110131},
            author = {Morimae, Tomoyuki},
            keywords = {Quantum Information},
            language = {en},
            title = {Fine-grained quantum supremacy and stabilizer rank},
            publisher = {Perimeter Institute},
            year = {2019},
            month = {nov},
            note = {PIRSA:19110131 see, \url{https://pirsa.org}}
          }

Tomoyuki Morimae Kyoto University

DOI 10.48660/19110131
Collection
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.