Homological Error Correction: Classical and Quantum Codes
arXiv:quant-ph/0605094 · doi:10.1063/1.2731356
Abstract
We prove several theorems characterizing the existence of homological error correction codes both classically and quantumly. Not every classical code is homological, but we find a family of classical homological codes saturating the Hamming bound. In the quantum case, we show that for non-orientable surfaces it is impossible to construct homological codes based on qudits of dimension , while for orientable surfaces with boundaries it is possible to construct them for arbitrary dimension . We give a method to obtain planar homological codes based on the construction of quantum codes on compact surfaces without boundaries. We show how the original Shor's 9-qubit code can be visualized as a homological quantum code. We study the problem of constructing quantum codes with optimal encoding rate. In the particular case of toric codes we construct an optimal family and give an explicit proof of its optimality. For homological quantum codes on surfaces of arbitrary genus we also construct a family of codes asymptotically attaining the maximum possible encoding rate. We provide the tools of homology group theory for graphs embedded on surfaces in a self-contained manner.
Revtex4 file
References in corpus (36)
- Fault-tolerant quantum computation by anyons
- Mixed State Entanglement and Quantum Error Correction
- Simple Proof of Security of the BB84 Quantum Key Distribution Protocol
- Good Quantum Error-Correcting Codes Exist
- Topological entanglement entropy
- Detecting topological order in a ground state wave function
- Decoherence Free Subspaces for Quantum Computation
- Topological quantum memory
- String-net condensation: A physical mechanism for topological phases
- Noiseless Quantum Codes
- Multiple Particle Interference and Quantum Error Correction
- A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound
- Controlling Spin Exchange Interactions of Ultracold Atoms in Optical Lattices
- Reliable Quantum Computers
- A Theory of Fault-Tolerant Quantum Computation
- Quantum Error Correction and Orthogonal Geometry
- Topologically-Protected Qubits from a Possible Non-Abelian Fractional Quantum Hall State
- Maintaining coherence in Quantum Computers
- Preserving coherence in quantum computation by pairing quantum bits
- Diverging Entanglement Length in Gapped Quantum Spin Systems
- Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory
- A Unified and Generalized Approach to Quantum Error Correction
- Simulation of topological field theories by quantum computers
- Implementation of Spin Hamiltonians in Optical Lattices
- Towards Universal Topological Quantum Computation in the Fractional Quantum Hall State
- A nonadditive quantum code
- Topological Quantum Computing with Only One Mobile Quasiparticle
- Realizing non-Abelian statistics
- Topological Protection and Quantum Noiseless Subsystems
- An extended Hubbard model with ring exchange: a route to a non-Abelian topological phase
- Pauli Exchange Errors in Quantum Computation
- A Line of Critical Points in 2+1 Dimensions: Quantum Critical Loop Gases and Non-Abelian Gauge Theory
- Self-dual random-plaquette gauge model and the quantum toric code
- Topological Quantum Error Correction with Optimal Encoding Rate
- Entanglement Distillation Protocols and Number Theory
- How to correct small quantum errors
Cited by in corpus (40)
- Roads towards fault-tolerant universal quantum computation
- Quantum Low-Density Parity-Check Codes
- Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
- A Family of Non-Abelian Kitaev Models on a Lattice: Topological Confinement and Condensation
- Optimal Resources for Topological 2D Stabilizer Codes: Comparative Study
- Balanced Product Quantum Codes
- Topological Subsystem Codes
- Quantum Measurements and Gates by Code Deformation
- Decoding color codes by projection onto surface codes
- Quantum Error Correction with the Semion Code
- Kitaev's Z_d-Codes Threshold Estimates
- Tradeoffs for reliable quantum information storage in surface codes and color codes
- Higher-dimensional quantum hypergraph-product codes
- Statistical Mechanical Models and Topological Color Codes
- Tailored XZZX codes for biased noise
- Topological color codes on Union Jack lattices: A stable implementation of the whole Clifford group
- General framework for constructing fast and near-optimal machine-learning-based decoder of the topological stabilizer codes
- Topological Color Codes and Two-Body Quantum Lattice Hamiltonians
- Generating Fault-Tolerant Cluster States from Crystal Structures
- A decoding algorithm for CSS codes using the X/Z correlations
- Quantum error correction with higher Gottesman-Kitaev-Preskill codes: minimal measurements and linear optics
- Error tolerance of topological codes with independent bit-flip and measurement errors
- Generalized Toric Codes Coupled to Thermal Baths
- Adiabatic topological quantum computing
- Spacetime replication of continuous variable quantum information
- An Interferometry-Free Protocol for Demonstrating Topological Order
- CSS code surgery as a universal construction
- Minimal distances for certain quantum product codes and tensor products of chain complexes
- Exact description of the boundary theory of the Kitaev Toric Code with open boundary conditions
- Anomaly inflow for CSS and fractonic lattice models and dualities via cluster state measurement
- Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High Performance
- The Need for Structure in Quantum LDPC Codes
- Union-Find Decoders For Homological Product Codes
- Efficient Code for Relativistic Quantum Summoning
- Counting stabiliser codes for arbitrary dimension
- Single-shot and measurement-based quantum error correction via fault complexes
- Subsystem CSS codes, a tighter stabilizer-to-CSS mapping, and Goursat's Lemma
- Single-shot preparation of hypergraph product codes via dimension jump
- Low-density parity-check representation of fault-tolerant quantum circuits
- Targeted Clifford logical gates for hypergraph product codes