Quantum information advantage based on Bell inequalities

This paper proposes an alternative quantum information advantage protocol based on parallel-repeated CHSH games that utilizes an information-based memory measure, offering an efficient verifier and a more noise-robust, efficient quantum prover compared to the recent experimental demonstration by Kretschmer et al.

The Gist

Here is an explanation of the paper using simple language, everyday analogies, and creative metaphors.

The Big Idea: A Memory Game with a Twist

Imagine you are playing a high-stakes memory game with a friend, but with a very strange rule: You cannot talk to each other during the game.

In this paper, the authors (Rahul Jain and Srijita Kundu) propose a new way to prove that Quantum Computers are fundamentally better at storing information than Classical Computers (like your laptop or phone).

They aren't trying to prove that quantum computers are faster at doing math. Instead, they are proving that quantum computers can solve a specific puzzle while using almost zero memory, whereas a classical computer would need a massive hard drive to do the same thing.

The Setup: The "Time-Travel" Phone Call

To understand their experiment, imagine a scenario involving two people, Alice and Bob, who are actually the same person (or the same computer) acting at two different times.

1. Time 1 (The Morning): Alice receives a secret code (Input X). She has to write down a hint (Output A) and then delete the code from her brain. She is only allowed to keep a tiny "note" (Memory M) to pass to her future self.
2. The Gap: Time passes. Alice is now Bob.
3. Time 2 (The Afternoon): Bob receives a different secret code (Input Y). He looks at the tiny "note" Alice left behind, combines it with the new code, and writes a second hint (Output B).
4. The Test: A referee checks if the Morning Hint and Afternoon Hint match a specific pattern based on the two secret codes.

The Challenge:

• The Classical Player: If you are a normal human (or a classical computer), to get the answer right, you need to remember everything about the Morning Code. You need a huge amount of memory (bits) to store the details of X so you can use them later.
• The Quantum Player: If you are a quantum computer, you can use a "magic trick" (entanglement). You can store the Morning Code in a way that holds no information about the code itself, yet still allows you to solve the puzzle perfectly when the Afternoon Code arrives.

The Magic Trick: The "Ghost" Note

The authors use a famous physics concept called the CHSH Game (a type of "Bell Inequality" test). Think of this as a game where Alice and Bob have to guess the outcome of a coin flip that depends on a secret rule.

• Classical Strategy: To win often, Alice must write down the secret rule on a piece of paper. If the rule is complex, the paper gets huge.
• Quantum Strategy: Alice and Bob share a pair of "entangled" coins. These coins are linked across space and time.
  • When Alice sees the Morning Code, she flips her coin.
  • When Bob sees the Afternoon Code, he flips his coin.
  • Because the coins are "ghostly" linked, they coordinate their answers perfectly without Alice needing to write down the Morning Code.

The Result:
The quantum player's "note" (Memory M) contains zero information about the Morning Code. It's like a blank piece of paper that somehow still helps you win.

• Classical Memory: Needs to be huge (thousands of bits).
• Quantum Memory: Needs to be tiny (effectively zero information about the input).

Why This Matters: The "Noise" Problem

In the real world, quantum computers are fragile. They are like glass houses in a storm; a little bit of "noise" (interference, heat, vibration) breaks the magic.

Previous experiments trying to prove this advantage failed because they required perfect, noise-free conditions. If the quantum computer made even a tiny mistake, the proof fell apart.

This paper's breakthrough:
The authors designed a version of the game that is noise-robust.

• Imagine playing the game not once, but 10,000 times in parallel.
• Even if the quantum computer is a bit "noisy" (making mistakes on some of the 10,000 tries), the sheer number of tries ensures that they still win most of the time.
• A classical computer, even with a huge memory, cannot win this many times because the math simply doesn't allow it without that massive memory.

The "Kretschmer" Comparison

The paper mentions a recent study by Kretschmer et al. that also tried to prove this.

