Certifying quantum states with few single-qubit measurements is a key challenge in quantum information science. This paper presents a method to certify that an n-qubit state ρ is close to a target state |ψ⟩ using only O(n²) single-qubit measurements. The method is based on a new technique that relates certification to the mixing time of a random walk. The protocol has applications in benchmarking quantum systems, optimizing quantum circuits, and learning and verifying quantum states using single-qubit measurements. The results show that such verified representations can efficiently predict highly non-local properties of ρ that would otherwise require an exponential number of measurements. The method is demonstrated with numerical experiments on up to 120 qubits, showing advantages over existing methods like cross-entropy benchmarking (XEB). The certification procedure involves performing single-qubit Pauli measurements on each qubit of ρ and using the results to estimate the shadow overlap, a surrogate for the fidelity between ρ and |ψ⟩. The shadow overlap is shown to be a good approximation of the fidelity for states with polynomial relaxation time. The method is efficient and computationally feasible, as it requires only single-qubit measurements and can be applied to a wide range of quantum states, including highly entangled states with exponential circuit complexity. The paper also discusses applications of the method in quantum state tomography, benchmarking quantum devices, and optimizing quantum circuits for state preparation. The results show that the shadow overlap can be used to efficiently certify the fidelity between a lab state and a target state, and that it can be used to predict non-local properties of the lab state. The method is shown to be effective for a wide range of quantum states, including Haar random states, quantum phase states, and ground states of gapped Hamiltonians. The paper concludes with a discussion of open questions and future directions for research in this area.Certifying quantum states with few single-qubit measurements is a key challenge in quantum information science. This paper presents a method to certify that an n-qubit state ρ is close to a target state |ψ⟩ using only O(n²) single-qubit measurements. The method is based on a new technique that relates certification to the mixing time of a random walk. The protocol has applications in benchmarking quantum systems, optimizing quantum circuits, and learning and verifying quantum states using single-qubit measurements. The results show that such verified representations can efficiently predict highly non-local properties of ρ that would otherwise require an exponential number of measurements. The method is demonstrated with numerical experiments on up to 120 qubits, showing advantages over existing methods like cross-entropy benchmarking (XEB). The certification procedure involves performing single-qubit Pauli measurements on each qubit of ρ and using the results to estimate the shadow overlap, a surrogate for the fidelity between ρ and |ψ⟩. The shadow overlap is shown to be a good approximation of the fidelity for states with polynomial relaxation time. The method is efficient and computationally feasible, as it requires only single-qubit measurements and can be applied to a wide range of quantum states, including highly entangled states with exponential circuit complexity. The paper also discusses applications of the method in quantum state tomography, benchmarking quantum devices, and optimizing quantum circuits for state preparation. The results show that the shadow overlap can be used to efficiently certify the fidelity between a lab state and a target state, and that it can be used to predict non-local properties of the lab state. The method is shown to be effective for a wide range of quantum states, including Haar random states, quantum phase states, and ground states of gapped Hamiltonians. The paper concludes with a discussion of open questions and future directions for research in this area.