PIRSA:17010080

Quantum supremacy of fault-tolerant quantum computation in a pre-threshold region

APA

Fujii, K. (2017). Quantum supremacy of fault-tolerant quantum computation in a pre-threshold region. Perimeter Institute for Theoretical Physics. https://pirsa.org/17010080

MLA

Fujii, Keisuke. Quantum supremacy of fault-tolerant quantum computation in a pre-threshold region. Perimeter Institute for Theoretical Physics, Jan. 25, 2017, https://pirsa.org/17010080

BibTex

          @misc{ scivideos_PIRSA:17010080,
            doi = {10.48660/17010080},
            url = {https://pirsa.org/17010080},
            author = {Fujii, Keisuke},
            keywords = {Other Physics},
            language = {en},
            title = {Quantum supremacy of fault-tolerant quantum computation in a pre-threshold region},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2017},
            month = {jan},
            note = {PIRSA:17010080 see, \url{https://scivideos.org/pirsa/17010080}}
          }
          

Keisuke Fujii University of Tokyo

Talk numberPIRSA:17010080
Source RepositoryPIRSA
Talk Type Scientific Series
Subject

Abstract

Demonstrating quantum supremacy, a complexity-guaranteed quantum advantage against over the best classical algorithms by using less universal quantum devices, is an important near-term milestone for quantum information processing. Here we develop a threshold theorem for quantum supremacy with noisy quantum circuits in the pre-threshold region, where quantum error correction does not work directly. By using the postselection argument, we show that the output sampled from the noisy quantum circuits cannot be simulated efficiently by classical computers based on a stable complexity theoretical conjecture, i.e., non-collapse of the polynomial hierarchy. By applying this to fault-tolerant quantum computation with the surface codes, we obtain the threshold value 2.84% for quantum supremacy, which is much higher than the standard threshold 0.75% for universal fault-tolerant quantum computation with the same circuit-level noise model. Moreover, contrast to the standard noise threshold, the origin of quantum supremacy in noisy quantum circuits is quite clear; the threshold is determined purely by the threshold of magic state distillation, which is essential to gain a quantum advantage.