Keisuke Fujii: Threshold theorem for quantum supremacy

Опубликовано 1 февраля 2017, 1:31

Demonstrating quantum supremacy, a complexity-guaranteed quantum advantage 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. This allows us to show that the output sampled from the noisy quantum circuits (without postselection) 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 3.20\% for quantum supremacy, which is much higher than the standard threshold 0.75% with the same circuit-level noise model.