• Kretschmer's Approach: Like trying to lift a heavy weight. It works, but it requires a very specific, complex setup (like preparing a random state that is hard to make).
• Jain & Kundu's Approach: Like juggling. It uses a simpler, more standard trick (the CHSH game) that is easier to build and much more resistant to errors. They argue their method is more practical for current technology.

The Takeaway

This paper proposes a new "Proof of Quantum Advantage."

Instead of asking, "Can a quantum computer solve this math problem faster?" they ask, "Can a quantum computer solve this puzzle while remembering almost nothing?"

The answer is yes. A quantum computer can act like a magician who remembers the trick without remembering the secret, while a classical computer needs to carry a giant encyclopedia of secrets to do the same job. And the best part? This magic still works even if the computer is a little bit "noisy" or imperfect.

In a nutshell:

• The Game: A memory challenge where you can't talk between steps.
• The Winner: Quantum computers win by using "spooky" connections instead of memory.
• The Innovation: This new game is simple, robust against errors, and proves that quantum memory is fundamentally different (and more efficient) than classical memory.

Technical Summary

Here is a detailed technical summary of the paper "Quantum information advantage based on Bell inequalities" by Rahul Jain and Srijita Kundu.

1. Problem Statement

The paper addresses the challenge of demonstrating Quantum Information Advantage (QIA). While previous works have shown quantum advantage in sampling tasks (e.g., Boson sampling) or computational complexity, these often rely on unproven complexity-theoretic assumptions (e.g., the hardness of sampling for classical computers).

A recent work by Kretschmer et al. [KGD+25] demonstrated a QIA where a quantum device solves a task with significantly less memory (12 qubits) than a classical device (62–382 bits). However, the [KGD+25] protocol relies on:

• Distributed linear cross-entropy benchmarking.
• Preparing Haar-random quantum states (which is resource-intensive and difficult to implement).
• An average-case definition of correctness that lacks standard interactive proof properties (completeness/soundness).
• A lack of rigorous asymptotic noise-robustness analysis.

The Goal: The authors propose an alternative protocol for QIA that is:

• Based on Bell inequalities (specifically CHSH games).
• Uses a more rigorous information-theoretic memory measure rather than just counting qubits.
• Features a noise-robust quantum prover.
• Employs a standard interactive proof framework with efficient verification.

2. Methodology

A. Core Concept: Parallel-Repeated CHSH Games

The authors utilize the CHSH game (a standard non-local game where inputs $x, y$ and outputs $a, b$ must satisfy $a \oplus b = x \cdot y$).

• Setup: The protocol is framed as a time-separated interaction between a Verifier and a Prover.
  • Time $t_0$: Verifier sends input $x$ (an $n$-bit string). Prover outputs $a$ and stores a memory register $M$.
  • Time $t_1$: Verifier sends input $y$ (an $n$-bit string). Prover uses $M$ and $y$ to output $b$.
• Winning Condition: The protocol accepts if the fraction of indices $i$ where $a_i \oplus b_i = x_i \cdot y_i$ is at least $t = 0.83n$ (a threshold parallel-repeated game).

B. Memory Measure: Smoothed Max Mutual Information

Unlike [KGD+25], which counts the raw number of qubits/bits, this paper defines memory cost via Smoothed Max Mutual Information, denoted as $I^\delta_{\max}(X : M)$.

• Definition: This measures the amount of information about the input $X$ contained in the memory register $M$, allowing for a small smoothing parameter $\delta$.
• Rationale: It is harder to maintain qubits in a state that retains information about an input than to maintain them in any state. A quantum strategy can store entanglement without storing information about $X$ (due to the no-signaling principle), whereas a classical strategy must store information about $X$ to correlate outputs with future inputs.

C. Protocol Structure

1. Verifier: A Probabilistic Polynomial Time (PPT) algorithm.
2. Prover: Can be Quantum Polynomial Time (QPT) or Classical.
3. Interaction:
   • Verifier sends $x \in \{0,1\}^n$.
   • Prover sends $a \in \{0,1\}^n$ and stores $M$.
   • Verifier sends $y \in \{0,1\}^n$.
   • Prover sends $b \in \{0,1\}^n$.
   • Verifier checks if $|\{i : a_i \oplus b_i = x_i y_i\}| \geq 0.83n$.

