# Techniques: Learning Quantum Processes with Quantum Statistical Queries

## What the paper contributes (one paragraph)

The paper introduces the quantum statistical query model for quantum processes (the QPStat oracle, which returns an estimate of tr(O E(rho))) and studies what can be learned in it. Its main positive result is an efficient average-case algorithm for shadow tomography of an unknown quantum process: adapting classical shadows to this weaker, single-copy access model, it predicts the expectation values of many observables on randomly drawn input states, with a linear overhead in the number of observables that a nearly matching lower bound shows is unavoidable. On the negative side it proves exponential and doubly exponential average-case query lower bounds for learning unitary 2-designs and Haar-random unitaries to diamond-distance accuracy. It then applies the learning algorithm to mount a (quasi-polynomial) learning attack against authentication protocols built on Classical-Readout Quantum Physically Unclonable Functions, partially settling an open question in quantum hardware security.

## Techniques offered

- **Average-case shadow tomography of quantum processes (quantum statistical query learning)** - an efficient algorithm that, from QPStat queries to an unknown process, predicts expectation values of a list of observables on input states drawn from a distribution, adapting classical shadows to the single-copy statistical-query access model.
  - guarantee: statistical bound; predicts M observables on average over the input distribution to error epsilon with high probability at query cost linear in M, shown tight up to a logarithmic factor by a matching Omega(M) lower bound, and polynomial in qubit number for constant epsilon.
  - quote: "We present an efficient algorithm that can predict properties of quantum processes from QPSQs."

- **Learning attack on CR-QPUF authentication** - a cryptanalytic attack that uses the shadow-tomography learner to forge valid responses to challenges in Classical-Readout Quantum Physically Unclonable Function authentication protocols.
  - guarantee: statistical bound; under an unbiased-output assumption and few-body observables, an adversary passes verification with non-negligible probability in quasi-polynomial query and time complexity, for any underlying process and any single-qubit-Clifford-invariant challenge distribution.
  - quote: "We demonstrate an attack against CR-QPUF-based authentication protocols using \Cref{alg:avg-spt}."

## Where it could apply

- Target primitive(s): sampling / classical shadows / shadow tomography; expectation-value estimation of observables on outputs of an unknown channel.
- Target application group(s): platforms_tooling (process characterisation and benchmarking), crypto_security (CR-QPUF and quantum hardware authentication), quantum_ml (quantum learning theory).

## Caveats

The diamond-distance hardness results (exponential lower bound for unitary 2-designs, doubly exponential for Haar-random unitaries) are query-complexity lower bounds, that is no-go style guarantees and non-supplies, not a suppliable technique. The shadow-tomography guarantee is average-case over the input distribution, not worst-case, and the learner is restricted to single-copy measurement statistics with no entangled ancilla measurements. The CR-QPUF attack is quasi-polynomial, so it does not formally break the security definition; it relies on an unbiased-output assumption and few-body observables, and can be evaded by adding small biased noise to the device output.