Threshold theorem

Last updated

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. [1] This result was proven (for various error models) by the groups of Dorit Aharanov and Michael Ben-Or; [2] Emanuel Knill, Raymond Laflamme, and Wojciech Zurek; [3] and Alexei Kitaev [4] independently. [3] These results built off a paper of Peter Shor, [5] which proved a weaker version of the threshold theorem.

Contents

Explanation

The key question that the threshold theorem resolves is whether quantum computers in practice could perform long computations without succumbing to noise. Since a quantum computer will not be able to perform gate operations perfectly, some small constant error is inevitable; hypothetically, this could mean that quantum computers with imperfect gates can only apply a constant number of gates before the computation is destroyed by noise.

Surprisingly, the quantum threshold theorem shows that if the error to perform each gate is a small enough constant, one can perform arbitrarily long quantum computations to arbitrarily good precision, with only some small added overhead in the number of gates. The formal statement of the threshold theorem depends on the types of error correction codes and error model being considered. Quantum Computation and Quantum Information , by Michael Nielsen and Isaac Chuang, gives the general framework for such a theorem:

Threshold theorem for quantum computation [6] : 481 : A quantum circuit on n qubits and containing p(n) gates may be simulated with probability of error at most ε using

gates (for some constant c) on hardware whose components fail with probability at most p, provided p is below some constant threshold, , 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." [7]

Threshold value in practice

Current estimates put the threshold for the surface code on the order of 1%, [8] though estimates range widely and are difficult to calculate due to the exponential difficulty of simulating large quantum systems.[ citation needed ] [lower-alpha 1] 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, [9] though more pathological error types could change this figure drastically.[ further explanation needed ]

See also

Notes

  1. ↑ It is widely believed that it is exponentially difficult for classical computers to simulate quantum systems. This problem is known as the quantum many body problem. However, quantum computers can simulate many (though not all) Hamiltonians in polynomial time with bounded errors, which is 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 may be better than classical computers at aiding design of further quantum computers.

Related Research Articles

<span class="mw-page-title-main">Quantum computing</span> Technology that uses quantum mechanics

A quantum computer is a computer that exploits quantum mechanical phenomena.

This is a timeline of quantum computing.

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

<span class="mw-page-title-main">Quantum circuit</span> Model of quantum computing

In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits to known values, and possibly other actions. The minimum set of actions that a circuit needs to be able to perform on the qubits to enable quantum computation is known as DiVincenzo's criteria.

Quantum error correction (QEC) is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is theorised as essential to achieve fault tolerant quantum computing that can reduce the effects of noise on stored quantum information, faulty quantum gates, faulty quantum preparation, and faulty measurements. This would allow algorithms of greater circuit depth.

A topological quantum computer is a theoretical quantum computer proposed by Russian-American physicist Alexei Kitaev in 1997. It employs quasiparticles in two-dimensional systems, called anyons, whose world lines pass around one another to form braids in a three-dimensional spacetime. These braids form the logic gates that make up the computer. The advantage of a quantum computer based on quantum braids over using trapped quantum particles is that the former is much more stable. Small, cumulative perturbations can cause quantum states to decohere and introduce errors in the computation, but such small perturbations do not change the braids' topological properties. This is like the effort required to cut a string and reattach the ends to form a different braid, as opposed to a ball bumping into a wall.

In quantum computing, the Gottesman–Knill theorem is a theoretical result by Daniel Gottesman and Emanuel Knill that states that stabilizer circuits, circuits that only consist of gates from the normalizer of the qubit Pauli group, also called Clifford group, can be perfectly simulated in polynomial time on a probabilistic classical computer. The Clifford group can be generated solely by using CNOT, Hadamard, and phase gate S; and therefore stabilizer circuits can be constructed using only these gates.

<span class="mw-page-title-main">One-way quantum computer</span> Method of quantum computing

The one-way or measurement-based quantum computer (MBQC) is a method of quantum computing that first prepares an entangled resource state, usually a cluster state or graph state, then performs single qubit measurements on it. It is "one-way" because the resource state is destroyed by the measurements.

