Topological subsystem codes proposed recently by Bombin are quantum error-correcting codes defined on a two-dimensional grid of qubits that permit reliable quantum information storage with a constant error threshold. These codes require only the measurement of two-qubit nearest-neighbor operators for error correction. In this paper, we demonstrate that topological subsystem codes (TSCs) can be viewed as generalizations of Kitaev's honeycomb model to 3-valent hypergraphs. This new connection provides a systematic way of constructing TSCs and analyzing their properties. We also derive a necessary and sufficient condition under which a syndrome measurement in a subsystem code can be reduced to measurements of the gauge group generators. Furthermore, we propose and implement some candidate decoding algorithms for one particular TSC assuming perfect error correction. Our Monte Carlo simulations indicate that this code, which we call the five-square code, has a threshold against depolarizing noise of at least 2%.

We study a 3D generalization of the toric code model introduced recently by Chamon. This is an exactly solvable spin model with six-qubit nearest-neighbor interactions on an FCC lattice whose ground space exhibits topological quantum order. The elementary excitations of this model which we call monopoles can be geometrically described as the corners of rectangular-shaped membranes. We prove that the creation of an isolated monopole separated from other monopoles by a distance R requires an operator acting on Ω(R²) qubits. Composite particles that consist of two monopoles (dipoles) and four monopoles (quadrupoles) can be described as end-points of strings. The peculiar feature of the model is that dipole-type strings are rigid, that is, such strings must be aligned with face-diagonals of the lattice. For periodic boundary conditions the ground space can encode 4g qubits where g is the greatest common divisor of the lattice dimensions. We describe a complete set of logical operators acting on the encoded qubits in terms of closed strings and closed membranes.

We ask whether there are fundamental limits on storing quantum information reliably in a bounded volume of space. To investigate this question, we study quantum error correcting codes specified by geometrically local commuting constraints on a 2D lattice of finite-dimensional quantum particles. For these 2D systems, we derive a tradeoff between the number of encoded qubits k, the distance of the code d, and the number of particles n. It is shown that kd2=O(n) where the coefficient in O(n) depends only on the locality of the constraints and dimension of the Hilbert spaces describing individual particles. The analogous tradeoff for the classical information storage is kd=O(n).

We initiate the study of Majorana fermion codes (MFCs). These codes can be viewed as extensions of Kitaev's one-dimensional (ID) model of unpaired Majorana fermions in quantum wires to higher spatial dimensions and interacting fermions. The purpose of MFCs is to protect quantum information against low-weight fermionic errors, that is, operators acting on sufficiently small subsets of fermionic modes. We examine to what extent MFCs can surpass qubit stabilizer codes in terms of their stability properties. A general construction of 2D MFCs is proposed that combines topological protection based on a macroscopic code distance with protection based on fermionic parity conservation. Finally, we use MFCs to show how to transform any qubit stabilizer code to a weakly self-dual CSS code.

We discuss several thermodynamic criteria that have been introduced to characterize the thermal stability of a self-correcting quantum memory. We first examine the use of symmetry-breaking fields in analyzing the properties of self-correcting quantum memories in the thermodynamic limit; we show that the thermal expectation values of all logical operators vanish for any stabilizer and any subsystem code in any spatial dimension. On the positive side, we generalize the results of Alicki et al to obtain a general upper bound on the relaxation rate of a quantum memory at nonzero temperature, assuming that the quantum memory interacts via a Markovian master equation with a thermal bath. This upper bound is applicable to quantum memories based on either stabilizer or subsystem codes.

We describe a classical approximation algorithm for evaluating the ground state energy of the classical Ising Hamiltonian with linear terms on an arbitrary planar graph. The running time of the algorithm grows linearly with the number of spins and exponentially with 1/ε, where ε is the worst-case relative error. This result contrasts the well known fact that exact computation of the ground state energy for the two-dimensional Ising spin glass model is NP-hard. We also present a classical approximation algorithm for the quantum Local Hamiltonian Problem or Quantum Ising Spin Glass problem on a planar graph with bounded degree which is known to be a QMA-complete problem. Using a different technique we find a classical approximation algorithm for the quantum Ising spin glass problem on the simplest planar graph with unbounded degree, the star graph.

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.

We study the complexity of the Local Hamiltonian Problem (denoted as LH-MIN) in the special case when a Hamiltonian obeys the condition that all off-diagonal matrix elements in the standard basis are real and non-positive. We will call such Hamiltonians, which are common in the natural world, stoquastic. An equivalent characterization of stoquastic Hamiltonians is that they have an entry-wise non-negative Gibbs density matrix for any temperature. We prove that LH-MIN for stoquastic Hamiltonians belongs to the complexity class AM - a probabilistic version of NP with two rounds of communication between the prover and the verifier. We also show that 2-local stoquastic LH-MIN is hard for the class MA. With the additional promise of having a polynomial spectral gap, we show that stoquastic LH-MIN belongs to the class PostBPP=BPPpath-a generalization of BPP in which a post-selective readout is allowed. This last result also shows that any problem solved by adiabatic quantum computation using stoquastic Hamiltonians is in PostBPP.

We show how to map a given n-qubit target Hamiltonian with bounded-strength k-body interactions onto a simulator Hamiltonian with two-body interactions, such that the ground-state energy of the target and the simulator Hamiltonians are the same up to an extensive error O(n) for arbitrary small. The strength of the interactions in the simulator Hamiltonian depends on and k but does not depend on n. We accomplish this reduction using a new way of deriving an effective low-energy Hamiltonian which relies on the Schrieffer-Wolff transformation of many-body physics.