Universal Quantum Computation with ideal Clifford gates and noisy ancillas

Model

• The model combines perfect Clifford operations and Pauli measurements with independently prepared mixed ancillas ρ, while allowing adaptive computation.The ancilla state is a model parameter, and preparing n ancillas yields ρ⊗n.Source: §I · pp. 1–2

Classical region

• For polarization vectors inside the stabilizer octahedron O, any adaptive computation is efficiently classically simulable.This reformulates the Gottesman-Knill theorem because such states are mixtures of the six Pauli eigenstates preparable using ideal operations.Source: §I · pp. 1–2

Magic-state distillation

• Magic-state distillation addresses states outside O by consuming several copies of ρ and producing increasingly pure T-type or H-type magic states.Magic states both enable UQC with Clifford operations and can be purified using adaptive ideal operations.Source: §I · p. 3

Universality conditions

• UQC simulation is possible whenever ρ has sufficiently large fidelity with a T-type or H-type magic state.Theorems 2 and 3 give separate sufficient conditions for the two magic-state families.Source: §I · p. 3

Thresholds

• A projection onto a T-direction exceeding approximately 0.655 enables distillation toward a magic state; otherwise, the process converges to the maximally mixed state.Source: §I · p. 3

Limits and implications

• The proposed thresholds are close to lower bounds that constrain possible improvements, while the ideal-Clifford assumption remains physically unrealized in realistic topological systems.The paper connects a possible threshold improvement to a transition at the octahedron boundary and notes ideal Clifford implementation as an open limitation.Source: §I · pp. 2–3

II. THE CLIFFORD GROUP, STABILIZERS, AND SYNDROME MEASUREMENTS

• The n-qubit Clifford group is generated by Hadamard, phase-shift, and controlled-not gates and normalizes the Pauli group.Source: §II · p. 4
• Stabilizers are Hermitian Pauli-group elements, and commuting stabilizers can be simultaneously mapped to single-qubit σz operators by a Clifford unitary.Source: §II · p. 4
• Clifford operations can perform joint nondestructive measurements of commuting stabilizers, producing a syndrome of eigenvalues and projecting the state accordingly.Source: §II · p. 4
• The most general transformation realizable by ideal operations is an adaptive syndrome measurement whose next stabilizer may depend on earlier outcomes.Source: §II · p. 4

III. UNIVERSAL QUANTUM COMPUTATION WITH MAGIC STATES

• A phase-state circuit measures σz⊗σz, applies a controlled-not, and leaves the data qubit with either Λ(e^iθ) or Λ(e^-iθ), with the sign known from the outcome.Source: §III · pp. 4–5
• Repeated applications produce a random walk over phase powers that eventually realizes the desired Λ(e^iθ), with polynomially or exponentially decreasing tail probability depending on θ.Source: §III · p. 5
• Preparing |H⟩ enables Λ(e^-iπ/4), while Clifford operations plus this gate generate a dense subgroup of U(2).Source: §III · p. 5
• For T-type states, measuring σz⊗σz on two copies yields the favorable outcome with probability 2/3, after which Clifford processing produces a usable distilled state.Source: §III · p. 5
• Clifford operations together with either ideal |H⟩ or |T⟩ magic states are sufficient for universal quantum computation.Source: §III · p. 5

IV. ERROR ANALYSIS

• The simulation uses a per-round budget of K magic states, and the probability of exhausting that budget scales as exp(−αK).Source: §IV · p. 5
• The required number of raw ancillas for one H-type state depends on the target output error, and the total simulation consumes KL ∼L log L distilled states.Source: §IV · p. 6
• The analysis combines reliable ideal-magic-state circuits with noisy-state distillation to establish the simulation theorems for Oideal ∪{|H⟩} and Oideal ∪{|T⟩}.Source: §IV · p. 6
• Magic states with output error ǫout ∼1/(L log L) suffice for circuits containing L non-Clifford gates, while each gate consumes K ∼log L states.Source: §IV · pp. 5–6
• Distillation can prepare magic states at error ǫout from raw ρ when FT(ρ) > FT or FH(ρ) > FH, using resources polynomial in log L.Source: §IV · p. 6

Distillation protocol

• The elementary subroutine processes five copies, measures four commuting stabilizers, discards nontrivial syndromes, and decodes successful outcomes to one qubit.The construction detects errors rather than correcting them, then discards states with detected errors.Source: §V · p. 6

Logical implementation

• The logical operator implemented on the five-qubit code acts as the single-qubit T operator, so the encoded eigenstates correspond to the desired T-type magic states.The logical Pauli operators obey the one-qubit Pauli algebra, and the decoded state is further transformed to target |T0⟩.Source: §V · pp. 7–8

Error-detection mechanism

