Sergey Bravyi, IBM Research
Abstract
Magic state distillation is a method of implementing fault-tolerant non-Clifford gates such as the pi/8-rotation by purifying certain single-qubit ancillary states. An important figure of merit of a distillation protocol is the distillation cost - the number of raw ancillas needed to distill one magic state with a desired accuracy. To construct low-cost distillation protocols we develop a general theory of stabilizer codes with transversal non-Clifford gates. The key ingredient in this theory is 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 pi/8-rotation on all logical qubits, possibly augmented by Clifford gates. A powerful numerical method for generating triorthogonal matrices is proposed. Our techniques lead to a new family of distillation protocols with a very favorable scaling of the distillation cost. Finally, we present a general no-go theorem for transversal implementation of non-Clifford gates for 2D topological stabilizer codes. In the case of spatial dimension D>2 our theorem provides a partial classification of transversal encoded gates.