We study the fundamental limits on the reliable storage of quantum information in lattices of qubits by deriving tradeoff bounds for approximate quantum error correcting codes. We introduce a notion of local approximate correctability and code distance, and give a number of equivalent formulations thereof, generalizing various exact error-correction criteria. Our tradeoff bounds relate the number of physical qubits n , the number of encoded qubits k , the code distance d , the accuracy parameter δ that quantifies how well the erasure channel can be reversed, and the locality parameter ℓ that specifies the length scale at which the recovery operation can be done. In a regime where the recovery is successful to accuracy δ that is exponentially small in ℓ , which is the case for perturbations of local commuting projector codes, our bound reads kd2D−1≤O(n(logn)2DD−1) for codes on D -dimensional lattices of Euclidean metric. We also find that the code distance of any local approximate code cannot exceed O(ℓn(D−1)/D) if δ≤O(ℓn−1/D) . As a corollary of our formulation of correctability in terms of logical operator avoidance, we show that the code distance d and the size d~ of a minimal region that can support all approximate logical operators satisfies d~d1D−1≤O(nℓDD−1) , where the logical operators are accurate up to O((nδ/d)1/2) in operator norm. Finally, we prove that for two-dimensional systems if logical operators can be approximated by operators supported on constant-width flexible strings, then the dimension of the code space must be bounded. This supports one of the assumptions of algebraic anyon theories, that there exist only finitely many anyon types.
We derive new tradeoffs for reliable quantum information storage in a 2D local architecture based on subsystem quantum codes. Our results apply to stabilizer subsystem codes, that is, stabilizer codes in which part of the logical qubits does not encode any information. A stabilizer subsystem code can be specified by its gauge group - a subgroup of the Pauli group that includes the stabilizers and the logical operators on the unused logical qubits. We assume that the physical qubits are arranged on a two-dimensional grid and the gauge group has spatially local generators such that each generator acts only on a few qubits located close to each other. Our main result is an upper bound kd = O(n), where k is the number of encoded qubits, d is the minimal distance, and n is the number of physical qubits. In the special case when both gauge group and the stabilizer group have spatially local generators, we derive a stronger bound kd2= O(n) which is tight up to a constant factor.
The following open problems, which concern a fundamental limit on coding properties of quantum codes with realistic physical constraints, are analyzed and partially answered here: (a) the upper bound on code distances of quantum error-correcting codes with geometrically local generators, (b) the feasibility of a self-correcting quantum memory. To investigate these problems, we study stabilizer codes supported by local interaction terms with translation and scale symmetries on a
D-dimensional lattice. Our analysis uses the notion of topology emerging in geometric shapes of logical operators, which sheds a surprising new light on theory of quantum codes with physical constraints.
We study properties of stabilizer codes that permit a local description on a regular D -dimensional lattice. Specifically, we assume that the stabilizer group of a code (the gauge group for subsystem codes) can be generated by local Pauli operators such that the support of any generator is bounded by a hypercube of size O (1). Our first result concerns the optimal scaling of the distance d with the linear size of the lattice L . We prove an upper bound d = O ( L D -1 ) which is tight for D =1, 2. This bound applies to both subspace and subsystem stabilizer codes. Secondly, we analyze the suitability of stabilizer codes for building a self-correcting quantum memory. Any stabilizer code with geometrically local generators can be naturally transformed to a local Hamiltonian penalizing states that violate the stabilizer condition. A degenerate ground state of this Hamiltonian corresponds to the logical subspace of the code. We prove that for D =1, 2, different logical states can be mapped into each other by a sequence of single-qubit Pauli errors such that the energy of all intermediate states is upper bounded by a constant independent of the lattice size L . The same result holds if there are unused logical qubits that are treated as 'gauge qubits'. It demonstrates that a self-correcting quantum memory cannot be built using stabilizer codes in dimensions D =1, 2. This result is in sharp contrast with the existence of a classical self-correcting memory in the form of a two-dimensional (2D) ferromagnet. Our results leave open the possibility for a self-correcting quantum memory based on 2D subsystem codes or on 3D subspace or subsystem 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\ensuremath{-}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.
It is commonly believed that logical states of quantum error-correcting codes have to be highly entangled such that codes capable of correcting more errors require more entanglement to encode a qubit. Here, we show that the validity of this belief depends on the specific code and the choice of entanglement measure. To this end, we characterize a tradeoff between the code distance d quantifying the number of correctable errors, and the geometric entanglement measure of logical states quantifying their maximal overlap with product states or more general "topologically trivial" states. The maximum overlap is shown to be exponentially small in d for three families of codes: (1) low-density parity check codes with commuting check operators, (2) stabilizer codes, and (3) codes with a constant encoding rate. Equivalently, the geometric entanglement of any logical state of these codes grows at least linearly with d. On the opposite side, we also show that this distance-entanglement tradeoff does not hold in general. For any constant d and k (number of logical qubits), we show there exists a family of codes such that the geometric entanglement of some logical states approaches zero in the limit of large code length.