Alice Zheng

Quantum memory is a scarce and costly resource, yet little is known about which learning tasks remain feasible under severe memory constraints. We study the problem of computing global properties of quantum sequences when quantum systems must be measured individually, without storing or jointly processing them. In our setting, a bit string \(x \in \{0,1\}^n\) is encoded into an \(n\)-qubit product state \(\ket{\psi_{x_1}} \otimes \cdots \otimes \ket{\psi_{x_n}}\), and the goal is to infer \(f(x) \in \{0,1\}\) from measurements of this quantum encoding. We consider a simple local strategy, which we call the \emph{greedy strategy}, that applies the same optimal single-system measurement independently to each subsystem and then infers \(f(x)\) from the results. Our main result gives a complete characterization of when the greedy strategy is optimal: it achieves the same maximum success probability as an unrestricted global measurement if and only if the target Boolean function is affine (in all but finitely many cases). For general Boolean functions, we establish a universal performance guarantee, showing that the success probability of the greedy strategy is always at least the square of the optimal global success probability, in direct analogy with the Barnum--Knill bound for the pretty good measurement. These results demonstrate that even under extreme memory constraints, simple local measurement strategies can remain provably competitive for learning global properties of quantum sequences.

Modern quantum devices require high-precision Hamiltonian dynamics, but environmental noise can cause calibrated Hamiltonian parameters to drift over time, necessitating expensive recalibration. Detecting when recalibration is needed is challenging, especially since the very gates required for sophisticated verification protocols may themselves be miscalibrated. While cloud quantum computing services implement heuristic routines for triggering recalibration, the fundamental limits of optimal recalibration have yet to be illuminated. Here we study the recalibration problem by developing efficient Hamiltonian certification and \changepoint{} detection protocols in the \emph{autonomous} setting. In this setting we use only single-qubit gates and measurements and do not use any ancilla qubits, making the protocols robust to the calibration issues for multi-qubit operations they aim to detect. For an unknown $n$-qubit $M$-sparse Hamiltonian $H$, our certification protocol distinguishes whether $\|H - H_0\|_F \geq \epsilon$ or $\|H - H_0\|_F \leq O(\epsilon/\sqrt{n})$ with sample complexity $\mathcal{O}(nM^2\ln(1/\delta)/\epsilon^2)$ and total evolution time $\mathcal{O}(nM\ln(1/\delta)/\epsilon^2)$, where $H_0$ is the target Hamiltonian and $\delta$ bounds the failure probability. The protocol achieves this by evolving random stabilizer product states and performing adaptive single-qubit measurements based on a classically simulable hypothesis state. Extending this to continuous monitoring, we develop an online \changepoint{} detection algorithm using the CUSUM procedure that achieves a detection delay bound of $\mathcal{O}(nM\ln(M\falsealarm{T})/\epsilon^2)$, matching the known asymptotically optimal scaling with respect to false alarm run length $\falsealarm{T}$. Our approach enables quantum devices to autonomously monitor their own calibration status without requiring ancillary systems, entangling operations, or a trusted reference device, and provides maximum-likelihood estimates of \changepoint{} locations to identify and rerun affected computations, offering a practical solution for robust quantum computing with contemporary noisy devices.