Tough error models
- Field
- Topic
Problem
Determine \(c(e,n)\) and construct tough error models in the sense of [KW05]. Let \(H=\mathbb{C}^n\), and let an \(e\)-dimensional error model be a complex linear subspace \(E\subseteq\operatorname{End}(H)\) with \(1\le e\le n^2\). A linear subspace \(C\subseteq H\) corrects \(E\) exactly when, for every \(A,B\in E\), there is a scalar \(\lambda(A,B)\in\mathbb{C}\) such that
where \(P_C\) is the orthogonal projector onto \(C\). Define the guaranteed code dimension by
Determine \(c(e,n)\) in Eq. (2), exactly or with asymptotically matching bounds, and exhibit explicit tough error models whose largest correcting code is close to this value.
Source
Krüger and Werner explicitly introduce the extremal function \(c(e,n)\) and ask for tough error models attaining its scale [KW05].
Progress
The compression condition in Eq. (1) is the Knill–Laflamme criterion for perfect correction of the linear error space \(E\) [KLV00].
The Knill–Laflamme–Viola existence argument and the projection construction recorded in the source give the ceiling-sensitive bounds
\begin{equation} \left\lceil \frac{\left\lceil n/e^2\right\rceil}{e^2+1} \right\rceil \le c(e,n) \le\left\lceil\frac{n}{e}\right\rceil. \tag{3} \end{equation}The upper bound uses an error space spanned by nearly equal-rank orthogonal projections. The parameter gap is polynomial in \(e\) [KLV00], [KW05].
The one-error case can be settled exactly. For \(E=\operatorname{span}\{A\}\), the condition is a scalar compression of the Hermitian matrix \(A^\dagger A\). The Hermitian higher-rank numerical-range formula therefore gives
\begin{equation} c(1,n)=\left\lceil\frac{n}{2}\right\rceil. \tag{4} \end{equation}A positive matrix with simple spectrum makes the bound sharp [CKZ06]. At the other extreme, the upper construction in Eq. (3), together with the trivial one-dimensional code, gives \(c(e,n)=1\) for \(e\ge n\).
Weaver’s quantum Turán framework interprets scalar compressions as quantum anticliques [Wea19]. Allen and Kornell’s improved low-dimensional anticlique theorem applies to \(\mathcal{V}_E:=\operatorname{span}(\{I\}\cup \{A^\dagger B:A,B\in E\})\). Since \(\dim\mathcal{V}_E\le5\) when \(e=2\), it gives \(c(2,n)\ge\lceil n/9\rceil\), improving the historical lower bound of order \(n/20\) [AK25]. This remains far from the upper bound \(\lceil n/2\rceil\); general operator-system estimates also do not exploit all of the product structure in \(\mathcal{V}_E\).
Comment
The source calls an error model \(E\) “tough” when the largest code correcting \(E\) has dimension close to \(c(e,n)\) [KW05]. The unresolved task is to close the bounds in Eq. (3) for \(2\le e<n\) and construct such models at the correct scale. Results for structured Pauli noise or arbitrary operator systems do not determine Eq. (2).
References
- [KLV00]
- E. Knill, R. Laflamme, and L. Viola, “Theory of Quantum Error Correction for General Noise,” Physical Review Letters 84, 2525–2528 (2000).DOIarXiv
- [CKZ06]
- M.-D. Choi, D. W. Kribs, and K. Życzkowski, “Higher-Rank Numerical Ranges and Compression Problems,” Linear Algebra and its Applications 418, 828–839 (2006).DOIarXiv
- [KW05]
- O. Krüger and R. F. Werner (eds.), “Some Open Problems in Quantum Information Theory,” arXiv:quant-ph/0504166 (2005).DOIarXiv