# Gottesman–Knill theorem

Gottesman–Knill theorem 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;[1] and therefore stabilizer circuits can be constructed using only these gates.

The reason for the speed up of quantum computers is not yet fully understood[citation needed]. The theorem proves that, for all quantum algorithms with a speed up that relies on entanglement which can be achieved with a CNOT and a Hadamard gate to produce entangled states, this kind of entanglement alone does not give any computing advantage.

There exists a more efficient simulation of stabilizer circuits than the construction of the original publication[1] with an implementation.[2] The Gottesman–Knill theorem was published in a single author paper by Gottesman in which he credits Knill with the result through private communication.[3] Formal statement Theorem: A quantum circuit using only the following elements can be simulated efficiently on a classical computer: Preparation of qubits in computational basis states, Clifford gates (Hadamard gates, controlled NOT gates, phase gate S ), and Measurements in the computational basis.

The Gottesman–Knill theorem shows that even some highly entangled states can be simulated efficiently. Several important types of quantum algorithms use only Clifford gates, most importantly the standard algorithms for entanglement distillation and for quantum error correction. From a practical point of view, stabilizer circuits have been simulated in O(n log n) time using the graph state formalism.

See also Magic state distillation References ^ Jump up to: a b Aaronson, Scott; Gottesman, Daniel (2004). "Improved simulation of stabilizer circuits". Phys. Rev. A. 70 (5): 052328. arXiv:quant-ph/0406196. Bibcode:2004PhRvA..70e2328A. doi:10.1103/physreva.70.052328. S2CID 5289248. ^ Aaronson, Scott; Gottesman, Daniel. "CHP: CNOT-Hadamard-Phase". scottaaronson. Retrieved 19 September 2017. ^ Gottesman, Daniel (1998). "The Heisenberg Representation of Quantum Computers". arXiv:quant-ph/9807006v1. Bibcode:1998quant.ph..7006G. S. Anders and H. J. Briegel (2006). "Fast simulation of stabilizer circuits using a graph-state representation". Phys. Rev. A. 73 (2): 022334. arXiv:quant-ph/0504117v2. Bibcode:2006PhRvA..73b2334A. doi:10.1103/PhysRevA.73.022334. S2CID 12763101. Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3. OCLC 844974180. show vte Quantum information science Categories: Quantum information science

Si quieres conocer otros artículos parecidos a Gottesman–Knill theorem puedes visitar la categoría Quantum information science.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información