quantum computing Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...

, the Gottesman–Knill theorem is a theoretical result by

Daniel Gottesman Daniel Gottesman is a physicist, known for his work regarding quantum error correction, in particular the invention of the stabilizer formalism for quantum error-correcting codes, and the Gottesman–Knill theorem. He is a faculty member at the ...

and Emanuel Knill that states that stabilizer circuits, circuits that only consist of gates from the

normalizer In mathematics, especially group theory, the centralizer (also called commutant) of a subset ''S'' in a group ''G'' is the set of elements \mathrm_G(S) of ''G'' such that each member g \in \mathrm_G(S) commutes with each element of ''S'', o ...

of the qubit

Pauli group In physics and mathematics, the Pauli group G_1 on 1 qubit is the 16-element matrix group consisting of the 2 × 2 identity matrix I and all of the Pauli matrices :X = \sigma_1 = \begin 0&1\\ 1&0 \end,\quad Y = \sigma_2 = \begin ...

, also called

Clifford group In mathematics, a Clifford algebra is an algebra generated by a vector space with a quadratic form, and is a unital associative algebra. As -algebras, they generalize the real numbers, complex numbers, quaternions and several other hypercomp ...

, 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. The reason for the speed up of quantum computers is not yet fully understood. The theorem proves that, for all quantum algorithms with a speed up that relies on entanglement which can be achieved with a

CNOT In computer science, the controlled NOT gate (also C-NOT or CNOT), controlled-''X'' gate'','' controlled-bit-flip gate, Feynman gate or controlled Pauli-X is a quantum logic gate that is an essential component in the construction of a gate-based ...

and a

Hadamard Jacques Salomon Hadamard (; 8 December 1865 – 17 October 1963) was a French mathematician who made major contributions in number theory, complex analysis, differential geometry and partial differential equations. Biography The son of a teac ...

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 with an implementation. The Gottesman–Knill theorem was published in a single author paper by Gottesman in which he credits Knill with the result through private communication.

Formal statement

Theorem: A quantum circuit using only the following elements can be simulated efficiently on a classical computer: # Preparation of

qubit In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...

s in computational basis states, #

Clifford gates 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 te ...

(

Hadamard gate The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...

controlled NOT gate In computer science, the controlled NOT gate (also C-NOT or CNOT), controlled-''X'' gate'','' controlled-bit-flip gate, Feynman gate or controlled Pauli-X is a quantum logic gate that is an essential component in the construction of a gate-based ...

s, 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 Entanglement distillation (also called ''entanglement purification'') is the transformation of ''N'' copies of an arbitrary entangled state \rho into some number of approximately pure Bell pairs, using only local operations and classical commun ...

and for

quantum error correction 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 ...

. From a practical point of view, stabilizer circuits have been simulated in time using the

graph state In quantum computing, a graph state is a special type of multi-qubit state that can be represented by a graph. Each qubit is represented by a vertex of the graph, and there is an edge between every interacting pair of qubits. In particular, they a ...

formalism.

References

* * {{DEFAULTSORT:Gottesman-Knill theorem Quantum information science

Formal statement

See also

References