⚛️ quantum physics

Interactive proofs for verifying (quantum) learning and testing

This paper investigates whether resource-constrained learners can benefit from interacting with untrusted, resource-rich provers, demonstrating that classical interaction offers no advantage for most learning and testing problems, whereas quantum communication enables significant efficiency gains through interactive proof protocols.

Original authors: Matthias C. Caro, Jens Eisert, Marcel Hinsche, Marios Ioannou, Alexander Nietner, Ryan Sweke

Published 2026-09-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthias C. Caro, Jens Eisert, Marcel Hinsche, Marios Ioannou, Alexander Nietner, Ryan Sweke

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

In the modern world of machine learning, success often depends on having access to vast amounts of data and immense computing power. The most advanced artificial intelligence models today are trained on terabytes of information using thousands of processors running for weeks, a process that costs millions of dollars and requires rare expertise. For many, the resources needed to train or even test these systems are simply out of reach. This creates a practical dilemma: what happens when a researcher or a small organization needs to solve a complex learning problem but lacks the necessary memory or processing capabilities? One natural solution is to ask for help. A resource-constrained party could send their data to a powerful, well-equipped service provider and ask them to do the heavy lifting. However, this introduces a new problem: how can the requester be sure the powerful provider is actually doing the work correctly and not just sending back a random answer? This question sits at the intersection of learning theory and cryptography, exploring whether a weak computer can verify the work of a strong, untrusted computer.

A team of researchers has now investigated this exact scenario, specifically looking at the unique challenges posed by quantum computing. In the quantum realm, a special kind of memory called quantum memory is a crucial resource. It allows a computer to hold onto multiple copies of a quantum state and measure them together in a way that reveals information impossible to find by measuring them one by one. Without this memory, many quantum learning and testing tasks become incredibly difficult, requiring exponentially more data to solve. The researchers asked a fundamental question: if a small quantum computer with limited memory interacts with a powerful, unlimited quantum computer, can the small one gain an advantage by asking the big one to help? Their answer depends entirely on how they talk to each other.

The study reveals a strict limitation when the two computers communicate using only classical signals, the same kind of bits used in everyday computers and the internet. The researchers proved that in this setting, a memory-constrained quantum verifier cannot gain any advantage by delegating a task to a powerful, untrusted prover. Even if the powerful computer has unlimited memory and can perform complex measurements on many copies of a data state at once, the small computer cannot use a classical conversation to bypass its own memory limits. If the small computer needs a certain number of data samples to solve a problem on its own, it will still need that same number of samples even if it asks the powerful computer for help. The powerful computer cannot simply "do the math" for the small one in a way that reduces the data burden, because the small computer cannot verify the result without having the data itself. This finding applies to a wide range of tasks, such as checking if a quantum state is pure or testing if a distribution of data is uniform.

However, the story changes completely when the two computers are allowed to communicate using quantum signals. In this setting, the researchers constructed specific protocols that allow the memory-constrained verifier to gain significant advantages. By sending quantum states directly to the powerful prover, the small computer can effectively outsource the memory-intensive parts of the calculation. The powerful computer can store and process many copies of the data simultaneously, performing the complex measurements that the small computer cannot. Crucially, the small computer can verify that the work was done correctly without needing to store all that data itself. The researchers demonstrated this with several concrete examples. For instance, in a task called purity testing, which determines if a quantum state is pure or mixed, a memory-constrained verifier usually needs a number of data copies that grows with the square root of the system's size. Through an interactive protocol using quantum communication, the verifier can solve the same problem using only a constant number of copies, regardless of the system size.

The researchers also developed methods for more complex learning tasks, such as reconstructing the full description of an unknown quantum state, known as state tomography. Normally, a computer with limited memory needs a number of samples that grows cubically with the size of the system, while a powerful computer with full memory only needs a quadratic number. The new protocols allow the limited computer to achieve a result that is better than what even the powerful computer could achieve alone, reducing the required samples to a linear growth rate. This is possible because the protocol allows the powerful computer to generate the solution using its own data, and the small computer then uses its own limited data to verify the quality of that solution. The researchers showed that this works for various types of learning problems, including learning specific types of quantum states called stabilizer states, where the limited computer can solve the problem with a number of samples that does not depend on the system size at all.

