Hidden-State Proofs of Quantumness

This paper presents a noise-robust cryptographic proof of quantumness that improves upon the Brakerski et al. (2018) protocol by hiding an extended GHZ state within classical bits, thereby allowing for significantly higher error tolerance while maintaining the same circuit structure.

The Gist

Here is an explanation of the paper "Hidden-State Proofs of Quantumness" using simple language and creative analogies.

The Big Picture: The "Are You a Robot?" Test

Imagine you are a judge trying to figure out if a mysterious machine in front of you is a super-smart human (a Quantum Computer) or just a very clever, but ultimately limited, robot (a Classical Computer).

In the world of cryptography, we call this a "Proof of Quantumness." The goal is to give the machine a puzzle that is easy for a quantum computer to solve but impossible for a classical computer to fake.

The Problem: Real-world quantum computers are messy. They are like a violinist playing in a hurricane; they make mistakes (noise). Previous tests were so strict that if the quantum computer made even a tiny mistake, it would fail the test, and we'd wrongly think it was just a classical robot. We needed a test that was robust—one that could handle a bit of "static" or "noise" without failing.

The Old Way: The "All-or-Nothing" Trap

The previous best test (by Brakerski et al., 2018) was like a game of "Find the Hidden Key."

1. The judge gives the machine a complex lock.
2. The machine has to find the specific key that opens it.
3. The Catch: If the machine gets one single digit of the key wrong, the whole attempt fails.

This is like asking someone to recite a 1,000-digit phone number perfectly. If they stumble on just one number, they lose. For a noisy quantum computer, this is too hard.

The New Solution: The "Hidden Party" Game

Carl Miller's paper introduces a new game called Game R. Instead of asking for one perfect key, this game hides a secret party inside a crowd of decoys.

The Analogy: The "Ghost Party" in a Crowd

Imagine a massive ballroom with 1,000 people.

• The Decoys: 900 of them are just regular people standing still. They are boring and predictable.
• The Ghosts: 100 of them are "ghosts" (entangled quantum particles). They are invisible to the naked eye but can dance in perfect sync with each other.

The Challenge:
The judge (Verifier) doesn't tell the player (Prover) who the ghosts are. The player just has to stand in the middle of the room and start dancing.

• If the player is a Classical Robot, they have to guess who is dancing with whom. Since they can't see the ghosts, they will mostly dance with the regular people (decoys) or get the rhythm wrong. They will fail the "dance-off" most of the time.
• If the player is a Quantum Computer, they can "feel" the ghosts. Even though they don't know exactly who is who, the quantum nature of the ghosts allows them to coordinate their dance moves perfectly with the hidden group, winning the dance-off almost every time.

Why is this better?
In the old test, if you missed one step, you lost. In this new test, because there are so many ghosts (a large group), you can make a few mistakes or miss a few steps, and you can still win the dance-off. The "noise" is absorbed by the size of the group.

The Secret Sauce: Cryptographic Hiding

How does the judge hide the ghosts so the robot can't cheat?
The judge uses a Cryptographic Lock (based on something called "Learning With Errors" or LWE).

• The judge creates a mathematical puzzle that looks like a random mess of numbers.
• Inside this mess, the judge hides the "ghosts" (the quantum state).
• To a classical computer, the mess looks truly random. There is no pattern to exploit.
• To a quantum computer, the mess contains a hidden structure (the ghosts) that it can exploit to win.

The paper proves that even if the classical computer tries to guess the pattern, the odds are so astronomically against them that they will fail, even if they are allowed to make a few mistakes.

The "Uncertainty Principle" Twist

To prove that the classical computer really can't win, the author had to invent a new mathematical tool.

• Think of the Heisenberg Uncertainty Principle (from physics) which says you can't know a particle's position and speed perfectly at the same time.
• The author created a "Mathematical Uncertainty Principle" for these number games.
• The Rule: You can't have a pattern that is both "simple" (easy for a classical computer to understand) and "hidden" (hard to find) at the same time. If the pattern is hidden enough to fool a classical computer, it must be complex enough that a classical computer cannot predict it, even with errors.

The Result: A Much Tougher Test for Robots

The paper shows that this new game (Game R) has a massive advantage for quantum computers over classical ones.

• Old Test: Quantum computers win by a factor of 2. (A coin flip).
• New Test: Quantum computers win by a factor that grows exponentially. (Like flipping a coin and getting heads 100 times in a row).

This means the test is extremely robust. Even if the quantum computer is very noisy and makes many errors, it can still prove it's a quantum machine.

Summary in One Sentence

This paper designs a new "quantum test" that hides a secret quantum dance party inside a crowd of decoys, making it impossible for a classical robot to fake the win, even if the quantum dancer is a bit clumsy and makes mistakes.

Technical Summary

Here is a detailed technical summary of the paper "Hidden-State Proofs of Quantumness" by Carl A. Miller.

1. Problem Statement

The paper addresses the critical challenge of implementing experimental cryptographic proofs of quantumness that are robust against noise.

