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).
A central task in quantum information science is state certification: testing whether an unknown state is
ε1-close to a fixed target state, or
ε2-far. Recent work has shown that surprisingly simple measurement protocols--comprising only single-qubit measurements--suffice to certify arbitrary
n-qubit states [Huang, Preskill, Soleimanifar '25; Gupta, He, O'Donnell '25]. However, these certification protocols are not robust: rather than allowing constant
ε1, they can only positively certify states within
ε1=O(1/n) trace distance of the target. In many experimental settings, the appropriate error tolerance is constant as the system size grows, so this lack of robustness renders existing tests inapplicable at scale, no matter how many times the test is repeated.
Here we present robust certification protocols based on few-qubit measurements that apply to all but a
O(2−n)-fraction of pure target states. Our first protocol achieves constant robustness, i.e.
ε1=Θ(1), using a single
O(logn)-qubit measurement along with single-qubit measurements in the
Z or
X basis on the other qubits. As a corollary of its robustness, this protocol also achieves constant (in
n) copy complexity, which is optimal. Our second protocol uses exclusively single-qubit measurements and is nearly robust:
ε1=Ω(1/logn). Our tests are based on a new uncertainty principle for conditional fidelities, which may be of independent interest.
A fundamental challenge in quantum information science is certifying that an n-qubit state
ρprepared in the lab closely matches a target state
∣ψ⟩. Previous approaches to this problem often require deep quantum circuits, exponentially many single-qubit measurements, or are limited to specific state families. In this work, we introduce a new method that leverages a connection between state certification and the mixing time of a random walk, allowing almost all n-qubit target states, including those with exponential circuit complexity, to be certified with only
O(n2)single-qubit measurements. Our protocol is broadly compatible with various experimental platforms and has applications in benchmarking quantum systems, optimizing quantum circuits, and efficiently learning and verifying representations of quantum states—such as neural networks and tensor networks—using only single-qubit measurements. Moreover, these verified representations enable the efficient prediction of highly non-local properties of
ρthat would otherwise require an exponential number of measurements.
Certifying that an n-qubit state synthesized in the lab is close to the target state is a fundamental task in quantum information science. However, existing rigorous protocols either require deep quantum circuits or exponentially many single-qubit measurements. In this work, we prove that almost all n-qubit target states, including those with exponential circuit complexity, can be certified from only O(n^2) single-qubit measurements. This result is established by a new technique that relates certification to the mixing time of a random walk. Our protocol has applications for benchmarking quantum systems, for optimizing quantum circuits to generate a desired target state, and for learning and verifying neural networks, tensor networks, and various other representations of quantum states using only single-qubit measurements. We show that such verified representations can be used to efficiently predict highly non-local properties that would otherwise require an exponential number of measurements. We demonstrate these applications in numerical experiments with up to 120 qubits, and observe advantage over existing methods such as cross-entropy benchmarking (XEB).