Ari Karchmer

Quantum learning from remotely accessed and a priori unknown quantum data must address two key challenges: verifying the correctness of data and ensuring the privacy of the learner’s data-collection strategies and resulting conclusions. The covert (verifiable) learning model of Canetti and Karchmer (TCC 2021) provides a framework for endowing classical learning algorithms with such guarantees, protecting against computationally bounded adversaries who observe and tamper with public oracle queries. However, their framework has two drawbacks: it relies on computational hardness assumptions and does not flexibly accommodate richer data-access models, such as quantum ones. In this work, we propose models of covert verifiable learning in quantum learning theory and realize them without computational hardness assumptions for remote data access scenarios motivated by established quantum data advantages. We consider two privacy notions: (i) strategy-covertness, where the eavesdropper does not gain information about the learner's strategy; and (ii) target-covertness, where the eavesdropper does not gain information about the unknown object being learned. We show: - Strategy-covert algorithms for making quantum statistical queries via classical shadows; - Target-covert algorithms for: - learning quadratic functions from public quantum examples and private quantum statistical queries; - Pauli shadow tomography and stabilizer state learning from public multi-copy and private single-copy quantum measurements; - solving Forrelation and Simon's problem from public quantum queries and private classical queries, where the adversary is an i.i.d. ancilla-free eavesdropper. The lattermost results in particular establish that the exponential separation between classical and quantum queries for Forrelation and Simon’s problem survives under covertness constraints. Along the way, we design covert verifiable protocols for quantum data acquisition from public quantum queries which may be of independent interest. Overall, our models and corresponding algorithms demonstrate that quantum advantages are privately and verifiably achievable even with untrusted, remote data.