PIRSA:19110131 Conference Quantum Information

DOI10.48660/19110131

Conference/School: Symmetry, Phases of Matter, and Resources in Quantum Computing

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}}
}

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.

Resources

Next talk

Related Talks