This paper presents a novel certification procedure for quantum states, demonstrating that almost all $n$-qubit target states can be certified with only $\mathcal{O}(n^2)$ single-qubit measurements. The method, based on a technique that relates certification to the mixing time of a random walk, offers significant advantages over existing protocols that either require deep quantum circuits or exponentially many single-qubit measurements. The certification procedure involves performing single-qubit Pauli measurements on each qubit of the unknown state $\rho$ and outputs an estimate called the *shadow overlap*. The expectation of this shadow overlap is shown to be a good surrogate for the fidelity $\langle\psi|\rho|\psi\rangle$. The relaxation time $\tau$ of a Markov chain induced by the measurement distribution $\pi(x) = |\langle x|\psi\rangle|^2$ is bounded, and the sample complexity of the certification procedure is $\mathcal{O}(\tau^2 / \epsilon^2)$ for generic quantum states and $\mathcal{O}(\tau / \epsilon)$ for more general single-qubit measurements. The paper also discusses applications of this certification procedure, including neural network quantum state tomography, benchmarking quantum devices, and optimizing quantum circuits for state preparation. Numerical experiments with up to 120 qubits demonstrate the effectiveness of the method, showing advantages over existing methods such as cross-entropy benchmarking (XEB).This paper presents a novel certification procedure for quantum states, demonstrating that almost all $n$-qubit target states can be certified with only $\mathcal{O}(n^2)$ single-qubit measurements. The method, based on a technique that relates certification to the mixing time of a random walk, offers significant advantages over existing protocols that either require deep quantum circuits or exponentially many single-qubit measurements. The certification procedure involves performing single-qubit Pauli measurements on each qubit of the unknown state $\rho$ and outputs an estimate called the *shadow overlap*. The expectation of this shadow overlap is shown to be a good surrogate for the fidelity $\langle\psi|\rho|\psi\rangle$. The relaxation time $\tau$ of a Markov chain induced by the measurement distribution $\pi(x) = |\langle x|\psi\rangle|^2$ is bounded, and the sample complexity of the certification procedure is $\mathcal{O}(\tau^2 / \epsilon^2)$ for generic quantum states and $\mathcal{O}(\tau / \epsilon)$ for more general single-qubit measurements. The paper also discusses applications of this certification procedure, including neural network quantum state tomography, benchmarking quantum devices, and optimizing quantum circuits for state preparation. Numerical experiments with up to 120 qubits demonstrate the effectiveness of the method, showing advantages over existing methods such as cross-entropy benchmarking (XEB).