Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions

1. Problem Statement

The paper addresses a fundamental open problem in quantum cryptography: Can Non-Interactive Classical Verification of Quantum Computation (NI-CVQC) for the complexity class QMA be constructed based on standard falsifiable cryptographic assumptions?

• Context: Mahadev (2022) introduced the first protocol allowing a classical verifier to verify a quantum prover's computation, but it required 4 messages of interaction and relied on the Learning-with-Errors (LWE) assumption.
• The Gap: While subsequent works achieved non-interactivity (1 message) in the Quantum Random Oracle Model (QROM), achieving this in the plain model (without random oracles) remains an open challenge.
• The Question: Is it possible to construct a NI-CVQC protocol for QMA in the plain model based on falsifiable assumptions (like LWE, One-Way Functions, etc.)?
• Definitions:
  • NI-CVQC: A protocol where the verifier sends a public key (independent of the instance), and the prover sends a single classical proof.
  • Falsifiable Assumption: An assumption that can be cast as an efficient interactive game where a challenger can verify if an adversary wins (e.g., breaking LWE).
  • QMA vs. QCMA: QMA allows quantum witnesses; QCMA allows classical witnesses. The paper assumes the existence of a "gap" where QMA problems are hard even for adversaries with access to a QCMA oracle.

2. Key Contributions

The authors prove a strong negative result: There is no quantum black-box reduction from the soundness of a NI-CVQC protocol for QMA to any falsifiable assumption, provided a specific complexity-theoretic condition holds.

Main Theorem (Informal):
Assuming the existence of a subexponential QMA-QCMA gap problem, no quantum black-box reduction exists that derives the soundness of a NI-CVQC protocol from a falsifiable assumption.

Corollary:
Assuming LWE and the existence of a subexponential QMA-QCMA gap problem, there is no quantum black-box reduction of NI-CVQC to Mahadev's 4-message CVQC protocol. This implies that moving from 4 messages to 1 message (non-interactive) likely requires assumptions stronger than standard falsifiable ones (or non-falsifiable assumptions).

3. Methodology and Technical Approach

The proof follows a "black-box separation" framework similar to the seminal Gentry-Wichs separation for SNARGs, but adapted for the quantum setting and QMA. The methodology involves three major technical components:

A. The QMA-QCMA Gap Problem

The authors introduce a specific type of problem to drive the separation. A QMA-QCMA gap problem involves a language $L$ where:

1. Yes instances can be efficiently sampled with valid quantum witnesses.
2. No instances can be sampled (possibly inefficiently).
3. Indistinguishability: No efficient adversary with access to a QCMA oracle (an oracle that solves Promise-QCMA problems) can distinguish between Yes and No instances.

• Significance: This is slightly stronger than $QMA \neq QCMA$. It requires that even with a "classical witness solver" (QCMA oracle), the quantum hardness of the problem remains.

B. Modified Leakage Lemma with QCMA Oracles

In classical SNARG separations (Gentry-Wichs), a "Leakage Lemma" states that if two distributions are indistinguishable, they remain indistinguishable even when augmented with short auxiliary strings (which can be brute-forced).

• Challenge: In NI-CVQC, proofs are not necessarily short; the space of possible proofs is exponentially large, making brute-force search intractable.
• Solution: The authors augment the adversary with a QCMA oracle.
  • They argue that finding the correct auxiliary information (the "fake proof") is equivalent to finding a classical witness, which is a QCMA task.
  • They prove a Modified Leakage Lemma: Even with polynomial-length auxiliary information, the Yes/No distributions remain indistinguishable to an adversary with QCMA oracle access, provided the underlying problem is a QMA-QCMA gap problem.

C. From Sample Indistinguishability to Oracle Indistinguishability

A critical hurdle in quantum separations is that the honest prover in NI-CVQC is a quantum algorithm.

• Problem: Standard leakage lemmas show that samples from the "fake" distribution are indistinguishable from the "honest" distribution. However, a quantum reduction might query the prover as a unitary oracle.
• Solution: The authors utilize the Compressed Oracle technique (Zhandry et al.) to construct an efficient, stateful simulator $S$. They prove that $S$ is quantum-oracle-indistinguishable from the inefficient adversary $P$ that generates fake proofs. This allows the reduction to be "tricked" into thinking it is interacting with the honest prover when it is actually interacting with the simulator.

4. Proof Structure (The Separation Argument)

The impossibility proof proceeds by contradiction:

1. Assumption: Assume a NI-CVQC protocol $\Pi$ exists and is based on a falsifiable assumption $(C, c)$ via a quantum black-box reduction $\Sigma$.
2. Constructing the Adversary: Using the QMA-QCMA gap problem, the authors construct an inefficient adversary $P$ that generates valid-looking proofs for "No" instances (breaking soundness).
3. Simulating the Adversary: They construct an efficient simulator $S$ that is indistinguishable from $P$ even when accessed as a quantum oracle.
4. Breaking the Reduction:
   • Since $P$ breaks soundness, the reduction $\Sigma^P$ breaks the falsifiable assumption.
   • Since $S$ is indistinguishable from $P$, $\Sigma^S$ must also break the assumption.
   • However, $S$ is efficient. If $\Sigma^S$ breaks the assumption, it implies an efficient attack exists against the falsifiable assumption, contradicting the assumption's truth.
5. Conclusion: Therefore, no such reduction $\Sigma$ can exist.

5. Supporting Construction (Oracle Separation)

To support the plausibility of the "QMA-QCMA gap problem" assumption, the authors provide a construction relative to a Quantum Unitary Oracle:

• They define a language where "Yes" instances correspond to inputs $x$ paired with a specific Haar-random state $|\psi_x\rangle$.
• The oracle applies a phase flip to $|x\rangle|\psi_x\rangle$ if $x \in L$.
• They prove that distinguishing these instances requires the specific quantum state $|\psi_x\rangle$.
• Crucially, they show that even with access to a QCMA oracle (which can find classical witnesses), an adversary cannot distinguish the distributions, leveraging a result by Aaronson and Kuperberg regarding the indistinguishability of identity vs. phase-flip unitaries.

6. Significance and Implications

• Limits of Falsifiable Assumptions: The result establishes a fundamental barrier. It suggests that achieving Non-Interactive verification for general QMA problems in the plain model is likely impossible using standard cryptographic assumptions (like LWE).
• Complexity Theory: It deepens the understanding of the relationship between QMA and QCMA, suggesting that the gap between them is essential for certain cryptographic primitives.
• Future Directions:
  • The separation holds for adaptive soundness (where the prover chooses the false statement after seeing the public key). The paper notes that static soundness (statement chosen before the key) is not covered, leaving a potential avenue for construction.
  • The result applies to QMA. For BQP (where the witness is trivial), the primitive itself is falsifiable, so the separation does not apply directly, though the authors suggest a conditional impossibility for BQP under specific gap assumptions.
• Practical Impact: It implies that if we want non-interactive verification for complex quantum computations (QMA), we may need to rely on non-falsifiable assumptions (like the existence of indistinguishability obfuscation) or accept interaction (4+ messages).

Summary Table