Magic-state distillation with low overhead

Abstract

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 γ=log_2(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.