Magic-state distillation with low overhead

We propose a family of error-detecting stabilizer codes with an encoding rate of 1/3 that permit a transversal implementation of the gate T=exp(-iπZ/8) on all logical qubits. These codes are used to construct protocols for distilling high-quality "magic" states T+ by Clifford group gates and Pauli measurements. The distillation overhead scales as O(logγ(1/ε)), where ε is the output accuracy and γ=log2(3)∼1.6. To construct the desired family of codes, we introduce the notion of a triorthogonal matrix, a binary matrix in which any pair and any triple of rows have even overlap. Any triorthogonal matrix gives rise to a stabilizer code with a transversal T gate on all logical qubits, possibly augmented by Clifford gates. A powerful numerical method for generating triorthogonal matrices is proposed. Our techniques lead to a twofold overhead reduction for distilling magic states with accuracy ε∼10-12 compared with previously known protocols. © 2012 American Physical Society.