• A trivial syndrome guarantees either no errors or at least two errors, because one-error components are projected out by the code subspace.This error-detection property is not directly tied to the code’s minimal distance.Source: §V · p. 8

Threshold behavior

• An initial error below ǫ0≈0.173 is purified toward zero, while above ǫ0 the output converges to the maximally mixed state; the threshold polarization is about 65.5%.For small ǫ, the output error obeys ǫout≈5ǫ2.Source: §V · p. 8

Yield and success probability

• The successful-syndrome probability decreases from 1/6 at zero error to 1/16 at error 1/2, and is approximately 1/6 in the low-error regime.This yields a constant output rate r=1/30 when five-copy groups are processed independently.Source: §V · pp. 8–9

Asymptotic scaling

• The scheme provides a constant yield r = 1/30 and produces output error ǫout(ǫ) ≈5ǫ2, with successive levels reaching ǫout ≈53ǫ4 and ǫout ≈57ǫ8.Source: §V · p. 9

• The 15-qubit CSS code enables measurement of a non-Pauli syndrome using only ideal operations by replacing restricted operators with equivalent Pauli operators after partial syndrome measurement.This unusual behavior is identified as the key property enabling H-type magic-state distillation.Source: §VI · pp. 10–11
• The code is built from subspaces L1 of linear Boolean functions and L2 of degree-two Boolean polynomials, whose weight and orthogonality properties establish the required CSS structure.L1 has dimension 4 and L2 has dimension 10, with L1 and L2 related to punctured Reed–Muller constructions.Source: §VI · p. 10
• The code CSS(σz, L2; A, L1) has the same syndrome subspaces as the stabilizer code CSS(σz, L2; σx, L1), allowing its syndrome measurement to be implemented with ideal operations.The procedure measures the σz syndrome, computes a correction w, applies A(w)†, measures the σx stabilizers, and applies A(w).Source: §VI · pp. 10–11
• The distillation subroutine consumes 15 copies of ρ, declares failure when the A-syndrome is nontrivial, and otherwise decodes the code subspace to one qubit using a Clifford transformation.The logical Pauli operators are represented by transversal operators, and the remaining fourteen qubits become unentangled after decoding.Source: §VI · pp. 11–12
• The successful subroutine has a derived success probability and produces a normalized one-qubit output state characterized by a derived error probability.The output is obtained by projecting onto the common code subspace and then applying the decoding transformation.Source: §VI · p. 12

Distillation analysis

• The H-type protocol’s output-error function is obtained from the weight enumerator WL1(x, y) = x15 + 15x7y8.The derivation uses the MacWilliams identity and the structure of the subspace L1.Source: §VI · p. 13
• The threshold error probability is found numerically by solving the fixed-point equation ǫout(ǫ) = ǫ.The resulting function ǫout(ǫ) is plotted in Fig. 3.Source: §VI · p. 13, Figure 3 · p. 13
• For small ǫ, the subroutine succeeds with probability close to 1 and has yield close to 1/15.In this regime, the output error probability is analyzed asymptotically.Source: §VI · p. 13
• Recursive application distills one copy of |A0⟩ from n input states, with the final error determined by the recursion depth k.Neglecting fluctuations in successful attempts, the resulting relation characterizes the distillation scheme’s efficiency.Source: §VI · p. 13

• A threshold polarization of ρ above which universal quantum computation simulation is possible is obtained using two magic-state distillation schemes.The schemes distill magic states from noisy ancillas while Clifford operations are realized exactly.Source: §VII · p. 13
• The region 1 < |ρx| + |ρy| + |ρz| ≤ 3/7 remains unresolved because the 5-qubit distillation scheme fails while Gottesman–Knill simulation is not established.A possible classical-to-universal transition is the octahedron boundary |ρx| + |ρy| + |ρz| = 1.Source: §VII · p. 13
• Constructing a T-type distillation scheme at the threshold fidelity could establish the proposed transition, but larger GF(4)-linear codes show increasing threshold fidelity in numerical simulations.Simulations for n = 11 and n = 17 suggest the 5-qubit code may be the best GF(4)-linear code for distillation.Source: §VII · pp. 13–14
• An experimental challenge is to build a system supporting reliable quantum-information storage and Clifford processing, although the scheme tolerates strong ancilla-preparation decoherence.Such a system is identified as a candidate for a practical quantum computer.Source: §VII · p. 14

• The appendix’s purpose is to prove Eq. (15) and begins by introducing the required notation.Source: Appendix A · p. 14
• The encoded basis states are defined as |T̂0⟩ = |T00000⟩ and |T̂1⟩ = |T11111⟩.Source: Appendix A · p. 14
• S+(5) contains the positive-sign tensor products of five-qubit Pauli operators, and |g| counts the qubits on which g acts.Its size is |S+(5)| = 45 = |S(5)|/2.Source: Appendix A · p. 14