Interactive proofs for verifying (quantum) learning and testing
quant-ph, cs.CC, cs.DS, cs.LG
Submitted: 2024-10-31
Updated: 2026-09-17
Comments: 14 + 34 + 16 pages; 1 table; 2 figures; some added clarifications in Sec 1; accepted for publication in Quantum
License: http://creativecommons.org/licenses/by/4.0/
The gist: We consider the problem of testing and learning from data in the presence of resource constraints, such as limited memory or weak data access, which place limitations on the efficiency and
Terminology
Abstract
We consider the problem of testing and learning from data in the presence of resource constraints, such as limited memory or weak data access, which place limitations on the efficiency and feasibility of testing or learning. In particular, we ask the following question: Could a resource-constrained learner/tester use interaction with a resource-unconstrained but untrusted party to solve a learning or testing problem more efficiently than they could without such an interaction? In this work, we answer this question both abstractly and for concrete problems, in two complementary ways: For a wide variety of scenarios, we prove that a resource-constrained learner cannot gain any advantage through classical interaction with an untrusted prover. As a special case, we show that for the vast majority of testing and learning problems in which quantum memory is a meaningful resource, a memory-constrained quantum algorithm cannot overcome its limitations via classical communication with a memory-unconstrained quantum prover. In contrast, when quantum communication is allowed, we construct a variety of interactive proof protocols, for specific learning and testing problems, which allow memory-constrained quantum verifiers to gain significant advantages through delegation to untrusted provers. These results highlight both the limitations and potential of delegating learning and testing problems to resource-rich but untrusted third parties.
Sources
- Private Quantum Channels and the Cost of Randomizing Quantum Information
- Verifying Computations with Streaming Interactive Proofs
- Unconditionally verifiable blind computation
- Communication and Memory Efficient Testing of Discrete Distributions
- Quantum statistical query learning
- Training Compute-Optimal Large Language Models
- Foundations for learning from noisy quantum experiments
- Simpler Distribution Testing with Little Memory
- Efficient Pauli channel estimation with logarithmic quantum memory
- When Does Adaptivity Help for Quantum State Learning?
- Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms
- Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation
- Agnostic Tomography of Stabilizer Product States
- Bell sampling from quantum circuits
- Single-copy stabilizer testing
- Certifying almost all quantum states with few single-qubit measurements
- Random unitaries in extremely low depth
- Few Single-Qubit Measurements Suffice to Certify Any Quantum State
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity