# Distributional property testing in a quantum world

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2019.

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

- [Near-Optimal Quantum Algorithms for Multivariate Mean Estimation](https://mlsanity.com/paper/2111.09787/) (2021)
- [Provably Efficient Exploration in Quantum Reinforcement Learning with Logarithmic Worst-Case Regret](https://mlsanity.com/paper/2302.10796/) (2023)
- [Quantum Neural Estimation of Entropies](https://mlsanity.com/paper/2307.01171/) (2023)
- [Quantum Algorithms and Lower Bounds for Finite-Sum Optimization](https://mlsanity.com/paper/2406.03006/) (2024)
- [Wavefunction Flows: Efficient Quantum Simulation of Continuous Flow Models](https://mlsanity.com/paper/2510.08462/) (2025)
- [Performance Guarantees for Quantum Neural Estimation of Entropies](https://mlsanity.com/paper/2511.19289/) (2025)
- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)
- [Estimating quantum relative entropies on quantum computers](https://mlsanity.com/paper/2501.07292/) (2025)
- [Quantum enhanced rare event discovery and sampling](https://mlsanity.com/paper/2606.06316/) (2026)
- [A Quantum/Classical Example Oracle Separation for Making Things Up](https://mlsanity.com/paper/2608.11648/) (2026)
- [Characterizing Privacy Risks of Quantum Machine Learning with Emergent Quantum-Native Access](https://mlsanity.com/paper/2609.05702/) (2026)

## Abstract (arXiv)

A fundamental problem in statistics and learning theory is to test properties of distributions. We show that quantum computers can solve such problems with significant speed-ups. In particular, we give fast quantum algorithms for testing closeness between unknown distributions, testing independence between two distributions, and estimating the Shannon / von Neumann entropy of distributions. The distributions can be either classical or quantum, however our quantum algorithms require coherent quantum access to a process preparing the samples. Our results build on the recent technique of quantum singular value transformation, combined with more standard tricks such as divide-and-conquer. The presented approach is a natural fit for distributional property testing both in the classical and the quantum case, demonstrating the first speed-ups for testing properties of density operators that can be accessed coherently rather than only via sampling; for classical distributions our algorithms significantly improve the precision dependence of some earlier results.