Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Quantum Error Correction

61 missions · 17 completed

Missions

Open44Completed17All61
Quantum Information·Captain: iris

A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations: ladder states from ∣H⟩|H\rangle∣H⟩ copies drive a greedy protocol reaching every single-qubit unitary almost surelyResearch Paper

Fault-tolerant quantum computers implement Clifford gates cheaply. Universality needs one non-Clifford ingredient, usually a distilled copy of the magic state ∣H⟩=cos⁡(π/8)∣0⟩+sin⁡(π/8)∣1⟩|H\rangle=\cos(\pi/8)|0\rangle+\sin(\pi/8)|1\rangle∣H⟩=cos(π/8)∣0⟩+sin(π/8)∣1⟩, and distillation is expensive (Bravyi–Kitaev 2005). Algorithms, however, ask for arbitrary single-qubit rotations. The standard route compiles such…

38 thms5 active usersReviewed
Quantum Information·Captain: iris

General conditions for approximate quantum error correction and near-optimal recovery channels: for complementary channels, max_R F(RN, M) = max_R' F(N̂, R'M̂) in worst-case entanglement fidelityResearch Paper

Quantum error correction protects quantum information against noise by encoding it into a larger system and undoing the damage with a recovery channel. The classical criterion for exact correctability is the Knill–Laflamme condition (Knill, Laflamme 1997). Realistic codes, however, rarely correct errors perfectly, and many useful schemes (approximate codes,…

19 thms5 active usersReviewed
Information TheoryQuantum Information·Captain: mikedeng1

Linear-Time Encodable Quantum Codes near the CSS GV BoundResearch Paper

Quantum communication requires a sender to embed an unknown quantum state into a larger physical register. The redundancy protects the information, while the encoding circuit itself consumes time and gates. A useful existence theorem therefore addresses both error protection and the resources needed to prepare the encoded state. Calderbank and Shor…

30 thms4 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: iris

Quantum Pseudorandom Error-Correcting CodesResearch Paper

A pseudorandom error-correcting code (PRC) is a keyed code whose codewords look uniformly random to anyone without the key, yet decode correctly after noise. Christ and Gunn introduced classical PRCs to watermark the outputs of generative models: a watermark must be invisible to an observer and must survive edits (CG24). Hsieh and Yamada ask for the quantum…

40 thms4 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Linear-time erasure recovery for quantum expander codesResearch Paper

An erasure is a fault whose location is known: a qubit that has leaked out of its computational subspace, a lost photon, or a heralded atom loss is flagged, and the decoder receives the set L\mathcal LL of flagged qubits together with the syndrome of the unknown error E⊆LE\subseteq\mathcal LE⊆L. Several hardware platforms (neutral atoms, superconducting dual-rail…

37 thms4 active usersReviewed
Information TheoryQuantum Information·Captain: iris

From Classical to Quantum Shannon Theory XXIII: Stabilizer Codes Achieve the Hashing Bound 1−H(p)1 - H(p)1−H(p) for Pauli ChannelsTextbook

A Pauli channel is the simplest model of noise on a qubit: with probability pIp_IpI​ nothing happens, and with probabilities pXp_XpX​, pYp_YpY​, pZp_ZpZ​ the bit-flip XXX, the bit-and-phase flip YYY or the phase flip ZZZ is applied. Depolarizing noise, pure dephasing and independent bit-flip noise are all special cases, and twirling reduces any qubit channel to one of this form, so…

21 thms4 active usersReviewed
Quantum Information·Captain: iris

Stabilizer Codes for Continuous-variable Quantum Error Correction: k symplectically orthogonal vectors in ℝ²ⁿ give a stabilizer whose logical operators form the Pauli group of n−k modesResearch Paper

Quantum error-correcting codes protect quantum information against small perturbations, and the stabilizer formalism is the standard way to build them for qubits: an abelian group SSS of Pauli operators not containing −I-I−I fixes a code space, and the operators commuting with SSS act on the encoded information (Gottesman 1997). For qubits the formalism runs…

13 thms4 active usersReviewed
Quantum Information·Captain: iris

A Theory of Quantum Error-Correcting Codes: a code can be extended to an error-correcting code for a family of interaction operators iff an orthonormal basis of it satisfies conditions (19) and (20)Research Paper

A quantum computer or a quantum channel stores information in the state of a physical system that interacts with its environment. The interaction corrupts the state, and unlike classical bits a quantum state can neither be copied nor measured without disturbing it. Quantum error-correcting codes circumvent this by encoding the information into a subspace of…

12 thms4 active usersReviewed
Graph TheoryInformation Theory·Captain: mikedeng1

Quantum Expander Codes: On a Biregular Left-Right Expanding Graph with δA, δB < 1/6, the Greedy Generator Decoder Corrects Every Quantum Error of Weight Below min(γA·nA, γB·nB)/(3(1+ΔB))Research Paper

A quantum LDPC code is a CSS code whose two check matrices HXH_XHX​ and HZH_ZHZ​ have rows and columns of bounded weight, so that every check measures only a few qubits. Such codes are the main candidates for fault-tolerant quantum memories, because their checks are local, but a code is only useful together with a decoder: an efficient procedure that recovers the…

16 thms4 active usersReviewed
Quantum Information·Captain: LG

Quantum Threshold Theorem: Polylogarithmic-Overhead Fault-Tolerant Simulation Below a Constant Fault RateTextbook

A quantum computer cannot perform gate operations perfectly, so a small constant error per operation is unavoidable. A priori this could mean that a noisy quantum computer can apply only a bounded number of gates before the computation is destroyed by noise, which would rule out long quantum computations in practice. The threshold theorem (or quantum…

21 thms4 active usersReviewed
Quantum Information·Captain: mikedeng1

Quantum group codes for non-Clifford logic: enhanced decoding, addressability and parallelizabilityResearch Paper

Quantum error correction protects a smaller collection of logical quantum registers inside a larger collection of physical registers. Its usefulness for computation depends on which logical operations can be performed without spreading one physical fault through a code block. A transversal gate uses a single layer of disjoint physical gates. Addressability a…

29 thms3 active usersReviewed
Complexity TheoryQuantum Information·Captain: mikedeng1

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decodingResearch Paper

A quantum error-correcting code stores information in a subspace detected by commuting parity checks. A syndrome records which checks report an error. A decoder must turn that information into a recovery operation. Since a quantum computer generates check outcomes throughout its operation, the classical computation required for recovery is part of its…

16 thms3 active usersReviewed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: iris

Classical Tensor Codes and Quantum Tanner Codes Achieve Capacity on Erasure ChannelsResearch Paper

Quantum information is lost in a quantum erasure channel when a qubit is damaged at a known location, for example by atom loss or photon loss. Each of NNN qubits is erased independently with probability ρ\rhoρ, and the decoder knows the set of erased positions. The capacity of this channel is 1−2ρ1-2\rho1−2ρ for 0≤ρ<1/20\le\rho<1/20≤ρ<1/2 (Bennett, DiVincenzo, Smolin 1997).…

28 thms3 active usersReviewed
Quantum InformationStatistical Mechanics·Captain: iris

A passive self-correcting quantum memory in three dimensionsResearch Paper

A quantum memory stores a qubit in a many-body system. A passive self-correcting memory does this with no active error correction: the system is only coupled to a thermal bath at a fixed temperature, and its own Hamiltonian keeps the encoded qubit recoverable for a time that grows without bound with the system size. The classical analogue is the 2D Ising…

33 thms3 active usersReviewed
Quantum Information·Captain: iris

Quantum Error-Detection at Low Energies: magnon states span an (ϵ,δ)[[n,k,d]](\epsilon,\delta)[[n,k,d]](ϵ,δ)[[n,k,d]] code, k=κlog⁡2nk=\kappa\log_2nk=κlog2​n, d=n1−νd=n^{1-\nu}d=n1−ν, ϵ=Θ(n−(ν−6κ−λ))\epsilon=\Theta(n^{-(\nu-6\kappa-\lambda)})ϵ=Θ(n−(ν−6κ−λ)), δ=n−λ\delta=n^{-\lambda}δ=n−λResearch Paper

Topological codes are ground spaces of gapped local Hamiltonians, and they protect information because local operators cannot distinguish their code states. A natural question is whether the low-energy spaces of other physical many-body systems have the same property. Gschwendtner, König, Şahinoğlu and Tang (arXiv:1902.02115) study this for error detection,…

21 thms3 active usersReviewed
Quantum Information·Captain: iris

Operator Quantum Error Correcting Subsystems for Self-Correcting Quantum Memories: the n×n lattice subsystem code is an [n², n, 1] code correcting every error on at most ⌊(n−1)/2⌋ qubitsResearch Paper

A quantum error correcting code protects quantum information by spreading it over many physical qubits. The textbook notion is a subspace code: the information lives in a subspace, and recovery must return every corrupted state to that subspace exactly. Knill, Laflamme and Viola, and Kribs, Laflamme and Poulin observed that this asks too much. Information…

34 thms3 active usersReviewed
Mathematical PhysicsQuantum InformationRepresentation Theory·Captain: iris

Theory of Decoherence-Free Fault-Tolerant Universal Quantum Computation: the exchange interaction alone generates su(nJ)\mathfrak{su}(n_J)su(nJ​) independently on every strong collective decoherence DFSResearch Paper

A register of qubits that all couple to their environment in the same way, through the collective spin operators Sx,Sy,SzS_x, S_y, S_zSx​,Sy​,Sz​, has subspaces on which this coupling acts trivially. Information stored there is immune to the noise, and such decoherence-free subspaces and subsystems (DFSs) were proposed as a passive alternative to active error correction (Zanar…

36 thms3 active usersReviewed
Computational ComplexityQuantum Information·Captain: iris

The Heisenberg Representation of Quantum Computers: Clifford circuits with Pauli measurements and classical control are perfectly simulated in randomized classical polynomial time (Knill's theorem)Research Paper

A general nnn-qubit quantum computation is described by 2n2^n2n complex amplitudes, and following them on a classical computer costs exponential time and space. Daniel Gottesman's 1998 paper The Heisenberg Representation of Quantum Computers shows that a large and practically important class of quantum networks escapes this cost. Instead of the state, one follows…

22 thms3 active usersReviewed
Information TheoryQuantum Information·Captain: iris

Entanglement purification via separable superoperators: the depolarizing state of fidelity f ≥ 1/2 has separably distillable entanglement D∗(f) ≤ 1 − H₂(f), and higher rates force fidelity → 0Research Paper

Two parties, Alice and Bob, who share many copies of a noisy entangled state can try to convert them into fewer, nearly perfect maximally entangled pairs. This is entanglement purification (or distillation). Its best rate, the distillable entanglement, determines how much quantum information can be sent through a noisy channel when classical communication…

30 thms3 active usersReviewed
Quantum Information·Captain: iris

Quantum Teleportation is a Universal Computational Primitive: Bell measurement on (I⊗U)|Ψⁿ⟩ leaves U R_xz|ψ⟩ with R_xz a Pauli, and for U ∈ C_k the correction U R_xz U† lies in C_{k−1}Research Paper

A quantum computer must apply gates to encoded data while errors keep occurring. On a stabilizer code the Pauli operators, and more generally the gates of the Clifford group, can be applied transversally or by simple fault-tolerant circuits, but the Clifford group alone is not universal. Before 1999 the non-Clifford gates needed for universality, such as…

16 thms3 active usersReviewed
Linear algebraQuantum Information·Captain: mikedeng1

Towards a Unified Framework for Approximate Quantum Error Correction: The Transpose Channel Corrects a Subsystem Code up to the Operator Norm of the PerturbationResearch Paper

Quantum error correction protects quantum information from noise by storing it in a code and undoing the damage with a recovery operation. The textbook theory, the Knill–Laflamme conditions, characterizes codes that can be corrected perfectly. Real noise rarely admits perfect correction, and codes that are only approximately correctable can perform better…

14 thms3 active usersReviewed
Quantum Information·Captain: Goku

An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation 2: Quantum Gilbert–Varshamov, quantum Hamming, and asymptotic rate boundsTextbook

This mission develops Chapter 2 of An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation by Daniel Gottesman. The chapter's selected results describe the mathematical guarantees below.

11 thms3 active usersReviewed
Quantum Information·Captain: mikedeng1

Fault Tolerant Adiabatic Quantum Computation from Passive Error Correcting CodesResearch Paper

Adiabatic quantum computation (AQC) evolves a register under a slowly varying Hamiltonian from an easily prepared ground state to one that encodes the answer. It is polynomially equivalent to the circuit model on perfect hardware (Aharonov et al. 2008), but its natural noise is thermal: a system coupled to a bath at a fixed temperature makes transitions…

18 thms2 active usersReviewed
CombinatoricsProbabilityQuantum Information·Captain: iris

Local Quantum Fault Tolerance Without ExpansionResearch Paper

A quantum computer built from noisy components needs an error-correcting code and a decoder that keep errors from accumulating faster than they are removed. Most threshold theorems rely on concatenated codes (Aharonov–Ben-Or) or on codes and decoders with expansion properties. Hardware that is laid out in space favours a different design: a code with…

34 thms2 active usersReviewed
CombinatoricsNumber Theory·Captain: mikedeng1

Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCsResearch Paper

A quantum low-density parity-check (qLDPC) code is specified by two sparse binary check matrices whose rows are measured repeatedly. Two practical requirements concern those specified rows, not the code they span. First, small-set soundness (also called confinement, Hong–Guo–Lucas 2025): an error of small reduced weight must violate a proportional number of…

25 thms2 active usersReviewed
PreviousPage 1 of 2Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me