Quantum threshold theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In quantum computing, the (quantum) threshold theorem (or quantum fault-tolerance theorem), proved by Michael Ben-Or and Dorit Aharonov (along with other groups),[who?] 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. Current estimates put the threshold for the surface code on the order of 1%,[1] though estimates range widely and are difficult to calculate due to the exponential difficulty of simulating large quantum systems.[citation needed][a] At a 0.1% probability of a depolarizing error, the surface code would require approximately 1,000-10,000 physical qubits per logical data qubit,[2] though more pathological error types could change this figure drastically.[further explanation needed]

According to leading 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."[3]

See also[edit]

Notes[edit]

  1. ^ It is exponentially difficult for classical computers to simulate quantum systems; known as the quantum many body problem. However, it is known that quantum computers can perform this in polynomial time with bounded errors, much more efficiently than classical computers; one of the main appeals of quantum computing. This is applicable to chemical simulations, drug discovery, energy production, climate modeling and fertilizer production (e.g. FeMoco) as well. Because of this, quantum computers will be better than classical computers at aiding design of further quantum computers.

References[edit]

  1. ^ Fowler, Austin G.; Stephens, Ashley M.; Groszkowski, Peter (2009-11-11). "High-threshold universal quantum computation on the surface code". Physical Review A. 80 (5). arXiv:0803.0272. Bibcode:2009PhRvA..80e2312F. doi:10.1103/physreva.80.052312. ISSN 1050-2947.
  2. ^ Campbell, Earl T.; Terhal, Barbara M.; Vuillot, Christophe (2017-09-13). "Roads towards fault-tolerant universal quantum computation". Nature. 549 (7671): 172–179. Bibcode:2017Natur.549..172C. doi:10.1038/nature23460. ISSN 0028-0836.
  3. ^ Aaronson, Scott; Granade, Chris (Fall 2006). "Lecture 14: Skepticism of Quantum Computing". PHYS771: Quantum Computing Since Democritus. Shtetl Optimized. Retrieved 2018-12-27.

Further reading[edit]

Books[edit]

Papers[edit]

From The Journals of the American Physical Society:

From the ArXiV:

External links[edit]