Few Single-Qubit Measurements Suffice to Certify Any Quantum State

A fundamental task in quantum information science is state certification: testing whether a lab-prepared $n$-qubit state is close to a given hypothesis state. In this work, we show that every pure hypothesis state can be certified using only $O(n^2)$ single-qubit measurements applied to $O(n)$ copies of the lab state. Prior to our work, it was not known whether even subexponentially many single-qubit measurements could suffice to certify arbitrary states. This resolves the main open question of Huang, Preskill, and Soleimanifar (FOCS 2024, QIP 2024). Our algorithm also showcases the power of adaptive measurements: within each copy of the lab state, previous measurement outcomes dictate how subsequent qubit measurements are made. We show that the adaptivity is necessary, by proving an exponential lower bound on the number of copies needed for any nonadaptive single-qubit measurement algorithm.