Lower Bounds on Pauli Manipulation Detection Codes

Keiya Ichikawa, Kenji Yasunaga · 2025

Read Lower Bounds on Pauli Manipulation Detection Codes by Keiya Ichikawa, Kenji Yasunaga (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-00357.txt.

Introduction

Keiya Ichikawa and Kenji Yasunaga prove a limit, in a 2025 preprint, on a class of quantum error-detecting codes. Pauli manipulation detection codes are built to catch any Pauli error with high chance. Users face a trade-off between how much data the code carries and how surely it catches errors. No firm bound was known. The authors derive the first one, covering codes over alphabets of any size.

The bound says the rate must fall short of one by a term tied to the log of the inverse error chance, scaled by the code length. In plain terms, demanding a tinier miss chance forces a real rate cost. Bounds like this fence in what code designers can hope for, and future constructions can be measured against it.

Catalog record

CREATORKeiya Ichikawa, Kenji Yasunaga
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE13 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-00357

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lower Bounds on Pauli Manipulation Detection Codes Keiya Ichikawa, Kenji Yasunaga Abstract We present a lower bound for Pauli Manipulation Detection (PMD) codes, which enables the detection of every Pauli error with high probability and can be used to construct quantum erasure and tamper-detection codes. Our lower bound reveals the first trade-off between the error and the redundancy parameters in PMD codes. 1 Introduction Pauli Manipulation Detection (PMD) codes were introduced by Bergamaschi [ 2 ] as a coding scheme for detecting every Pauli error with high probability. PMD codes can be seen as a quantum analogue of Algebraic Manipulation Detection (AMD) codes [ 3 ] , which guarantee error detection of every additive error without using secret keys. Bergamaschi [ 2 ] provided an explicit construction of PMD codes based on purity testing codes [ 1 ] and demonstrated their applications in quantum error correction and tamper detection. Specifically, he constructed approximate quantum erasure codes approaching the quantum Singleton (or non-cloning) bound by combining PMD codes with list-decodable stabilizer codes. Also, he gave a construction of quantum tamper-detection codes for qubit-wise channels using classical non-malleable codes. AMD codes have been extensively studied since their introduction in [ 3 ] . Lower bounds on the adversary’s success probability and the tag size are known [ 3 , 4 , 9 ] , as well as near-optimal constructions [ 5 , 9 , 6 , 7 ] . However, no such lower bounds are known for PMD codes. In this work, we present the first lower bound for PMD codes. A q^{k} -dimensional subspace \Pi of \mathbb{C}^{q^{n}} is said to be an (n,k,\varepsilon)_{q} -PMD code if \|\Pi E\Pi\|_{\infty}\leq\varepsilon for every n -qudit Pauli error E\neq\mathbb{I} , where \|\cdot\|_{\infty} is the operator norm. (See Definition 1 for a formal definition.) We show that every (n,n-\lambda,\varepsilon)_{q} -PMD code satisfies \varepsilon\geq\sqrt{(q^{2n-\lambda}-1)/(q^{2n}-1)} , which also implies that \lambda\geq 2\log_{q}(1/\varepsilon)-\log_{q}2 . This bound reveals the trade-off between the error parameter \varepsilon and the redundancy parameter \lambda . Our derivation exploits the fact that the Pauli operators form a unitary 1 -design, allowing us to analyze the average behavior of Pauli errors in the same way as that of the entire unitary errors. 2 Preliminaries 2.1 Quantum States and Distances Let \mathcal{L}(\mathcal{H}) be the set of linear operators on a finite Hilbert space \mathcal{H} . Let A be a linear operator in \mathcal{L}(\mathcal{H}) . Then, A is said to be unitary if A^{\dagger}A=AA^{\dagger}=\mathbb{I} . We denote by \mathcal{U}(\mathcal{H}) the set of all unitary operators U\in\mathcal{L}(\mathcal{H}) , which is called the unitary group. An operator A is said to be Hermitian if A^{\dagger}=A . A projection operator is a Hermitian operator A such that AA=A . The trace of A\in\mathcal{L}(\mathcal{H}) is defined as \mathrm{Tr}(A)=\sum_{i=1}^{n}\bra{\vb*{e}_i}A\ket{\vb*{e}_i} , where \ket{\vb*{e}_1},\dots,\ket{\vb*{e}_n}\in\mathcal{L}(\mathcal{H}) are the orthogonal normal bases. The trace has the cyclic property of being invariant under circular shifts; \mathrm{Tr}(ABCD)=\mathrm{Tr}(BCDA)=\mathrm{Tr}(CDAB)=\mathrm{Tr}(DABC) . An operator A\in\mathcal{L}(\mathcal{H}) is positive semi-definite if \bra{\psi}A\ket{\psi}\geq 0 for any \ket{\psi}\in\mathcal{H} . A quantum state \rho\in\mathcal{L}(\mathcal{H}) is a linear operator that is positive semi-definite and trace 1 . We use the Schatten norms for quantifying the distances between quantum states. The operator (or infinity) norm is \|M\|_{\infty}=\max_{\ket{\psi}}\left|\bra{\psi}M^{\dagger}M\ket{\psi}\right|^{1/2} , where the maximum is taken over all quantum states \ket{\psi}\in\mathcal{L}(\mathcal{H}) . 2.2 q -ary Pauli Operators Let \mathbb{F}_{q} be a finite field of q=p^{m} elements for a prime p . The field trace is a function \mathrm{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}:\mathbb{F}_{q}\to\mathbb{F}_{p} such that \mathrm{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}(a)=\sum_{i=1}^{m}a^{p^{i}} . The set of elements \{\alpha_{1},\dots,\alpha_{m}\} is a basis of \mathbb{F}_{q} over \mathbb{F}_{p} if every a\in\mathbb{F}_{q} can be expressed uniquely as a=\sum_{i=1}^{m}a_{i}\alpha_{i} , where a_{i}\in\mathbb{F}_{p} . A pair of bases \alpha=\{\alpha_{1},\dots,\alpha_{m}\} and \beta=\{\beta_{1},\dots,\beta_{m}\} are said to be dual bases if \mathrm{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}(\alpha_{i}\beta_{j})=\delta_{ij} for every i,j\in[m]=\{1,\dots,m\} , where \delta_{ij}=1 if i=j , and \delta_{ij}=0 otherwise. When a,b\in\mathbb{F}_{q} are expressed as (a_{1},\dots,a_{m}) and (b_{1},\dots,b_{m}) in the dual bases \alpha and \beta , respectively, the inner product becomes the field trace; \langle a,b\rangle=\sum_{i=1}^{m}a_{i}b_{i}=\sum_{i=1}^{m}\sum_{j=1}^{m}a_{i}b_{j}\mathrm{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}(\alpha_{i}\beta_{j})=\mathrm{tr}_{\mathbb{F}_{q}/\mathbb{F}_{p}}(ab). We define the shift operator T and the phase operator R over \mathbb{C}^{p} as T=\sum_{x\in\mathbb{F}_{p}}\ket{x+1}\bra{x}\text{ and }R=\sum_{x\in\mathbb{F}_{p}}\omega^{x}\ket{x}\bra{x}, where \omega=e^{2\pi i/p} . The operators T^{i}R^{j} for i,j\in\mathbb{F}_{p} are said to be the Weyl-Heisenberg operators and form an orthogonal normal basis of operators over \mathbb{C}^{p} . If a,b\in\mathbb{F}_{q} are expressed as (a_{1},\dots,a_{m}) and (b_{1},\dots,b_{m}) in the dual bases \alpha and \beta , respectively, we can define a basis of operators over \mathbb{C}^{q} by E_{a,b}=X^{a}Z^{b}=\bigotimes_{i\in[m]}T^{a_{i}}R^{b_{i}}, where \otimes is the tensor product. Then, we have E_{a,b}E_{a^{\prime},b^{\prime}}=\omega^{\langle a,b^{\prime}\rangle-\langle a^{\prime},b\rangle}E_{a^{\prime},b^{\prime}}E_{a,b} . For \mathbf{a}=(a^{(1)},\dots,a^{(n)}),\mathbf{b}=(b^{(1)},\dots,b^{(n)})\in\mathbb{F}_{q}^{n} , we can define operators on \mathbb{C}^{q^{n}} by {E}_{\mathbf{a},\mathbf{b}}=\bigotimes_{j\in[n]}E_{a^{(j)},b^{(j)}} . The set of n qudit Pauli operators \mathbb{P}^{n}_{q} is \{{E}_{\mathbf{a},\mathbf{b}}:\mathbf{a},\mathbf{b}\in\mathbb{F}_{q}^{n}\} , and the n qudit Pauli group \mathcal{P}_{q}^{n} is the group generated by {E}_{\mathbf{a},\mathbf{b}} and \omega^{1/2}\cdot\mathbb{I}_{q^{n}\times q^{n}} . 2.3 Haar Measure and Unitary Designs For a unitary group \mathcal{U}(\mathbb{C}^{d}) for d\geq 1 , the Haar measure on \mathcal{U}(\mathbb{C}^{d}) is the unique probability measure \mu_{H} such that for every integrable function f and every V\in\mathcal{U}(\mathbb{C}^{d}) , \int_{\mathcal{U}(\mathbb{C}^{d})}f(U)d\mu_{H}(U)=\int_{\mathcal{U}(\mathbb{C}^{d})}f(UV)d\mu_{H}(U)=\int_{\mathcal{U}(\mathbb{C}^{d})}f(VU)d\mu_{H}(U). Since it is a probability measure, \int_{S}d\mu_{H}(U)\geq 0 for any S\subseteq\mathcal{U}(\mathbb{C}^{d}) and \int_{\mathcal{U}(\mathbb{C}^{d})}d\mu_{H}(U)=1 . The expected value of f(U) on \mu_{H} is \mathop{\mathbb{E}}_{U\sim\mu_{H}}[f(U)]=\int_{\mathcal{U}(\mathbb{C}^{d})}f(U)d\mu_{H}(U). A set of operators S\subseteq\mathcal{L}(\mathbb{C}^{d}) is called a unitary k -design if for every O\in\mathcal{L}(\mathbb{C}^{{d}^{k}}) , it holds that \mathop{\mathbb{E}}_{V\sim\nu_{S}}\left[V^{\otimes k}O{V^{\dagger}}^{\otimes k}\right]=\mathop{\mathbb{E}}_{U\sim\mu_{H}}\left[U^{\otimes k}O{U^{\dagger}}^{\otimes k}\right], where \nu_{S} is the uniform distribution over S . If S is finite, the left-hand side is equivalent to \frac{1}{|S|}\sum_{V\in S}V^{\otimes k}O{V^{\dagger}}^{\otimes k}. Intuitively, a unitary design is a set of operators that simulates the entire unitary operators. Regarding the definition of the unitary 1 -design, the right-hand side can be written as follows. Lemma 1 . [ 8 , Corollary 13] For every O\in\mathcal{L}(\mathbb{C}^{d}) , it holds that \mathop{\mathbb{E}}_{U\sim\mu_{H}}\left[UO{U^{\dagger}}\right]=\frac{\mathrm{Tr}(O)}{d}\mathbb{I}_{d\times d}. It is well known that the Pauli operators \mathbb{P}_{q}^{n} forms a unitary 1 -design, leading to the next lemma, which will be used in our proof. Lemma 2 . For every O\in\mathcal{L}(\mathbb{C}^{q^{n}}) , \frac{1}{\left|\mathbb{P}_{q}^{n}\right|}\sum_{E\in\mathbb{P}_{q}^{n}}EOE^{\dagger}=\frac{\mathrm{Tr}(O)}{q^{n}}\mathbb{I}_{q^{n}\times q^{n}}. It is known that every unitary 1 -design S\subseteq\mathcal{L}(\mathbb{C}^{d}) satisfies |S|\geq d^{2} [ 10 ] . Since |\mathbb{P}_{q}^{n}|=q^{2n} , the Pauli operators \mathbb{P}_{q}^{n} is an example of a minimum-sized unitary 1 -design. 3 PMD Codes and Their Lower Bounds A Pauli manipulation detection (PMD) code is defined as follows. Definition 1 . A projection operator \Pi on a q^{k} -dimensional subspace of \mathbb{C}^{q^{n}} is said to be an (n,k,\varepsilon)_{q} -PMD code if for every non-trivial Pauli operator E\in\mathcal{P}_{q}^{n}\setminus\{\mathbb{I}_{q^{n}\times q^{n}}\} , \|\Pi E\Pi\|_{\infty}\leq\varepsilon. We also denote by \Pi the code space defined by the projection \Pi . With this definition, we can see that any code state \ket{\psi_1} corrupted by a non-trivial Pauli operator E is almost orthogonal to the code space. Namely, for any code state \ket{\psi_2}\in\Pi , \displaystyle|\bra{\psi_1}E^{\dagger}\ket{\psi_2}| \displaystyle=\left|\bra{\psi_1}E^{\dagger}\Pi\ket{\psi_2}\bra{\psi_2}\Pi E\ket{\psi_1}\right|^{1/2} (1) \displaystyle\leq\|\Pi E^{\dagger}\Pi E\Pi\|^{1/2}_{\infty}=\|\Pi E\Pi\|_{\infty}\leq\varepsilon. We prove a lower bound on \varepsilon for any PMD code. Theorem 1 . Let \Pi be an (n,n-\lambda,\varepsilon)_{q} -PMD code. Then, it holds that \varepsilon\geq\sqrt{\frac{q^{2n-\lambda}-1}{q^{2n}-1}}. Proof. We consider the following value to derive our bound: \max_{\ket{\psi}}\mathop{\mathbb{E}}_{E\in\mathbb{P}_{q}^{n}}\left|\bra{\psi}\Pi E^{\dagger}\Pi E\Pi\ket{\psi}\right|, (2) where the maximum is taken over all quantum states \ket{\psi}\in\mathcal{L}(\mathbb{C}^{q^{n}}) . First, we evaluate ( 2 ) as follows: \displaystyle\max_{\ket{\psi}}\mathop{\mathbb{E}}_{E\in\mathbb{P}_{q}^{n}}\left|\bra{\psi}\Pi E^{\dagger}\Pi E\Pi\ket{\psi}\right| \displaystyle=\max_{\ket{\psi}}\mathop{\mathbb{E}}_{E\in\mathbb{P}_{q}^{n}}\mathrm{Tr}\left(\bra{\psi}\Pi E^{\dagger}\Pi E\Pi\ket{\psi}\right) (3) \displaystyle=\max_{\ket{\psi}}\frac{1}{|\mathbb{P}_{q}^{n}|}\sum_{E\in\mathbb{P}_{q}^{n}}\mathrm{Tr}\left(\bra{\psi}\Pi E^{\dagger}\Pi E\Pi\ket{\psi}\right) \displaystyle=\max_{\ket{\psi}}\frac{1}{|\mathbb{P}_{q}^{n}|}\sum_{E\in\mathbb{P}_{q}^{n}}\mathrm{Tr}\left(\Pi E\Pi\ket{\psi}\bra{\psi}\Pi E^{\dagger}\right) \displaystyle\because\text{The cyclic property} \displaystyle=\max_{\ket{\psi}}\mathrm{Tr}\left(\Pi\frac{1}{|\mathbb{P}_{q}^{n}|}\sum_{E\in\mathbb{P}_{q}^{n}}\left(E\Pi\ket{\psi}\bra{\psi}\Pi E^{\dagger}\right)\right) \displaystyle\because\text{The linearity} \displaystyle=\max_{\ket{\psi}}\mathrm{Tr}\left(\Pi\frac{\mathrm{Tr}\left(\Pi\ket{\psi}\bra{\psi}\Pi\right)}{q^{n}}\right) \displaystyle\because\text{Lemma~\ref{lem:unitary_design}} \displaystyle=\max_{\ket{\psi}}\frac{1}{q^{n}}\mathrm{Tr}\left(\Pi\ket{\psi}\bra{\psi}\Pi\right)\mathrm{Tr}(\Pi) \displaystyle=q^{-\lambda}. \displaystyle\because\mathrm{Tr}(\Pi)=q^{n-\lambda} (4) where ( 3 ) follows from the fact that the inner products take non-negative values and that

Read the complete text