The toric code is a topological quantum error correcting code, and an example of a stabilizer code, defined on a two-dimensional spin lattice. It is the simplest and most well studied of the quantum double models. It is also the simplest example of topological order—Z2 topological order (first studied in the context of Z2 spin liquid in 1991). The toric code can also be considered to be a Z2 lattice gauge theory in a particular limit. It was introduced by Alexei Kitaev.

<span class="mw-page-title-main">Ancilla bit</span> Extra bits required in reversible and quantum computation, as bits cannot be modified arbitrarily

In reversible computing, ancilla bits are extra bits being used to implement irreversible logical operations. In classical computation, any memory bit can be turned on or off at will, requiring no prior knowledge or extra complexity. However, this is not the case in quantum computing or classical reversible computing. In these models of computing, all operations on computer memory must be reversible, and toggling a bit on or off would lose the information about the initial value of that bit. For this reason, in a quantum algorithm there is no way to deterministically put bits in a specific prescribed state unless one is given access to bits whose original state is known in advance. Such bits, whose values are known a priori, are known as ancilla bits in a quantum or reversible computing task.

Linear optical quantum computing or linear optics quantum computation (LOQC) is a paradigm of quantum computation, allowing universal quantum computation. LOQC uses photons as information carriers, mainly uses linear optical elements, or optical instruments to process quantum information, and uses photon detectors and quantum memories to detect and store quantum information.

The DiVincenzo criteria are conditions necessary for constructing a quantum computer, conditions proposed in 2000 by the theoretical physicist David P. DiVincenzo, as being those necessary to construct such a computer—a computer first proposed by mathematician Yuri Manin, in 1980, and physicist Richard Feynman, in 1982—as a means to efficiently simulate quantum systems, such as in solving the quantum many-body problem.

In quantum computing, quantum supremacy or quantum advantage is the goal of demonstrating that a programmable quantum computer can solve a problem that no classical computer can solve in any feasible amount of time, irrespective of the usefulness of the problem. The term was coined by John Preskill in 2012, but the concept dates back to Yuri Manin's 1980 and Richard Feynman's 1981 proposals of quantum computing.

Continuous-variable (CV) quantum information is the area of quantum information science that makes use of physical observables, like the strength of an electromagnetic field, whose numerical values belong to continuous intervals. One primary application is quantum computing. In a sense, continuous-variable quantum computation is "analog", while quantum computation using qubits is "digital." In more technical terms, the former makes use of Hilbert spaces that are infinite-dimensional, while the Hilbert spaces for systems comprising collections of qubits are finite-dimensional. One motivation for studying continuous-variable quantum computation is to understand what resources are necessary to make quantum computers more powerful than classical ones.

In quantum information and computation, the Solovay–Kitaev theorem says, roughly, that if a set of single-qubit quantum gates generates a dense subset of SU(2), then that set can be used to approximate any desired quantum gate with a relatively short sequence of gates. This theorem is considered one of the most significant results in the field of quantum computation and was first announced by Robert M. Solovay in 1995 and independently proven by Alexei Kitaev in 1997. Michael Nielsen and Christopher M. Dawson have noted its importance in the field.

In quantum computing, a qubit is a unit of information analogous to a bit in classical computing, but it is affected by quantum mechanical properties such as superposition and entanglement which allow qubits to be in some ways more powerful than classical bits for some tasks. Qubits are used in quantum circuits and quantum algorithms composed of quantum logic gates to solve computational problems, where they are used for input/output and intermediate computations.

Magic state distillation is a method for creating more accurate quantum states from multiple noisy ones, which is important for building fault tolerant quantum computers. It has also been linked to quantum contextuality, a concept thought to contribute to quantum computers' power.

In quantum computing and quantum information theory, the Clifford gates are the elements of the Clifford group, a set of mathematical transformations which normalize the n-qubit Pauli group, i.e., map tensor products of Pauli matrices to tensor products of Pauli matrices through conjugation. The notion was introduced by Daniel Gottesman and is named after the mathematician William Kingdon Clifford. Quantum circuits that consist of only Clifford gates can be efficiently simulated with a classical computer due to the Gottesman–Knill theorem.