3. Key Contributions

1. New QIA Protocol based on Bell Inequalities:
   The authors construct a QIA proof using the threshold parallel-repeated CHSH game ($CHSH_{t/n}$). This avoids the need for complex Haar-random state preparation required by [KGD+25].

2. Information-Theoretic Memory Definition:
   They formalize QIA using $I^\delta_{\max}(X : M)$.

   • Quantum Case: The quantum prover uses $n$ EPR pairs. Due to the no-signaling principle, Bob's half of the EPR pair (the memory $M$) has zero mutual information with Alice's input $X$. Thus, $I(X:M) = 0$.
   • Classical Case: A classical prover must store information about $X$ in $M$ to correlate with $y$ later. The paper proves that if the classical memory has low information about $X$, the winning probability drops exponentially.

3. Noise Robustness:
   The protocol is robust to noise. If the quantum device has a noise level $\gamma$ such that the single-copy winning probability remains $\geq 0.85 - \gamma$, the protocol still succeeds with high probability for sufficiently large $n$. Specifically, they show robustness for $\gamma = 0.01$.

4. Efficient Verification:
   The verifier's task is simply to count the number of satisfied CHSH conditions, which can be done in $O(n)$ time. This contrasts with [KGD+25], where verification involves estimating cross-entropy, potentially requiring multiple rounds and complex calculations.

4. Results

The main result is formalized in Theorem 1:

• Existence: There exists a $(0, \Omega(n), 0.01)$ noise-robust proof of quantum information advantage.
• Quantum Completeness:
  • A quantum prover using $n$ EPR pairs (where the memory $M$ has $I(X:M)=0$) wins with probability $\approx 0.903$ (for $n \approx 1.17 \times 10^4$).
  • The quantum memory carries zero information about the input $X$.
• Classical Soundness:
  • Any classical prover with memory $M$ satisfying $I^\delta_{\max}(X : M) \leq \text{threshold}$ (where the threshold is roughly proportional to $n$) will win with probability at most $72\delta^2$(which is very small, e.g.,$\leq 0.5$ for specific parameters).
• Concrete Parameters:
  • For $n = 1.1697 \times 10^4$ and noise $\gamma = 0.01$, the protocol achieves a separation where the quantum memory information is 0, while a classical prover requires roughly 100 bits of information (though potentially more physical bits) to achieve a non-trivial win rate.
  • The winning probability for a classical prover with limited information memory is bounded by $1/2$.

5. Significance and Comparison with [KGD+25]

Feature	[KGD+25] (Kretschmer et al.)	Jain & Kundu (This Paper)
Underlying Task	Distributed Linear Cross-Entropy Benchmarking	Parallel-Repeated CHSH Game (Bell Inequality)
Memory Measure	Count of qubits/bits ($m$ vs $s$)	Information Measure ($I^\delta_{\max}(X:M)$)
State Preparation	Requires Haar-random states (hard to implement)	Requires EPR pairs (standard, feasible)
Noise Robustness	Not asymptotically analyzed; relies on specific ansatz	Proven robust to constant gate noise ($\gamma=0.01$)
Verification	Complex (estimating $\epsilon$); may require many rounds	Simple ($O(n)$ time check of CHSH conditions)
Completeness/Soundness	Average-case, non-standard interactive proof	Standard interactive proof definitions
Feasibility	Implementation of Haar-random states is difficult	Feasible with current technology (device-independent crypto context)

Conclusion:
This paper provides a more practical and theoretically rigorous framework for demonstrating Quantum Information Advantage. By shifting the metric from "number of qubits" to "information content in memory" and utilizing the well-understood CHSH game, the authors demonstrate a separation that is robust to noise, easier to verify, and feasible to implement with near-term quantum hardware. The protocol proves that quantum devices can solve a relational problem with zero information stored in memory about the first input, a feat impossible for classical devices without storing significant information.