FOCS Conference 2024 Conference Paper
Certifying Almost All Quantum States with Few Single-Qubit Measurements
- Hsin-Yuan Huang
- John Preskill
- Mehdi Soleimanifar
A fundamental challenge in quantum information science is certifying that an n-qubit state $\rho$ prepared in the lab closely matches a target state $\vert \psi\rangle$. 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 $\mathrm{O}(n^{2})$ 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 $\rho$ that would otherwise require an exponential number of measurements.