Speaker
Description
Several quantum testing and learning tasks exhibit a striking
asymmetry: an algorithm that jointly measures multiple states is exponentially more powerful than one restricted to
single-copy measurements. Purity testing requires $\Omega(\sqrt{d})$
copies incoherently but only $\mathcal{O}(1)$ coherently; Pauli
shadow tomography on $n$ qubits requires $\Omega(2^n)$ incoherently
but only $\mathcal{O}(n)$ coherently. This memory gap motivates
delegation: a resource-bounded experimentalist hands the hard part
of a testing task to an untrusted helper and verifies the answer
cheaply. We develop a framework for such delegation in a
\emph{black-box} setting, where the verifier knows only the problem
description and a promise on the helper's per-round resource budget,
with no assumption about the helper's algorithm.
For Testing Problems, the interaction follows
a test-and-compute template in which the prover cannot distinguish
test rounds from compute rounds, preventing selective cheating.
Focusing on Many-vs-one Problems we identify four classes organised
by the structure certifying the
existence of a black-box interactive proof: two protocol classes,
TCB and RSM, and two structural classes, OSP and ORP, defined
by an orbital geometry on the instance space. The main results are
a universal RSM protocol generalising the purity testing
construction of Caro et al. (2025), and the containment
OSP $\subseteq$ RSM $\subseteq$ TCB, proven by showing that
orbiting and falling operator families supply the components to
instantiate the protocol. The framework reduces the design of
black-box interactive proofs to identifying geometric structure,
replacing protocol search with a question about symmetry and
distance.
| Topic | Theoretical foundations of quantum learning |
|---|---|
| Additional Topic | Quantum state reconstruction from data |