⚛️ quantum physics

Random Exclusion Codes: Quantum Advantages of Single-Shot Communication

This paper introduces the random exclusion code (REC) as a single-shot communication primitive and demonstrates that quantum resources outperform classical strategies by achieving higher success probabilities and requiring smaller dimensions to describe detection events, while noting that such dimension advantages may not extend to the related random access codes (RACs).

Original authors: Joonwoo Bae, Kieran Flatt, Teiko Heinosaari, Oskari Kerppo, Karthik Mohan, Andrés Muñoz-Moller, Ashutosh Rai

Published 2026-02-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joonwoo Bae, Kieran Flatt, Teiko Heinosaari, Oskari Kerppo, Karthik Mohan, Andrés Muñoz-Moller, Ashutosh Rai

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 are playing a high-stakes game of "20 Questions" with a friend, but with a twist: you don't want to guess the answer; you just want to prove what the answer isn't.

This is the core idea behind a new study by a team of physicists who have invented a new way to test the power of quantum computers. They call it "Random Exclusion Codes" (RECs).

Here is the simple breakdown of what they did, why it matters, and how quantum mechanics wins the game.

The Game: "Don't Say It!"

In the world of information, we usually try to send a message and have the receiver guess the exact word. This is like sending a secret code and hoping your friend decodes "APPLE."

The researchers flipped the script.

The Sender (Alice) has a secret message made of two letters (like "A-B").
The Receiver (Bob) is asked to point to one of the letters and say, "I am 100% sure this letter is NOT the one Alice sent."
The Goal: Bob wins if he successfully excludes the wrong letter.

Think of it like this: Alice sends a secret word. Bob looks at a list of options and says, "I know for a fact it's not 'Banana'." If the word was actually "Apple," Bob wins. If the word was "Banana," Bob loses.

The Challenge: The "Bit" vs. The "Qubit"

To play this game, Alice has to send Bob a tiny package of information.

The Classical Way (The Bit): Alice can only send a simple "Yes/No" signal (a 0 or a 1). It's like sending a single coin flip.
The Quantum Way (The Qubit): Alice can send a "quantum coin." This coin can be in a strange state where it is spinning in a way that represents both heads and tails simultaneously, or anything in between.

The Results: Why Quantum Wins

The researchers ran this game with a specific setup: Alice has a 3-letter alphabet (A, B, C), and she sends a 2-letter word (like "A-C").

1. The Probability Advantage (Winning More Often)

Classical Limit: If Alice uses a simple coin (classical bit), the best Bob can do is guess correctly about 88.8% of the time. There is a hard ceiling; he simply doesn't have enough information to be sure.
Quantum Limit: If Alice uses a quantum coin (qubit), Bob can win about 91.5% of the time.
The Analogy: Imagine trying to guess which of three doors a cat is hiding behind. With a classical clue, you can rule out one door 8 out of 9 times. With a quantum clue, you can rule it out 9 out of 10 times. It's a small difference, but in the world of quantum physics, that gap proves that quantum resources are fundamentally more powerful.

2. The Dimension Advantage (The "Small Box" Trick)
This is the most mind-bending part. The researchers asked: How big of a "box" do we need to store the information to play this game perfectly?

The Classical Box: To play this game perfectly (100% success) and ensure the answers are fair, a classical system needs a box with 9 different slots (dimensions). It's like needing a 9-drawer filing cabinet to organize the data perfectly.
The Quantum Box: A quantum system can do the exact same perfect game using a box with only 4 slots.
The Analogy: It's like trying to fit a giant, complex puzzle into a suitcase. A classical suitcase needs to be huge (9 drawers) to hold all the pieces without them getting mixed up. A quantum suitcase is much smaller (4 drawers), but because the pieces can "fold" into each other in special ways, they fit perfectly inside.

The Twist: Why This is Different from "Guessing"

You might ask, "Why not just guess the letter?" The researchers compared their "Exclusion" game to a standard "Guessing" game (called Random Access Codes).

