The existence of quantum LDPC codes with minimal distance scaling linearly in the number of qubits is a central open problem in quantum information. Despite years of research good quantum LDPC codes are not known to exist, but at the very least it is known they cannot be defined on very regular topologies, like low-dimensional grids. In this work we establish a complementary result, showing that good quantum CSS codes which are sparsely generated require “structure” in the local terms that constrain the code space so as not to be “too-random” in a well-defined sense. To show this, we prove a weak converse to a theorem of Krasikov and Litsyn on weight distributions of classical codes due to which may be of independent interest: subspaces for which the distribution of weights in the dual space is approximately binomial have very few codewords of low weight, tantamount to having a non-negligible “approximate” minimal distance. While they may not have a large minimal non-zero weight, they still have very few words of low Hamming weight.
The existence of quantum LDPC codes with minimal distance scaling linearly in the number of qubits is a central open problem in quantum information. Despite years of research good quantum LDPC codes are not known to exist, but at the very least it is known they cannot be defined on very regular topologies, like low-dimensional grids. In this work we establish a complementary result, showing that good quantum CSS codes which are sparsely generated require “structure” in the local terms that constrain the code space so as not to be “too-random” in a well-defined sense. To show this, we prove a weak converse to a theorem of Krasikov and Litsyn on weight distributions of classical codes due to which may be of independent interest: subspaces for which the distribution of weights in the dual space is approximately binomial have very few codewords of low weight, tantamount to having a non-negligible “approximate” minimal distance. While they may not have a large minimal non-zero weight, they still have very few words of low Hamming weight.
The existence of quantum locally generated codes is a long standing open problem in quantum information theory. In this thesis, we consider a bound concerning this conjecture as well as a few constructions with codes that are `barely non-local'. We establish a complementary result to Bravyi and Terhal, and show quantum codes which are ``strongly'' not embeddable into finite dimensional lattices must also have poor distance. Along the way we derive some results concerning "pseudorandom" classical codes.\nGiven that quantum codes seem to be difficult to construct, it seems useful to examine "bad" quantum codes for applications in information and communication. Indeed, most of the work in quantum error correction by researchers today is in this direction. We construct a "nearly local" quantum erasure code which can achieve the capacity of the quantum erasure channel. This code has very poor (adversarial) distance, but still manages to correct random erasure errors with high probability. The codes use random Erdos-Renyi graphs to construct quantum states which are nearly local, but also highly entangled across fixed cuts with high probability. We derive some new results concerning classical codes with log-sparse parity check matrices which may be of independent interest.\nInspired by this construction, we are able to construct new approximate unitary 2-designs or "scramblers". The study of scrambling is the study of the mixing properties of different distributions of random unitaries. There is an inherent duality between the study of scrambling and the study of error correction: A good quantum code will make a good scrambler and vice versa. We study the scrambling properties of our random Erdos-Renyi graph state encoding circuits. We are able to show that these circuits, when supplemented by some local "Expander Graph" quantum circuits, form approximate unitary 2-designs. This construction, strictly speaking, does not achieve more efficient parameters than existing approximate 2-designs, but might have implementation advantages over other designs and points to a conjecture which could yield approximate unitary designs with time independent qubit-to-qubit coupling. This would be an extremely interesting construction in the context of experimental randomized benchmarking.
We propose a method for modifying orthogonal sparse matrix pairs used in CSS codes while preserving their matrix row and column weight distributions, which play a crucial role in determining the performance of belief-propagation decoding. Unlike simple row or column permutations that merely reorder existing elements, the proposed local modification introduces genuine structural randomness through small 2×2 cross-swap operations followed by integer-linear-program-based local repairs that restore orthogonality. By applying this procedure repeatedly in a random manner, ensembles of randomized quantum LDPC codes can be constructed. The computational complexity of each repair depends only on the maximum row and column weights and is independent of the overall matrix size, ensuring scalability to large code blocks.
Quantum low-density parity-check (LDPC) codes are an important class of quantum error correcting codes. In such codes, each qubit only affects a constant number of syndrome bits, and each syndrome bit only relies on some constant number of qubits. Constructing quantum LDPC codes is challenging. It is an open problem to understand if there exist good quantum LDPC codes, i.e. with constant rate and relative distance. Furthermore, techniques to perform fault-tolerant gates are poorly understood. We present a unified way to address these problems. Our main results are a) a bound on the distance, b) a bound on the code dimension and c) limitations on certain fault-tolerant gates that can be applied to quantum LDPC codes. All three of these bounds are cast as a function of the graph separator of the connectivity graph representation of the quantum code. We find that unless the connectivity graph contains an expander, the code is severely limited. This implies a necessary, but not sufficient, condition to construct good codes. This is the first bound that studies the limitations of quantum LDPC codes that does not rely on locality. As an application, we present novel bounds on quantum LDPC codes associated with local graphs in D -dimensional hyperbolic space.
Classical low-density parity-check (LDPC) codes are a widely deployed and well-established technology, forming the backbone of modern communication and storage systems. It is well known that, in this classical setting, increasing the girth of the Tanner graph while maintaining regular degree distributions leads simultaneously to good belief-propagation (BP) decoding performance and large minimum distance. In the quantum setting, however, this principle does not directly apply because quantum LDPC codes must satisfy additional orthogonality constraints between their parity-check matrices. When one enforces both orthogonality and regularity in a straightforward manner, the girth is typically reduced and the minimum distance becomes structurally upper bounded. In this work, we overcome this limitation by using permutation matrices with controlled commutativity and by restricting the orthogonality constraints to only the active part of the construction, while preserving regular check-matrix structures. This design circumvents conventional structural distance limitations induced by parent-matrix orthogonality, and enables the construction of quantum LDPC codes with large girth while avoiding latent low-weight logical operators. As a concrete demonstration, we construct a girth-8, (3,12)-regular [[9216,4612,≤48]] quantum LDPC code and show that, under BP decoding combined with a low-complexity post-processing algorithm, it achieves a frame error rate as low as 10−8 on the depolarizing channel with error probability 4%.
Quantum codes with low-weight stabilizers known as LDPC codes have been actively studied recently due to their simple syndrome readout circuits and potential applications in fault-tolerant quantum computing. However, all families of quantum LDPC codes known to this date suffer from a poor distance scaling limited by the square-root of the code length. This is in a sharp contrast with the classical case where good families of LDPC codes are known that combine constant encoding rate and linear distance. Here we propose the first family of good quantum codes with low-weight stabilizers. The new codes have a constant encoding rate, linear distance, and stabilizers acting on at most n qubits, where n is the code length. For comparison, all previously known families of good quantum codes have stabilizers of linear weight. Our proof combines two techniques: randomized constructions of good quantum codes and the homological product operation from algebraic topology. We conjecture that similar methods can produce good stabilizer codes with stabilizer weight na for any a>0. Finally, we apply the homological product to construct new small codes with low-weight stabilizers.
A recent preprint (arXiv:2609.40252) extends the local coordinate-wise linear (LCL) witness framework of Levi, Mosheiff, and Shagrithaya from classical linear codes to CSS quantum codes. The central structural difficulty is that a CSS code is a nested pair of spaces S ⊆ C, so a local witness has two ranks: a physical rank on representatives in C and a logical rank in the quotient C/S. The resulting theory yields a threshold theorem for random CSS codes whose striking corollary is that the per-sector rate threshold equals the classical rate threshold, together with quantum subspace designs and explicit folded constructions that are themselves qLDPC — the first explicit quantum list-decodable and list-recoverable codes with optimal list sizes. This paper is a reconciled analytical companion to that work. We compute the binary entropy H₂(0.1) = 0.468996 and the associated classical threshold R* = 1 − H₂(0.1) = 0.5310, exhibit a concrete random CSS allocation with per-sector rates R_X = R_Z = 0.3 and total rate 0.4 that lies strictly below threshold in both sectors, and quantify the downstream resource consequences: a rate-1/2 good qLDPC code uses 2 physical qubits per logical qubit — a rate statement independent of distance; at matched distance d = 100 this requires block length n ≈ 910 (relative distance δ ≈ 0.11, the largest value consistent with the quantum Hamming bound at R = 1/2), versus 19,999 for a surface code — a factor of ≈10⁴ on locality-permissive architectures, conditional on the distance being achieved at that block length. We also present an alternative threshold convention (R* = 1 − H(p) − 1/L) used in one source draft for fixed list size L, and document the resolution in Appendix A. We identify finite-length behavior, decoder realizability, and check geometry as the principal gaps between the asymptotic theory and deployable systems. ## 1. Introduction The gold standard in coding theory is a code that is explicit, efficient to encode and decode, and Full text and updates: papers.qnfo.org/papers/from-random-quantum-codes-to-explicit-qld-codes-a-reconciled-threshold-analysis-/