Minimal block length of permutation-invariant qubit codes

Problem

Is the least number of physical qubits on which a two-dimensional permutation-invariant code corrects arbitrary errors on \(t\) qubits equal to \(3t^2+3t+1\) for every integer \(t\geq1\)? For \(n\geq1\) let \(\operatorname{Sym}^n(\mathbb C^2)\subseteq(\mathbb C^2)^{\otimes n}\) denote the symmetric subspace, consisting of the vectors fixed by every permutation of the \(n\) tensor factors; a code contained in it is fully permutation-invariant, with every code vector, not merely the code projector, invariant under relabelling the qubits. A subspace \(\mathcal C\) with orthogonal projector \(P\) has distance \(d(\mathcal C)\geq d\) when \(PEP\) is a scalar multiple of \(P\) for every Pauli operator \(E\) acting nontrivially on fewer than \(d\) qubits, and it corrects arbitrary errors on \(t\) qubits exactly when \(d(\mathcal C)\geq 2t+1\). Define

\begin{equation} n_{\min}^{\mathrm{PI}}(t):=\min\bigl\{n\in\mathbb N:\ \exists\,\mathcal C\subseteq\operatorname{Sym}^n(\mathbb C^2),\ \dim\mathcal C=2,\ d(\mathcal C)\geq 2t+1\bigr\}. \tag{1} \end{equation}

The minimum in Eq. (1) ranges over all complex two-dimensional subspaces of the symmetric subspace and over both even and odd \(n\); no coefficient ansatz, reality condition, or transversal-gate requirement is imposed. The question is whether

\begin{equation} n_{\min}^{\mathrm{PI}}(t)=3t^2+3t+1 \qquad\text{for every integer } t\geq1 . \tag{2} \end{equation}

A complete answer proves Eq. (2) or exhibits an integer \(t\geq1\) for which it fails.

Source

Bond, Minář, Ozols, Safavi-Naini, and Visnevskyi state Eq. (2) explicitly as Conjecture 3.1, on the basis of the numerical searches of their Section 3.1 and Figs. 1 and 2 [BMO+26]. The quantity in Eq. (1) extends the single-error question studied by Pollatsek and Ruskai [PR04].

Progress

Pollatsek and Ruskai constructed two seven-qubit permutation-invariant codes that correct every single-qubit error (Section 6.2, Eq. (62)), so \(n_{\min}^{\mathrm{PI}}(1)\leq7\). Their necessary and sufficient conditions (Theorem 1) and their exclusion of a five-qubit code (Section 6.1) concern real coefficients, odd lengths, and a restricted code form, not every two-dimensional subspace of the symmetric subspace [PR04].
Ouyang’s gnu codes with \(g=n=2t+1\) and scaling \(u\geq1\) correct arbitrary errors on \(t\) qubits (Theorem 4). At \(u=1\) their length is \((2t+1)^2\), so \(n_{\min}^{\mathrm{PI}}(t)\leq(2t+1)^2\) for every \(t\), and permutation invariance is compatible with correcting any fixed number of errors [Ouy14].
Aydin, Alekseyev, and Barg define codes \(Q_{g,m,\delta,\epsilon}\) of length \(2gm+\delta+1\) and prove in Theorem 5.3 that they correct arbitrary errors on \(t\) qubits whenever \(m\geq t\), \(\delta\geq 2t\), and either \(g\geq 2t\) with \(\epsilon=-1\) or \(g\geq 2t+1\) with \(\epsilon=+1\). The choice \(Q_{2t,t,2t,-}\) gives the explicit bound

\begin{equation} n_{\min}^{\mathrm{PI}}(t)\leq 4t^2+2t+1 , \tag{3} \end{equation}

