⚛️ quantum physics

Lower Bounds on Pauli Manipulation Detection Codes

This paper establishes the first trade-off between error parameter and coding rate for Pauli Manipulation Detection codes by proving a lower bound showing that the rate of any $q$ -ary PMD code of length $n$ is upper-bounded by $1 - \frac{2}{n}\log_q(1/\epsilon) + o(1)$ .

Original authors: Keiya Ichikawa, Kenji Yasunaga

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Keiya Ichikawa, Kenji Yasunaga

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a incredibly valuable secret message written on a piece of glass. You want to send this message across a noisy, chaotic room where invisible "gremlins" (errors) might try to poke, scratch, or flip the glass.

In the world of quantum computing, these gremlins are called Pauli errors. They are the most common type of troublemakers that can ruin quantum information.

This paper is about a special kind of "security seal" called a Pauli Manipulation Detection (PMD) code. Think of a PMD code as a magical, invisible force field around your message. Its job isn't necessarily to fix the scratches (that's error correction); its job is to scream, "Hey! Someone touched this!" with very high confidence.

Here is the breakdown of what the authors, Keiya Ichikawa and Kenji Yasunaga, discovered, explained simply:

1. The Big Question: How Small Can the Seal Be?

For years, scientists knew how to build these magical force fields (PMD codes). They knew how to make them work. But they didn't know the theoretical limit.

Think of it like building a fortress. We know how to build a castle that keeps out thieves, but we didn't know the minimum amount of stone required to make a castle that is 99% secure. Could you build a tiny, paper-thin fortress that was just as secure as a giant stone one? Or is there a hard rule that says, "To get this level of security, you must use this much extra space"?

This paper answers that question for the first time.

2. The Trade-Off: Security vs. Space

The authors found a strict rule of thumb: You cannot have high security without paying a price in space.

The Coding Rate (R): This is how much of your "storage space" is actually used for the real message versus the security seal. A high rate means you are using most of the space for the message and very little for the seal.
The Error Parameter (ε): This is how likely the system is to miss a tampering attempt. A low ε means the system is very strict and rarely misses a thief.

The Discovery:
The paper proves that if you want your system to be extremely strict (very low ε), you must sacrifice some of your message space to build a bigger security seal.

They found a mathematical formula that acts like a speed limit:

Rate ≤ 1 - (Constant × log of Security)

In plain English: If you want to make the chance of missing a tamper (ε) 10 times smaller, you have to give up a specific amount of your message space to build a stronger seal. You can't cheat physics; you can't have a tiny, invisible seal that catches every possible attack.

3. The "Magic Trick" They Used

How did they prove this? They used a clever statistical trick involving averages.

Imagine you are trying to test a lock. Instead of trying every single key in the world (which is impossible), you pick a specific, perfect set of keys that, on average, behave exactly like all possible keys.

In quantum physics, the "Pauli operators" (the gremlins) act like this perfect set. The authors realized that even though there are billions of ways a gremlin could attack, if you look at the average behavior of all these gremlins, it looks exactly like if they were attacking randomly from a giant, infinite bag of possibilities.

By using this "average" view, they could calculate the absolute minimum size the security seal must be to catch the gremlins. It's like proving that to catch a fly, you don't need to know exactly where it will fly next; you just need to know the size of the room it's flying in.

4. The Gap: We Are Close, But Not There Yet

The authors compared their new "minimum size" rule against the best "actual castle" built by a researcher named Bergamaschi in 2024.

The Rule (Lower Bound): Says you need at least X amount of stone.
The Castle (Upper Bound): The best castle built so far uses X + a little bit extra stone.

There is a small gap between the rule and the castle. It's like the rule says, "You need at least 10 bricks," but the best castle we've built uses 12 bricks. The authors suspect that with better building techniques, we might eventually get down to 10 or 11 bricks, but for now, there is a tiny gap we haven't closed yet.

Why Does This Matter?

This is a foundational paper. Before this, we didn't know the "laws of physics" for these quantum security codes. Now that we know the limits:

Engineers know the goal: They know exactly how much space they need to save to build perfect quantum security.
It connects to the real world: These codes are crucial for Quantum Tamper Detection. Imagine a future where you send a quantum key to unlock a bank vault. If a hacker tries to peek at it, the PMD code ensures the bank knows immediately. This paper tells us the absolute minimum cost to make that system secure.

The Takeaway

You can't have a perfect security system that takes up zero space. The more secure you want to be against quantum gremlins, the more "overhead" (extra space) you must pay. The authors have finally written down the exact price tag for that security.

1. Problem Statement

The paper addresses a fundamental gap in the theory of Pauli Manipulation Detection (PMD) codes.

