# Certifying almost all quantum states with few single-qubit measurements

arXiv: https://arxiv.org/abs/2404.07281 · HTML: https://mlsanity.com/paper/2404.07281/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 62 references that are in the map.
- First posted on arXiv 10 Apr 2024.

## Builds on (most cited first, 18 of 18)

- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Ab-Initio Solution of the Many-Electron Schr"odinger Equation with Deep Neural Networks](https://mlsanity.com/paper/1909.02487/) (2019)
- [Deep autoregressive models for the efficient variational simulation of many-body quantum systems](https://mlsanity.com/paper/1902.04057/) (2019)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Neural tensor contractions and the expressive power of deep neural quantum states](https://mlsanity.com/paper/2103.10293/) (2021)
- [Learning shallow quantum circuits](https://mlsanity.com/paper/2401.10095/) (2024)
- [From Tensor Network Quantum States to Tensorial Recurrent Neural Networks](https://mlsanity.com/paper/2206.12363/) (2022)
- [Quantum state certification](https://mlsanity.com/paper/1708.06002/) (2017)
- [Toward Instance-Optimal State Certification With Incoherent Measurements](https://mlsanity.com/paper/2102.13098/) (2021)
- [The power and limitations of learning quantum dynamics incoherently](https://mlsanity.com/paper/2303.12834/) (2023)
- [Tight Bounds for Quantum State Certification with Incoherent Measurements](https://mlsanity.com/paper/2204.07155/) (2022)
- [(Pseudo) Random Quantum States with Binary Phase](https://mlsanity.com/paper/1906.10611/) (2019)
- [Fast and robust quantum state tomography from few basis measurements](https://mlsanity.com/paper/2009.08216/) (2020)
- [Empirical Sample Complexity of Neural Network Mixed State Reconstruction](https://mlsanity.com/paper/2307.01840/) (2023)
- [Uniform multicommodity flow in the hypercube with random edge capacities](https://mlsanity.com/paper/1406.4433/) (2014)

## Built on by (most cited first, 7 of 7)

- [When can classical neural networks represent quantum states?](https://mlsanity.com/paper/2410.23152/) (2024)
- [Learning topological states from randomized measurements using variational tensor network tomography](https://mlsanity.com/paper/2406.00193/) (2024)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Learning to Classify Quantum Phases of Matter with a Few Measurements](https://mlsanity.com/paper/2409.05188/) (2024)
- [Instance-Optimal Quantum State Certification with Entangled Measurements](https://mlsanity.com/paper/2507.06010/) (2025)
- [Hybrid Classical-Quantum architecture for vectorised image classification of hand-written sketches](https://mlsanity.com/paper/2407.06416/) (2024)
- [Non-iid hypothesis testing: from classical to quantum](https://mlsanity.com/paper/2510.06147/) (2025)

## Abstract (arXiv)

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