The Eastin–Knill theorem is a no-go theorem that states: "No quantum error correcting code can have a continuous symmetry which acts transversely on physical qubits". In other words, no quantum error correcting code can transversely implement a universal gate set. Since quantum computers are inherently noisy, quantum error correcting codes are used to correct errors that affect information due to decoherence. Decoding error corrected data in order to perform gates on the qubits makes it prone to errors. Fault tolerant quantum computation avoids this by performing gates on encoded data. Transversal gates, which perform a gate between two "logical" qubits each of which is encoded in N "physical qubits" by pairing up the physical qubits of each encoded qubit, and performing independent gates on each pair, can be used to perform fault tolerant but not universal quantum computation because they guarantee that errors don't spread uncontrollably through the computation. This is because transversal gates ensure that each qubit in a code block is acted on by at most a single physical gate and each code block is corrected independently when an error occurs. Due to the Eastin–Knill theorem, a universal set like {H, S, CNOT, T} gates can't be implemented transversally. For example, the T gate can't be implemented transversely in the Steane code. This calls for ways of circumventing Eastin–Knill in order to perform fault tolerant quantum computation. In addition to investigating fault tolerant quantum computation, the Eastin–Knill theorem is also useful for studying quantum gravity via the AdS/CFT correspondence and in condensed matter physics via quantum reference frame or many-body theory.

This glossary of quantum computing is a list of definitions of terms and concepts used in quantum computing, its sub-disciplines, and related fields.

References

  1. ↑ Neumann, J. von (1956-12-31), "Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components", Automata Studies. (AM-34), Princeton: Princeton University Press, pp. 43–98, doi:10.1515/9781400882618-003, ISBN   978-1-4008-8261-8 , retrieved 2020-10-10
  2. ↑ Aharonov, Dorit; Ben-Or, Michael (2008-01-01). "Fault-Tolerant Quantum Computation with Constant Error Rate". SIAM Journal on Computing. 38 (4): 1207–1282. arXiv: quant-ph/9906129 . doi:10.1137/S0097539799359385. ISSN   0097-5397. S2CID   8969800.
  3. 1 2 Knill, E. (1998-01-16). "Resilient Quantum Computation". Science. 279 (5349): 342–345. arXiv: quant-ph/9702058 . Bibcode:1998Sci...279..342K. doi:10.1126/science.279.5349.342.
  4. ↑ Kitaev, A. Yu. (2003-01-01). "Fault-tolerant quantum computation by anyons". Annals of Physics. 303 (1): 2–30. arXiv: quant-ph/9707021 . Bibcode:2003AnPhy.303....2K. doi:10.1016/S0003-4916(02)00018-0. ISSN   0003-4916. S2CID   119087885.
  5. ↑ Shor, P.W. (1996). "Fault-tolerant quantum computation". Proceedings of 37th Conference on Foundations of Computer Science. Burlington, VT, USA: IEEE Comput. Soc. Press. pp. 56–65. doi:10.1109/SFCS.1996.548464. ISBN   978-0-8186-7594-2. S2CID   7508572.
  6. ↑ Nielsen, Michael A.; Chuang, Isaac L. (June 2012). Quantum Computation and Quantum Information (10th anniversary ed.). Cambridge: Cambridge University Press. ISBN   9780511992773. OCLC   700706156.
  7. ↑ Aaronson, Scott; Granade, Chris (Fall 2006). "Lecture 14: Skepticism of Quantum Computing". PHYS771: Quantum Computing Since Democritus . Shtetl Optimized. Retrieved 2018-12-27.
  8. ↑ 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): 052312. arXiv: 0803.0272 . Bibcode:2009PhRvA..80e2312F. doi:10.1103/physreva.80.052312. ISSN   1050-2947. S2CID   119228385.
  9. ↑ Campbell, Earl T.; Terhal, Barbara M.; Vuillot, Christophe (2017-09-13). "Roads towards fault-tolerant universal quantum computation". Nature. 549 (7671): 172–179. arXiv: 1612.07330 . Bibcode:2017Natur.549..172C. doi:10.1038/nature23460. ISSN   0028-0836. PMID   28905902. S2CID   4446310.


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.