In this paper, we present a detailed mathematical description of the error correction process for Kitaev's model for finite Abelian groups. The number of errors Kitaev's model can correct depends on the lattice and its topology. Although there is a theoretical maximum number of errors that can be corrected, we prove that correcting this number of errors, in general, is an NP-complete problem. Consequently, we introduce a polynomial-time correction algorithm that corrects a number of errors below the theoretical maximum.
In this paper, we present a detailed mathematical description of the error correction process for Kitaev's model for finite Abelian groups. The number of errors Kitaev's model can correct depends on the lattice and its topology. Although there is a theoretical maximum number of errors that can be corrected, we prove that correcting this number of errors, in general, is an NP-complete problem. Consequently, we introduce a polynomial-time correction algorithm that corrects a number of errors below the theoretical maximum.
This thesis presents a detailed analysis of the quantum double model and its twisted version, focusing on their properties as quantum error-correcting codes. In the case of Kitaev's quantum double model for finite Abelian groups, the error correction process is explicitly described. The number of correctable errors depends on the lattice and the topology of the underlying surface. Although there exists a theoretical maximum number of errors that can be corrected, it is proven that correcting this number of errors is, in general, an NP-complete problem. As an alternative, a polynomial-time correction algorithm is proposed that corrects a number of errors below the theoretical maximum. In regard to the twisted quantum double model, it is studied within the framework of Local Topological Order (LTO). Originally formulated for square lattices, the definition of LTO is extended here to arbitrary two-dimensional lattices, enabling an explicit characterization of the ground states space through invariant spaces of monomial representations. By reformulating the LTO conditions to include such general lattices, it is proven that the twisted model satisfies all four axioms of LTO on any 2D lattice. As a result, the ground states space of the model is shown to define a quantum error-correcting code, highlighting the role of topological order in fault-tolerant quantum computation.
Kitaev's quantum double models in 2D provide some of the most commonly studied examples of topological quantum order. In particular, the ground space is thought to yield a quantum error-correcting code. We offer an explicit proof that this is the case for arbitrary finite groups. Actually a stronger claim is shown: any two states with zero energy density in some contractible region must have the same reduced state in that region. Alternatively, the local properties of a gauge-invariant state are fully determined by specifying that its holonomies in the region are trivial. We contrast this result with the fact that local properties of gauge-invariant states are not generally determined by specifying all of their non-Abelian fluxes --- that is, the Wilson loops of lattice gauge theory do not form a complete commuting set of observables. We also note that the methods developed by P. Naaijkens (PhD thesis, 2012) under a different context can be adapted to provide another proof of the error correcting property of Kitaev's model. Finally, we compute the topological entanglement entropy in Kitaev's model, and show, contrary to previous claims in the literature, that it does not depend on whether the ``log dim R'' term is included in the definition of entanglement entropy.
We study a class of quantum error-correcting codes through the geometry of complex abelian varieties. These codes, introduced by Gottesman--Kitaev--Preskill, are built from symplectically integral lattices and therefore naturally define polarized complex abelian varieties. We give a precise mathematical formulation of this relationship and extend it to a dictionary between the main structures of GKP code theory and classical objects in the theory of abelian varieties. For instance, under this dictionary, the finite-dimensional code space becomes the space of theta functions H0(X,L), logical Pauli gates arise from the theta group, passive logical Clifford gates correspond to automorphisms of the polarized abelian variety, and concatenation with stabilizer codes corresponds to isogeny. We also prove several key results that give precise mathematical formulations of statements about these codes that often appear in heuristic form in the physics literature. In particular, we prove that the encoding is asymptotically isometric, that every logical Clifford gate is realized by a Gaussian unitary, and that, for noise of small variance, the failure probability is governed to first order by the shortest nontrivial displacement in the kernel of the polarization isogeny, a systolic invariant of the underlying polarization. This leads naturally to optimization problems on the moduli space of polarized abelian varieties.
Abstract The Kitaev honeycomb model is an approximate topological quantum error correcting code in the same phase as the toric code, but requiring only a 2-body Hamiltonian. As a frustrated spin model, it is well outside the commuting models of topological quantum codes that are typically studied, but its exact solubility makes it more amenable to analysis of effects arising in this noncommutative setting than a generic topologically ordered Hamiltonian. Here we study quantum error correction in the honeycomb model using both analytic and numerical techniques. We first prove explicit exponential bounds on the approximate degeneracy, local indistinguishability, and correctability of the code space. These bounds are tighter than can be achieved using known general properties of topological phases. Our proofs are specialized to the honeycomb model, but some of the methods may nonetheless be of broader interest. Following this, we numerically study noise caused by thermalization processes in the perturbative regime close to the toric code renormalization group fixed point. The appearance of non-topological excitations in this setting has no significant effect on the error correction properties of the honeycomb model in the regimes we study. Although the behavior of this model is found to be qualitatively similar to that of the standard toric code in most regimes, we find numerical evidence of an interesting effect in the low-temperature, finite-size regime where a preferred lattice direction emerges and anyon diffusion is geometrically constrained. We expect this effect to yield an improvement in the scaling of the lifetime with system size as compared to the standard toric code.
A Clifford template is a finite ordered family of repeatable Clifford operations, and an instantiation specifies how many times each operation is applied. The Clifford template compilation problem asks how to choose these repetition numbers so that the template realizes a target transformation of Pauli operators. This problem arises, for example, when searching for logical operations in quantum error correction using only Clifford operations permitted by physical or fault-tolerance constraints. Although forward Clifford dynamics is efficiently classically simulable, this inverse problem has sharp complexity transitions. For commuting templates with unrestricted integer exponents, feasibility lies in NP∩BQP and a constructive quantum algorithm returns a particular solution together with the full exponent-relation lattice; already at k=1, recovering the repetition number contains finite-field discrete logarithm over F2r×. In general, restricting every exponent to {0,1} removes the Abelian-group closure and makes feasibility NP-complete for variable k, even for exactly commuting CNOT-only operations and X-type Paulis. For commuting self-inverse Clifford actions, both binary feasibility and recovery of one solution are classically polynomial-time solvable, but imposing a bound on the total repetition count is NP-complete, even for CNOT-only operations. These results reveal a rich complexity landscape within Clifford template compilation, spanning classically tractable cases, problems admitting quantum polynomial-time algorithms, and NP-complete variants.
The goal of this paper is to provide a self contained detailed and rigorous mathematical introduction to some aspects of the quantum error-correcting codes and especially quantum stabilizer codes without venturing much, if at all, into the world of physics. While most of the results presented are not new, it is not easy to extract a precise mathematical formulation of results and to provide their rigorous proofs by reading the vast number of papers in the field, quite a few of which are written by computer scientists or physicists. It is this formulation and proofs - quite a few of of them new - that we present here. The connections between (a) quantum stabilizer codes and classical self-orthogonal codes and (b) between error correction and error detection have been established in details. Techniques from algebra of finite fields as well as representations of finite abelian groups have been employed here.