The threshold theorem states that any abstract circuit in BQP can be computed by another polynomial-depth circuit that succeeds in the presence of noise. The original construction from 1996 requires paying a poly-log factor of depth. Is it possible to reduce this to a constant overhead factor? What are the known lower bounds regarding fault-tolerant computation?

  • 2
    $\begingroup$ It looks like it's probably possible: arxiv.org/abs/1310.2984 (this requires a family of codes with the right properties. There's been a lot of progress on these types of code recently, although I don't know if they quite match up with the requirements of the paper.) $\endgroup$
    – DaftWullie
    Commented May 18, 2023 at 14:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.