In a Guessing game, if you can guess the answer perfectly, you can also exclude the wrong answers perfectly. They are two sides of the same coin.
In an Exclusion game, the rules are different. The researchers found that you can play the "Exclusion" game perfectly with a tiny quantum box, but you cannot play the "Guessing" game perfectly with that same tiny box.

The Metaphor:
Imagine you are trying to find a specific key in a bunch of keys.

Guessing: You have to point to the exact right key.
Exclusion: You just have to point to a key that is definitely not the right one.

The study shows that while quantum mechanics helps you find the right key, it is even better at helping you confidently throw away the wrong ones, doing so with less physical space (dimension) than classical physics ever could.

Why Should We Care?

This isn't just a math puzzle. It proves that quantum computers aren't just "faster" versions of regular computers; they are fundamentally different.

Efficiency: We can do complex communication tasks using smaller, cheaper hardware (fewer dimensions) if we use quantum tricks.
Security: These "exclusion" games are related to how we generate random numbers and secure data. If a quantum system can do something a classical system physically cannot, we can use that to build unbreakable codes.
New Tools: By creating this "Exclusion Code," the researchers gave us a new tool to measure exactly where the line between the classical world and the quantum world lies.

In short: The universe has a secret shortcut. If you want to prove what something isn't, quantum mechanics lets you do it with less effort and smaller tools than the classical world ever dreamed possible.

1. Problem Statement

The paper addresses the fundamental challenge of identifying information tasks where quantum resources demonstrably outperform classical ones in single-shot communication scenarios (where a single outcome is obtained from a detection event). While Random Access Codes (RACs) have established quantum advantages in guessing tasks, the authors introduce a new primitive called Random Exclusion Codes (RECs).

In an REC, the goal is inverted compared to RACs:

Sender (Alice): Encodes a random message string $a = a_1...a_n$ (where each letter is from an alphabet of size $m$ ) into a system of dimension $d$ .
Receiver (Bob): Is asked to identify a specific index $i$ and must output a letter $b_i$ such that $b_i \neq a_i$ .
Objective: Maximize the probability of successfully excluding the correct letter.

The authors investigate whether quantum resources (qubits) offer advantages over classical resources (bits) in terms of:

Success Probability: The likelihood of a correct exclusion in a single shot.
Dimensional Efficiency: The minimum dimension required to achieve perfect (zero-error) exclusion, specifically under uniform outcome constraints.

2. Methodology

The authors employ a combination of analytical proofs, numerical optimization, and communication matrix theory.

Protocol Definition: They define an $(n, m)$ REC where $n$ is the message length and $m$ is the alphabet size. The specific focus is on the $(2, 3)$ case (2 trits, alphabet size 3) encoded into a 2-dimensional system (qubit or bit).
Classical Analysis: They analyze deterministic and probabilistic strategies for classical bits. They partition the set of possible messages and derive upper bounds on success probability by proving that any deterministic strategy must fail in at least a specific number of instances.
Quantum Analysis: They construct specific quantum protocols using:
- State Preparation: Pure qubit states (e.g., Trine states or specific superpositions on the Bloch sphere).
- Measurements: Positive Operator-Valued Measures (POVMs), including projective measurements and those with null elements.
- Optimization: They utilize the channelling of the problem to the Bloch sphere, restricting states and measurements to a great circle (XY-plane) to simplify the optimization of success probabilities.
Dimensional Analysis: To analyze the "dimension advantage," they utilize Communication Matrices. They calculate the Non-negative Rank (for classical systems) and the Positive Semidefinite (PSD) Rank (for quantum systems) of the matrix representing the task's conditional probabilities.
- Non-negative Rank ( $rank_+$ ): The minimum classical dimension required.
- PSD Rank ( $rank_{psd}$ ): The minimum quantum dimension required.

3. Key Contributions

A. Introduction of Random Exclusion Codes (RECs)