These findings highlight a sharp divide in the capabilities of quantum systems based on their communication channels. While classical communication offers no help to a memory-constrained learner trying to verify a powerful prover, quantum communication unlocks a new level of efficiency. This suggests that for future quantum technologies, the ability to transmit quantum information is just as critical as the ability to process it. The work provides a clear roadmap for when delegation is possible and when it is not, offering a foundation for building secure and efficient quantum learning systems where small devices can safely rely on powerful, untrusted servers. The results confirm that while resource constraints are a hard barrier in some contexts, the right kind of interaction can overcome them, turning an impossible task into a feasible one.

Technical Summary: Interactive Proofs for Verifying (Quantum) Learning and Testing

1. Problem Statement

Modern machine learning and quantum data processing often require resources (memory, data access, computational power) that exceed the capabilities of individual agents. This creates a scenario where a resource-constrained "verifier" ( $V$ ) must solve a learning or testing problem by interacting with a resource-unconstrained but untrusted "prover" ( $P$ ).

The central question addressed by this work is: Can a resource-constrained verifier gain a significant advantage in query, sample, or time complexity by interacting with an untrusted prover, compared to what the verifier could achieve in isolation?

The paper focuses on two specific types of resource constraints:

Memory Constraints: Specifically, the inability to perform coherent measurements on multiple copies of an unknown quantum state (single-copy vs. multi-copy access).
Oracle Constraints: Limitations in the type of data access available (e.g., statistical queries vs. random samples, or noisy vs. noiseless access).

The problems considered include many-vs-one distinguishing tasks (e.g., purity testing, state certification, uniformity testing) and agnostic learning problems (e.g., quantum state tomography, learning stabilizer states).

2. Methodology and Framework

The authors formalize the setting using an Interactive Proof (IP) framework adapted for learning and testing.

Definitions: A learning/testing problem is defined by an instance set, a model class, and a loss function. An interactive proof system $(V, P)$ is defined by Completeness (an honest prover convinces $V$ to accept a valid solution) and Soundness (no dishonest prover can convince $V$ to accept an invalid solution).
Resource Models:
- Verifiers: Constrained by limited quantum memory (single-copy measurements) or restricted oracle access (e.g., Statistical Queries).
- Provers: Unconstrained in memory (coherent multi-copy measurements) or oracle access, but untrusted.
- Communication: The paper distinguishes between classical communication and quantum communication channels.

The methodology involves two primary approaches:

No-Go Theorems: Proving that under certain conditions (specifically classical communication or oracle mismatches), the verifier cannot gain any complexity advantage. This is done by constructing a simulator that mimics the prover's actions using only the verifier's resources, thereby showing that the interaction adds no new computational power.
Constructive Protocols: Designing specific interactive proof protocols where the verifier does gain an advantage. These rely on:
- Verified Blind Quantum Computing (VBQC): Delegating the execution of a known quantum circuit to the prover while verifying correctness.
- Black-Box Protocols: Verifying the solution to a problem without the verifier needing to know the specific algorithm used to generate it.
- Certificate of Validity: Constructing efficient algorithms to verify if a candidate solution is valid, often by reducing the learning problem to a simpler distinguishing task.

3. Key Contributions and Results

3.1 Limitations (No-Go Results)

The paper establishes a fundamental limitation on the power of interactive proofs when communication is restricted.

