Fault-tolerant logical gates in quantum error-correcting codes

Recently, S. Bravyi and R. K\"onig Phys. Rev. Lett. 110, 170503 (2013) have shown that there is a trade-off between fault-tolerantly implementable logical gates and geometric locality of stabilizer codes. They consider locality-preserving operations which are implemented by a constant-depth geometrically local circuit and are thus fault tolerant by construction. In particular, they show that, for local stabilizer codes in D spatial dimensions, locality-preserving gates are restricted to a set of unitary gates known as the Dth level of the Clifford hierarchy. In this paper, we explore this idea further by providing several extensions and applications of their characterization to qubit stabilizer and subsystem codes. First, we present a no-go theorem for self-correcting quantum memory. Namely, we prove that a three-dimensional stabilizer Hamiltonian with a locality-preserving implementation of a non-Clifford gate cannot have a macroscopic energy barrier. This result implies that non-Clifford gates do not admit such implementations in Haah's cubic code and Michnicki's welded code. Second, we prove that the code distance of a D-dimensional local stabilizer code with a nontrivial locality-preserving mth-level Clifford logical gate is upper bounded by O (L^D+1-m). For codes with non-Clifford gates (m>2), this improves the previous best bound by S. Bravyi and B. Terhal New. J. Phys. 11, 043029 (2009). Topological color codes, introduced by H. Bombin and M. A. Martin-Delgado Phys. Rev. Lett. 97, 180501 (2006) ; Phys. Rev. Lett. 98, 160502 (2007) ; Phys. Rev. B 75, 075103 (2007), saturate the bound for m=D. Third, we prove that the qubit erasure threshold for codes with a nontrivial transversal mth-level Clifford logical gate is upper bounded by 1/m. This implies that no family of fault-tolerant codes with transversal gates in increasing level of the Clifford hierarchy may exist. This result applies to arbitrary stabilizer and subsystem codes and is not restricted to geometrically local codes. Fourth, we extend the result of Bravyi and K\"onig to subsystem codes. Unlike stabilizer codes, the so-called union lemma does not apply to subsystem codes. This problem is avoided by assuming the presence of an error threshold in a subsystem code, and a conclusion analogous to that of Bravyi and K\"onig is recovered.