Context: PMD codes, introduced by Bergamaschi [Ber24], are quantum coding schemes designed to detect every Pauli error with high probability. They serve as the quantum analogue to classical Algebraic Manipulation Detection (AMD) codes.
The Gap: While AMD codes have well-established tight lower bounds on their redundancy (tag length) and success probability, no lower bounds were previously known for PMD codes.
Objective: The authors aim to establish the first theoretical lower bound for PMD codes, specifically investigating the trade-off between the coding rate ( $R$ ), the code length ( $n$ ), and the error parameter ( $\varepsilon$ ).

2. Methodology

The proof strategy relies on the algebraic properties of Pauli operators and their relationship to unitary designs.

Definition of PMD Codes: A code is defined by a projection operator $\Pi$ onto a $q^k$ -dimensional subspace of $\mathbb{C}^{q^n}$ . It is an $(n, k, \varepsilon)_q$ -PMD code if for every non-identity Pauli error $E$ , the operator norm satisfies $\|\Pi E \Pi\|_\infty \leq \varepsilon$ . This condition implies that any corrupted state is nearly orthogonal to the code space.
Unitary 1-Design Property: The core of the proof exploits the fact that the set of $n$ $n$ -qudit Pauli operators ( $\mathcal{P}_n^q$ $P_{n}^{q}$ ) forms a unitary 1-design. This means the uniform average of Pauli operators behaves identically to the average over the entire unitary group (Haar measure) for first-order moments.
- Specifically, for any operator $O$ , $\frac{1}{|\mathcal{P}_n^q|} \sum_{E \in \mathcal{P}_n^q} E O E^\dagger = \frac{\text{Tr}(O)}{q^n} I$ .
Derivation Technique:
1. The authors construct an expectation value involving the code projector $\Pi$ and Pauli errors: $\max_{|\psi\rangle} \mathbb{E}_{E} [|\langle \psi | \Pi E^\dagger \Pi E \Pi | \psi \rangle|]$ .
2. Lower Bound Calculation: They evaluate this expectation using the 1-design property (Lemma 2), showing the value equals $q^{-\lambda}$ (where $\lambda = n-k$ is the redundancy).
3. Upper Bound Calculation: They derive an upper bound using the definition of the PMD code ( $\|\Pi E \Pi\|_\infty \leq \varepsilon$ for $E \neq I$ ).
4. Comparison: By equating the lower and upper bounds, they derive a constraint on $\varepsilon$ relative to the code parameters.

3. Key Contributions and Results

Main Theorem (Theorem 1)

The authors prove that for any $(n, n-\lambda, \varepsilon)_q$ -PMD code, the error parameter $\varepsilon$ must satisfy:
$\varepsilon \geq \sqrt{\frac{q^{2n-\lambda} - 1}{q^{2n} - 1}}$

Corollary: Rate vs. Error Trade-off

From the main theorem, the paper derives a lower bound on the redundancy $\lambda$ and an upper bound on the coding rate $R = k/n$ :
$R \leq 1 - \frac{2}{n} \log_q \left( \frac{1}{\varepsilon} \right) + o(1)$
This is the first known trade-off between the error parameter and the coding rate for PMD codes.

Comparison with Existing Constructions

Bergamaschi's Construction [Ber24]: Provides an explicit construction with redundancy $\lambda = 2\ell$ and error $\varepsilon \approx \sqrt{(2n+1)q^{-\ell}}$ .
The Gap: When applying the new lower bound to Bergamaschi's parameters, the theoretical minimum redundancy is $\ell - O(\log_q n)$ , while the construction uses $2\ell$ .
Implication: There is currently a gap of approximately $\ell$ between the best known construction and the theoretical lower bound. The authors suggest closing this gap may require techniques beyond unitary 1-designs or improved purity-testing constructions.

4. Significance

Foundational Theory: This work establishes the first theoretical limits for PMD codes, placing them on a firmer mathematical footing similar to classical AMD codes.
Connection to Classical Cryptography: The derived bound $R \leq 1 - \frac{2}{n}\log_q(1/\varepsilon)$ closely mirrors the known tight bounds for classical AMD codes ( $2\log(1/\varepsilon)$ redundancy). This suggests that optimal PMD code constructions likely exist and that the current gap is due to construction limitations rather than fundamental impossibility.
Quantum Security Applications: PMD codes are critical for:
- Approximate Quantum Error Correction: Allowing small error probabilities to outperform exact codes.
- Tamper Detection: Protecting quantum states against adversarial unitary attacks.
- Non-malleable Codes: Preventing adversaries from modifying quantum messages in meaningful ways.
Methodological Insight: The proof demonstrates the utility of treating Pauli operators as a unitary 1-design to analyze average-case behavior of quantum errors, a technique that may be applicable to other quantum coding problems.

Conclusion

Ichikawa and Yasunaga have successfully derived the first lower bound for Pauli Manipulation Detection codes, revealing a fundamental trade-off between coding rate and error detection capability. While a gap remains between their theoretical bound and existing constructions, the result strongly implies that efficient, near-optimal PMD codes are theoretically possible, guiding future research in quantum tamper detection and error correction.