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).
We provide a geometric classification of single-qubit projective measurements on one-dimensional linear cluster states within a topological framework. Establishing an explicit correspondence between local measurements and surgery operations on an associated link model, we represent the cluster state as a linear Hopf chain. Computational-basis (Z) measurements act as topological severance for bulk qubits and boundary pruning for end qubits. Transverse-basis (X) measurements remove the measured qubit and stratify the remaining state into a superposition of two disjoint but classically correlated segments. In contrast, lateral-basis (Y) measurements preserve a single continuous spliced chain while generating complex phase factors absent from unframed link descriptions. Although the unframed linking structure already distinguishes X- and Y-basis measurement outcomes geometrically, it cannot differentiate the two possible outcomes within a fixed basis. To resolve this ambiguity, we introduce a framed ribbon representation in which quantum phases are encoded as geometric twists, with chiral plus/minus 90 deg twists representing the phases plus/minus i. The resulting framework provides a phase-sensitive, outcome-resolved geometric description of single-shot Pauli measurements on linear cluster states. The twist angles are geometric labels determined by measurement outcomes and associated by-product operators rather than topological invariants, whereas the underlying linking pattern remains a genuine topological datum. The analysis is restricted to single-shot single-qubit Pauli measurements on one-dimensional cluster states; sequential measurements and classical feedforward are left as open problems.