The paper formalizes RECs as a communication primitive based on quantum state exclusion (anti-discrimination). Unlike RACs, where guessing one value implies excluding the other (in binary cases), exclusion in larger alphabets ( $m > 2$ ) is operationally distinct and more general.

B. Quantum Advantage in Success Probability

The authors prove that for a $(2, 3)$ REC (encoding 2 trits into 1 qubit):

Classical Limit: The maximum average success probability for a classical bit is $8/9$ ( $\approx 0.888$ ).
Quantum Limit: The maximum average success probability for a single qubit is $(7 + \sqrt{2})/9$ ( $\approx 0.927$ ).
Result: There is a strict quantum advantage ( $\Delta \approx 0.046$ ).
Generalization: They extend this to $(2, m)$ RECs, showing that for any alphabet size $m \geq 2$ , the quantum success probability $1 - \frac{2-\sqrt{2}}{m^2}$ strictly exceeds the classical bound $1 - \frac{1}{m^2}$ .

C. Dimensional Advantage in Uniform Exclusion

The paper introduces a constraint of uniformity (all correct exclusion outcomes must occur with equal probability) to witness a dimensional gap.

Classical Requirement: To achieve perfect, uniform exclusion for a $(2, 3)$ REC, a classical system requires a dimension of 9 (Non-negative rank of the communication matrix is 9).
Quantum Requirement: The same task can be achieved perfectly with a quantum system of dimension 4 (two qubits, PSD rank is 4).
Contrast with RACs: The authors demonstrate that this dimensional advantage is unique to exclusion. For Random Access Codes (RACs), perfect implementation requires the same dimension (9) for both classical and quantum systems. This highlights that exclusion is a stronger signature of quantum behavior than discrimination/guessing.

D. Optimality Proofs

The authors provide analytical proofs (Appendix A) showing that the derived quantum success probability for the $(2, 3)$ REC is optimal among all two-outcome POVM strategies and that the optimal states lie on a great circle of the Bloch sphere.

4. Key Results

Metric	Classical Strategy	Quantum Strategy	Advantage
Max Success Prob. (2,3)	$8/9 \approx 0.888$	$(7+\sqrt{2})/9 \approx 0.927$	$\approx 4.6\%$
Min Dim. for Perfect/Uniform	9 (Non-negative Rank)	4 (PSD Rank)	Dimensional Gap
Min Dim. for Perfect RAC	9	9	No Gap

Probability Gap: $\Delta_{QC}^{(REC)} = \frac{\sqrt{2}-1}{9}$ .
Dimensional Gap: Quantum systems achieve perfect uniform exclusion with half the dimension required by classical systems (4 vs 9).
Inequivalence: The paper establishes that while a perfect RAC implies a perfect REC (via relabeling), a perfect REC does not imply a perfect RAC. This asymmetry explains why RACs lack the dimensional advantage seen in RECs.

5. Significance

New Quantum Primitive: The work introduces RECs as a robust tool for demonstrating quantum advantages in single-shot scenarios, complementing the existing literature on RACs and state discrimination.
Operational Distinction: It clarifies the operational difference between state discrimination (guessing) and state exclusion (anti-discrimination). The paper shows that exclusion is a more powerful signature of quantumness, particularly regarding dimensional efficiency.
Foundational Insight: The results reinforce the Pusey-Barrett-Rudolph (PBR) theorem's implications by showing that quantum resources can describe detection events in a lower-dimensional space than classical ontic models, specifically for exclusion tasks.
Practical Applications: By identifying tasks where quantum resources are more efficient (both in probability and dimension), the paper suggests potential applications in device-independent protocols, randomness extraction, and secure communication where minimizing resource overhead is critical.

In conclusion, the paper demonstrates that Random Exclusion Codes offer a distinct and powerful avenue for observing quantum advantages, surpassing classical limits in both the probability of success and the dimensional resources required, a feat not achievable by their guessing counterparts (RACs) in the same setting.