• Context: While quantum computers are advancing, proving they possess a "quantum advantage" over classical computers is difficult. Previous methods, such as Google's random circuit sampling, relied on assumptions about classical simulation hardness that were later disproven.
• The Specific Gap: The seminal 2018 protocol by Brakerski et al. (based on the Learning With Errors, or LWE, assumption) provided a theoretical interactive proof of quantumness. However, this protocol suffered from low error tolerance. Specifically, the "pre-image test" required the prover to report an entire vector perfectly; even a small probability of error would cause a classical prover to fail too often or a quantum prover to score below the threshold required to distinguish it from a classical adversary.
• Goal: To design a proof of quantumness that maintains the efficient circuit structure of the Brakerski et al. protocol but significantly improves the bias ratio (the ratio of quantum winning probability to classical winning probability), thereby allowing for much higher noise tolerance.

2. Methodology

The author proposes a new protocol (Game $R$) and a sequential variant (Game $R'$) that cryptographically hides an extended Greenberger-Horne-Zeilinger (GHZ) state within a sequence of classical bits.

Core Mechanism: Cryptographic Hiding

• The Setup: The verifier generates a pair of injective functions $f_0, f_1$ based on LWE. The prover prepares a "claw-state" superposition.
• The Innovation: Unlike the original protocol where the prover holds a state $|s_0, 0\rangle + |s_1, 1\rangle$, the new protocol measures specific qubits immediately. The prover is left with a state of the form:
  $$\phi' = \frac{1}{\sqrt{2}} (|c, 0\rangle \pm |c', 1\rangle)$$
  where $c$ and $c'$ are bit strings. Crucially, the XOR string $c \oplus c'$ is cryptographically hidden from the prover.
• The Game: The verifier asks the prover to measure the qubits in specific bases (X, Y, or $(X+Y)/\sqrt{2}$). The bits where $c_j \neq c'_j$ form an entangled GHZ state, while bits where $c_j = c'_j$ act as "decoy" states. The prover must play a modified extended GHZ game without knowing which qubits are entangled.

Theoretical Tools

To prove the security and noise tolerance, the author introduces a novel Uncertainty Principle for Finite Abelian Groups:

• Theorem 1.2: This theorem refines the Donoho-Stark uncertainty principle. It states that if the product of the support sizes of a function $h$ and its Fourier transform $\hat{h}$ is close to the group size $|G|$, then $|h|$ must be nearly constant on an affine linear subset (a coset of a subgroup).
• Application: The classical bias of the game is expressed via the discrete Fourier transform. The proof shows that the support of the relevant functions is highly "non-linear," causing the classical bias to vanish exponentially as the parameter $d$ increases.

3. Key Contributions

1. High-Noise Tolerance Protocol: The paper presents Game $R$ and Game $R'$, which maintain the 2-round (or $(d+2)$-round) structure of the Brakerski et al. protocol but achieve a bias ratio that grows exponentially with a parameter $d$.
2. Exponential Bias Ratio:
   • For Game $R$, the classical bias is upper bounded by $\exp(-\Omega(d))$.
   • For Game $R'$, the classical bias is upper bounded by $2 \cdot (0.75)^{d/4}$.
   • The quantum bias remains high ($\approx \sqrt{2}/2$).
   • This implies the bias ratio is at least exponential in $d$, allowing the total error probability in the circuit to be as high as $1 - O(\lambda^{-C})$for any constant$C$.
3. New Uncertainty Principle: The paper proves a quantitative uncertainty principle (Theorem 1.2) relating the support of a function and its Fourier transform to its uniformity and linearity coefficients. This result is of independent mathematical interest.
4. Reduction to LWE: The paper rigorously proves that any classical strategy achieving a high score in these games can be used to break the LWE assumption, ensuring the protocol's soundness.

4. Results

• Theorem 1.1: Assuming the hardness of LWE, Games $R$ and $R'$ satisfy:
  • Quantum bias $\ge \sqrt{2}/2 - o(1)$.
  • Classical bias for $R$ $\le \exp(-\Omega(d)) + \text{negl}(\lambda)$.
  • Classical bias for $R'$ $\le 2 \cdot (0.75)^{d/4} + \text{negl}(\lambda)$.
• Parameter Scaling: The parameter $d$ can be set to $O(\log \lambda)$. This allows the bias ratio to grow polynomially in the security parameter $\lambda$ (specifically $\lambda^{\Omega(C)}$), making the protocol asymptotically robust against noise.
• Numerical Example: In Section 7, the author calculates that for specific parameters ($d=40$), a classical score above 0.1617 would imply a break of the LWE problem, whereas a quantum prover can achieve $\approx 0.7071$. This yields a quantum-to-classical bias ratio of roughly 4.37, significantly higher than previous iterations.

5. Significance

• Experimental Feasibility: This work bridges the gap between theoretical proofs of quantumness and experimental reality. By allowing for high error rates, it makes it possible to demonstrate quantum advantage on near-term, noisy quantum devices (NISQ era) without requiring full quantum error correction.
• Stability of Claims: Unlike previous attempts based on IQP or random circuit sampling, which faced challenges regarding the hardness of classical simulation assumptions, this protocol relies on the well-established and stable hardness of the LWE problem.
• Circuit Efficiency: The protocol does not require complex quantum homomorphic encryption (unlike some other high-bias approaches) and retains the simple circuit structure of preparing a single claw-state and performing single-qubit measurements.
• Mathematical Impact: The derived uncertainty principle for finite abelian groups provides a new tool for analyzing the limits of classical strategies in nonlocal games and cryptographic protocols.

In summary, Miller's paper provides a robust, noise-tolerant framework for verifying quantum computers, leveraging cryptographic hiding and advanced Fourier analysis to achieve exponential separation between quantum and classical capabilities.