Linear-size logarithmic-depth encoders for good quantum LDPC codes
- Fields
- Topics
Problem
Does some family of asymptotically good qubit CSS LDPC codes admit unitary encoding circuits with linearly many gates and logarithmic depth? Consider qubit CSS codes \([[n,k_n,d_n]]\) with \(n\to\infty\), \(k_n,d_n=\Omega(n)\), and check weights and qubit degrees bounded uniformly in \(n\). The question asks whether such a family has measurement-free unitary Clifford encoders \(V_n\) on its \(n\) physical qubits satisfying
where \(\operatorname{Enc}_n\) is an isometry onto the code space and \(V_n\) is a circuit of \(O(n)\) one- and two-qubit gates with depth \(O(\log n)\). The constants implicit in these bounds are independent of \(n\), and gates may act on arbitrary pairs of qubits.
Source
Wills, Lin, Zhang, and Hsieh note that it is not known whether there exist LDPC codes with low-depth or low-complexity encoders, even classically, and ask whether there must be a tradeoff between the parameters of a code, the depth or complexity of its encoder, and its maximum check weight [WLZ+26], Section 1.2, discussion of Open Problem 3. The statement specializes that question to good qubit CSS codes with bounded check weights and qubit degrees, measurement-free unitary Clifford encoders, \(O(n)\) gates, and \(O(\log n)\) depth, in the noiseless encoding model of their Section 4.1.
Progress
Wills, Lin, Zhang, and Hsieh construct asymptotically good qubit CSS codes, randomized in Theorem 1 and explicit in Theorem 2, that are encoded and unencoded by parallel quantum circuits of logarithmic depth with a linear number of gates, and decoded by classical circuits with a linear number of gates [WLZ+26], Theorems 1 and 2, retained in the revision of 22 June 2026. In their model the encoder acts on the message qubits and on check qubits prepared in \(|+\rangle\) or \(|0\rangle\) and may be taken to consist of CNOT gates (Section 4.1); preparing \(|+\rangle\) as \(H|0\rangle\) adds one layer of Hadamard gates and gives the form of Eq. (1). Hence these preprint theorems answer the question affirmatively without the LDPC requirement. They do not assert bounded check weights or qubit degrees.
Dinur, Hsieh, Lin, and Vidick construct explicit good quantum LDPC codes with linear-time decoders [DHLV23]. Efficient syndrome decoding does not bound the size or depth of a unitary encoder satisfying Eq. (1).
Logarithmic depth is necessary for linear distance, with or without the LDPC restriction, by a light-cone argument. Let \(P\) be a nontrivial Pauli operator on one logical input qubit, and let \(V_n\) have depth \(D\), each layer acting on every qubit at most once. Each layer of one- and two-qubit gates at most doubles the support of a conjugated operator, so the Pauli operator \(V_n(P\otimes I)V_n^\dagger\) is supported on at most \(2^D\) qubits. By Eq. (1) it maps \(\operatorname{Enc}_n|\psi\rangle\) to \(\operatorname{Enc}_nP|\psi\rangle\) for every \(|\psi\rangle\), so it is a nontrivial logical operator and has weight at least \(d_n\). Therefore
\begin{equation} d_n\le 2^{D}, \tag{2} \end{equation}and \(d_n=\Omega(n)\) forces \(D\ge\log_2 d_n=\Omega(\log n)\). This elementary deduction shows that the depth bound in the statement cannot be lowered to a constant.
Comment
Literature checked through 15 September 2026: no construction or impossibility theorem was found that meets the good-code, bounded-weight, linear-gate-count, and logarithmic-depth requirements simultaneously. The encoding model is ideal: gates are noiseless, no measurements or classical feed-forward are allowed, and no geometric locality is imposed. The circuit must encode arbitrary unknown logical states, so preparing one fixed code state, fast syndrome decoding, or fault-tolerant state preparation does not by itself answer the question. By Eq. (2) the depth requirement is optimal up to a constant factor for linear distance, and the version without the LDPC requirement is answered affirmatively in the preprint [WLZ+26]; the open issue is whether uniformly bounded check weights and qubit degrees are compatible with such encoders.