Threshold theorem

In quantum computing, the threshold theorem (or quantum fault-tolerance theorem) states that a quantum computer with a physical error rate below a certain threshold can, through application of quantum error correction schemes, suppress the logical error rate to arbitrarily low levels. This shows that quantum computers can be made fault-tolerant, as an analogue to von Neumann's threshold theorem for classical computation. This result was proven independently (for various error models) by the groups of Dorit Aharonov and Michael Ben-Or; Emanuel Knill, Raymond Laflamme, and Wojciech Zurek; and Alexei Kitaev. These results built on a paper of Peter Shor, which proved a weaker version of the threshold theorem.

In quantum computing, the threshold theorem (or quantum fault-tolerance theorem) states that a quantum computer with a physical error rate below a certain threshold can, through application of quantum error correction schemes, suppress the logical error rate to arbitrarily low levels. This shows that quantum computers can be made fault-tolerant, as an analogue to von Neumann's threshold theorem for classical computation. This result was proven independently (for various error models) by the groups of Dorit Aharonov and Michael Ben-Or; Emanuel Knill, Raymond Laflamme, and Wojciech Zurek; and Alexei Kitaev. These results built on a paper of Peter Shor, which proved a weaker version of the threshold theorem. O(\log^c(p(n)/\varepsilon)p(n)) gates (for some constant c) on hardware whose components fail with probability at most p, provided p is below some constant threshold, p , and given reasonable assumptions about the noise in the underlying hardware. Threshold theorems for classical computation have the same form as above, except for classical circuits instead of quantum. The proof strategy for quantum computation is similar to that of classical computation: for any particular error model (such as having each gate fail with independent probability p), use error correcting codes to build better gates out of existing gates. Though these "better gates" are larger, and so are more prone to errors within them, their error-correction properties mean that they have a lower chance of failing than the original gate (provided p is a small-enough constant). Then, one can use these better gates to recursively create even better gates, until one has gates with the desired failure probability, which can be used for the desired quantum circuit. According to quantum information theorist Scott Aaronson: "The entire content of the Threshold Theorem is that you're correcting errors faster than they're created. That's the whole point, and the whole non-trivial thing that the theorem shows. That's the problem it solves." ==External links== Gil Kalai. "Perpetual Motion of The 21st Century?". Scott Aaronson. "PHYS771 Lecture 14: Skepticism of Quantum Computing": «The entire content of the Threshold Theorem is that you're correcting errors faster than they're created. That's the whole point, and the whole non-trivial thing that the theorem shows. That's the problem it solves.»

Text derived from https://en.wikipedia.org/w/index.php?oldid=1360742213 under CC BY-SA 4.0; modifications have been made.