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).

证明了可以通过 O (n^2) 单比特测量来认证几乎所有 n 比特目标态，包括具有指数电路复杂性的目标态，并通过建立一种新的与随机行走的混合时间相关的技术，将认证与目标态的混合时间相关联。