magic state

In plain terms

The Gottesman-Knill theorem says circuits built from the Clifford gates can be simulated classically, so you can ask where quantum advantage hides. It hides in one extra gate, the T gate, which twists the phase of one branch of a qubit's superposition by an eighth of a turn, so if you add T to the Clifford set you can approximate any quantum computation, and if you leave it out a laptop keeps up.

What makes T genuinely different can be proved. Push a Pauli operation, a bit flip, a phase flip or both, through any Clifford gate and out comes another Pauli operation, and that closure is the whole mechanism of classical simulability. Push a Pauli operation through T and what comes out isn't a Pauli operation, and can't be made one.

The magic state is T's resource form, the specific single-qubit state T produces from a plain equal superposition. Feed copies of it into circuits made only of Clifford gates and the effect of the T gate is obtained without ever applying it, which is why fault-tolerant architectures spend most of their budget manufacturing, or distilling, high-quality magic states.

In CSD

The magic layer is the precise complement of the corpus's Gottesman-Knill layer, and three theorems draw the boundary. Applying T twice gives the Clifford phase gate, so the hierarchy of gates descends as it should. Pushing the bit-flip Pauli operation through T gives an explicit combination of two Pauli operations, out of the Pauli family but inside its two-term span, the level-three hierarchy identity as a closed operator equation. And the no-go says no multiple of any Pauli operation equals that result, proved by comparing two columns of the matrices until the arithmetic demands an impossibility.

The magic state itself is exhibited with explicit coordinates and unit length.

The three things this module leaves out are proved elsewhere in the corpus. The injection circuit that spends a magic state to perform the T gate is a gate-teleportation identity, and a noisy resource gives the expected mixture of the intended gate with its phase-flipped version. The fifteen-to-one distillation protocol of Bravyi and Kitaev is proved end to end, with its cubic error bound and the convergence of the recursion below one twentieth. And Clifford plus T is proved universal, dense in the unitary group modulo one global phase. The standing disclaimer applies, as the algorithm layer consumes the programme's unitary-evolution pillar and doesn't support the foundations.

Mathematically

With tPhase = e^(i pi/4), tPhase squared is i, so T^2 = S on the register. The conjugation identity T X T-dagger = (X + i XZ)/sqrt 2 holds coordinatewise via e^(+-i pi/4) = (1 +- i)/sqrt 2. The no-go (tGate_conj_X_not_pauli) says that if T X T-dagger = c X^a Z^b then reading the |0> and |1> columns forces c = e^(i pi/4) and e^(-i pi/4) = c times a sign, hence e^(-i pi/2) in {+1, -1}, but e^(-i pi/2) = -i. The magic state T H |0> has coordinates (1, e^(i pi/4))/sqrt 2.

The name

The term "magic state" belongs to Sergey Bravyi and Alexei Kitaev, from their 2005 paper showing that noisy copies of certain single-qubit states can be distilled by ideal Clifford operations into fuel for universal computation, the fifteen-to-one protocol that still anchors fault-tolerant cost estimates. The gate-injection idea goes back to Gottesman and Chuang's 1999 teleportation construction, which organised gates into the Clifford hierarchy, with Paulis at level one, Clifford gates at level two, and T at level three.

The economics of quantum computing largely reduce to magic-state throughput, which is why "magic", Bravyi and Kitaev's deliberately playful word, became sober technical vocabulary.

Related entries

• Gottesman-Knill theoremThe Gottesman-Knill theorem marks the boundary of quantum advantage, as circuits built from the Clifford gates can be simulated classically, because in the right picture they're nothing more than linear algebra on bits.
• Steane codeSeven qubits protect one, as the Steane code was the first to correct any single- qubit error by using the same classical Hamming code twice, once for bit flips and once for phase flips.
• Shor codeShor's nine-qubit code was the first proof that quantum information can be protected against any error on any single qubit without ever being read, and the corpus verifies that protection as explicit constructed operations, including the subtle case where two different errors share one repair.
• Pauli matricesThree small matrices carry the entire two-level world, and their refusal to commute is the uncertainty principle in its smallest packaging.
• amplitude amplificationAmplitude amplification is the theorem of which Grover's algorithm is a shadow, as any quantum procedure with any success probability can have that probability raised by pure interference, quadratically faster than retrying.
• magic-state distillationDistillation turns many noisy magic states into one clean one, by encoding them in a code whose checks reject the likely errors, and the error rate falls as the cube of itself at every round.
• Clifford plus TClifford plus T is the standard universal gate set, as the Clifford gates alone are classically simulable and adding the single eighth-turn phase gate makes every unitary reachable to any accuracy you ask for.
• transversal gateA transversal gate computes on encoded information by acting on each physical qubit separately, so a fault in one qubit stays in one qubit and the code keeps its protection while the computation runs.