Theorem 1 (Limitations for Many-vs-One Distinguishing): If a resource-constrained algorithm class $\mathcal{A}$ requires $m$ queries to solve a distinguishing task, and the honest prover's actions (given access to the "accept" instance) can be simulated by an algorithm in $\mathcal{A}$ , then the verifier must also make at least $m$ queries.
Implication for Classical Communication: For any scenario where the verifier is memory-constrained (single-copy) and communicates classically with a memory-unconstrained prover, no query complexity advantage is possible.
- Corollary 1: Memory-constrained quantum verifiers cannot overcome single-copy lower bounds for tasks like purity testing, state Pauli spike detection, state certification, and unitarity testing via classical delegation.
- Corollary 2: Verifiers with weaker oracle access (e.g., Statistical Queries) cannot gain advantages over provers with stronger access (e.g., Sample access) for tasks like parity testing or stabilizer testing.
- Corollary 6: NISQ (Noisy Intermediate-Scale Quantum) verifiers interacting with BQP provers still face exponential lower bounds for Pauli shadow tomography.

Key Insight: The presence of data (unknown quantum states) fundamentally changes the delegation landscape compared to standard delegated quantum computation (where classical communication suffices under cryptographic assumptions). Without quantum communication, the verifier cannot "outsource" the storage of unknown data required for coherent multi-copy processing.

3.2 Power of Interactive Proofs (Positive Results)

When quantum communication is allowed, the paper constructs protocols that allow memory-constrained verifiers to surpass known lower bounds.

Generic Protocols via VBQC (Observation 1): Using Verified Blind Quantum Computing, a single-copy verifier can delegate a coherent multi-copy algorithm to a prover. The verifier sends copies of the unknown state one by one. This allows the verifier to achieve the same query complexity as a coherent multi-copy algorithm, though it cannot surpass the multi-copy lower bound (since the prover does not use its own data).
Black-Box Protocols (Theorem 2/6): The authors construct a protocol for Purity Testing where the verifier treats the prover as a "problem-solving black box." The verifier only needs to know the problem description and that the prover can solve it with $m$ $m$ copies.
- Result: A single-copy verifier can solve purity testing with $O(1)$ copies, significantly beating the $\Omega(\sqrt{d})$ single-copy lower bound.
Outperforming Isolated Provers (Theorems 3, 4, 5): The paper presents protocols where the verifier uses fewer copies than even an unconstrained prover would need to solve the problem in isolation. This is achieved by delegating the heavy lifting (data processing) to the prover and using the verifier's limited data to verify the solution's validity.
- Quantum State Tomography (Theorem 3): A single-copy verifier uses $O(d \log(1/\delta)/\epsilon^2)$ copies, improving upon the optimal single-copy bound $\Omega(d^3/\epsilon^2)$ and the multi-copy bound $\Omega(d^2/\epsilon^2)$ .
- Agnostic Rank- $k$ Tomography (Theorem 4): A single-copy verifier uses $O(k^2 \epsilon^{-4} \log(1/\delta))$ copies, outperforming the multi-copy lower bounds.
- Agnostic Stabilizer Learning (Theorem 5): A single-copy verifier uses $O(\log(1/\delta)/\epsilon^2)$ copies, which is independent of the system size $n$ , whereas single-copy learning typically requires $\Theta(n^2)$ copies and multi-copy requires $\Theta(n)$ .

4. Significance and Claims

The paper claims to initiate the study of delegated quantum learning and testing. Its significance lies in:

Clarifying the Role of Data: It highlights a sharp distinction between delegating computation (where classical communication may suffice) and delegating learning/testing from data (where quantum communication is often necessary to overcome resource constraints).
Defining Limits: It provides rigorous "no-go" theorems showing that for many practical scenarios (NISQ devices, classical communication), delegation to untrusted servers offers no complexity advantage. This prevents unrealistic expectations for near-term quantum delegation.
Enabling New Protocols: It demonstrates that with quantum communication, resource-constrained parties can not only match but surpass the performance of unconstrained parties in isolation. This is achieved by shifting the burden of data storage and coherent processing to the prover while the verifier performs efficient validation.
Foundational Work: The authors state that this work provides a foundation for future research into concrete interactive proof protocols for quantum learning, a field with no prior direct comparisons for upper and lower bounds in the delegated setting.

The paper remains modest regarding specific experimental proposals, focusing instead on theoretical complexity bounds and the existence of protocols. It emphasizes that while VBQC provides a generic solution, the "black-box" and "outperforming prover" protocols offer more nuanced advantages for specific learning tasks.