Smooth and sharp complexity transitions in learning with bounded quantum memory

Learning properties of unknown quantum systems or processes is of fundamental importance to the development of quantum technologies. While many learning algorithms require access to external ancillary qubits (referred to as quantum memory), the statistical complexity and experimental costs for these algorithms vary considerably due to different sizes of quantum memory. Here, we investigate the transitions for statistical complexity required for learning quantum data with bounded quantum memory. On the one hand, we study the Pauli shadow tomography problem: estimating expectation values of an arbitrary set of Pauli observables given an unknown state. We propose a series of sample-optimal Pauli shadow tomography algorithms using no quantum memory, k-qubit quantum memory, and two-copy measurements, where we show a smooth transition in the sample-memory trade-off. On the other hand, we revisit the prototypical tasks for characterizing the structure of noise in quantum devices: estimating every eigenvalue of Pauli noise channels. We propose a concatenating protocol that can estimate the eigenvalues of a Pauli channel using only logarithmic ancilla qubits and polynomial measurements. In contrast, we prove a tight lower bound that any ancilla-free protocol requires exponentially many measurements, which reveals a sharp transition in the measurement-memory trade-off.

*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*