which matches Eq. (2) only at \(t=1\) [AAB24].
Section 7 of the same paper extends the Pollatsek–Ruskai conditions to every \(t\) for real, odd-length codes of a fixed parity-separated form (Proposition 7.1). For \(t=2\) and \(n=19\) these conditions are nine quadratic equations, and the authors report a real solution computed with the polynomial-system solver msolve, whose output is an interval for each variable containing an exact solution, cross-checked in Mathematica. This establishes a nineteen-qubit permutation-invariant code of distance five, so \(n_{\min}^{\mathrm{PI}}(2)\leq19\). The accompanying remark that no shorter \(t=2\) code exists refers to that ansatz and is stated without proof [AAB24].
Bond and collaborators minimize a Knill–Laflamme cost function, accepting a solution when the cost is below \(10^{-18}\) and the gradient below \(10^{-20}\), with up to \(1000\) random starts per length. With unrestricted complex coefficients the first solutions appear at \(n=7,19,37\) for \(t=1,2,3\); within the Pollatsek–Ruskai family they appear at \(n=7,19,37,61,91\) for \(t=1,\dots,5\) (Section 3.1, Figs. 1 and 2). They also note the quantum Singleton bound \(n\geq 4t+1\). Local numerical searches neither certify codes nor exclude shorter ones, so this is evidence for Eq. (2) rather than a proof [BMO+26].
In a different regime, Aydin, Albert, and Barg construct permutation-invariant codes whose local dimension \(q\) equals the block length \(N\), with code dimension \(K=o(2^N)\) and distance \(d=o(N/\log N)\) (Proposition VII.7 and Theorem VII.8). The growing local dimension is essential, so these codes do not bound the qubit quantity in Eq. (1) [AAB26].
Kubischta and Teixeira identify subspaces of \(\operatorname{Sym}^n(\mathbb C^2)\) with intrinsic codes in the spin-\(n/2\) representation of \(\mathrm{SU}(2)\), with intrinsic depth equal to qubit distance (Theorem B1, Lemma B1, and Proposition B2 of version 2). Their resulting linear program has a unique feasible enumerator for \(n=7\), \(K=2\), and distance three (Propositions B5–B6), and Appendix B-D states that the same program is infeasible at every shorter length, so no permutation-invariant \(((n,2,3))\) code exists for \(n<7\); the routine infeasibility checks are described in Appendix B-B but not written out. With the seven-qubit codes this gives \(n_{\min}^{\mathrm{PI}}(1)=7\) without any reality or ansatz restriction. The result appears in the 26 August 2026 revision of a preprint [KT26].
Teixeira identifies the intrinsic MacWilliams matrix of permutation-invariant qudit codes with a Racah polynomial system (Theorem 1 and Corollary 1). For qubits, Eq. (87) reads

\begin{equation} M_{ba}=\frac{2b+1}{n+1}\, {}_4F_3\!\left(\begin{matrix}-b,\ b+1,\ -a,\ a+1\\ 1,\ -n,\ n+2\end{matrix};1\right), \qquad 0\leq a,b\leq n, \tag{4} \end{equation}

where the generalized hypergeometric series terminates and \(a,b\) label the spin sectors of the operator space. Equation (4) makes the linear-programming bounds of the preceding item explicit for every \(n\), but the preprint does not evaluate them for \(t\geq2\) [Tei26].

Comment

The case \(t=1\) is settled: the seven-qubit codes of Pollatsek and Ruskai attain Eq. (2), and the unrestricted exclusion of shorter codes comes from the linear program of Kubischta and Teixeira, which is a preprint. For \(t=2\) the nineteen-qubit code of Aydin, Alekseyev, and Barg settles existence at the conjectured length, so the remaining question is whether a permutation-invariant distance-five code exists on at most eighteen qubits. For \(t\geq3\) neither an exact code of length \(3t^2+3t+1\) nor an unrestricted lower bound of that order was located; the explicit constructions give only Eq. (3), and the numerical searches are not proofs. A proof of Eq. (2) needs both a matching unrestricted lower bound and existence at the conjectured length for every \(t\), while a single \(t\) with a different value refutes it. The record Minimal permutation-invariant qubit code for two errors isolates the case \(t=2\); resolving it would not decide Eq. (2) for other \(t\). Literature checked through 15 September 2026.

References

[PR04]: H. Pollatsek and M. B. Ruskai, “Permutationally invariant codes for quantum error correction,” Linear Algebra and its Applications 392, 255–288 (2004).DOI arXiv
[Ouy14]: Y. Ouyang, “Permutation-invariant quantum codes,” Physical Review A 90, 062317 (2014).DOI arXiv
[AAB24]: A. Aydin, M. A. Alekseyev, and A. Barg, “A family of permutationally invariant quantum codes,” Quantum 8, 1321 (2024).DOI arXiv
[BMO+26]: L. J. Bond, J. Minář, M. Ozols, A. Safavi-Naini, and V. Visnevskyi, “Permutation-invariant codes: a numerical study and qudit constructions,” arXiv preprint (2026).arXiv
[AAB26]: A. Aydin, V. V. Albert, and A. Barg, “Quantum error correction beyond \(\mathrm{SU}(2)\): spin, bosonic, and permutation-invariant codes from convex geometry,” PRX Quantum 7, 010341 (2026).DOI arXiv
[KT26]: E. Kubischta and I. Teixeira, “MacWilliams identities for intrinsic quantum codes,” arXiv preprint, version 2 (2026).arXiv
[Tei26]: I. Teixeira, “Orthogonal polynomials and the MacWilliams transform for permutation-invariant qudit codes,” arXiv preprint (2026).arXiv

Minimal block length of permutation-invariant qubit codes

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems