# Testing classical properties from quantum data

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 125 references that are in the map.
- First posted on arXiv 19 Nov 2024.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Distributional property testing in a quantum world](https://mlsanity.com/paper/1902.00814/) (2019)
- [Improved Stabilizer Estimation via Bell Difference Sampling](https://mlsanity.com/paper/2304.13915/) (2023)
- [(Pseudo) Random Quantum States with Binary Phase](https://mlsanity.com/paper/1906.10611/) (2019)
- [Optimal algorithms for learning quantum phase states](https://mlsanity.com/paper/2208.07851/) (2022)
- [Tight bounds on Pauli channel learning without entanglement](https://mlsanity.com/paper/2309.13461/) (2023)
- [Efficient Pauli channel estimation with logarithmic quantum memory](https://mlsanity.com/paper/2309.14326/) (2023)
- [Hamiltonian Property Testing](https://mlsanity.com/paper/2403.02968/) (2024)
- [VC Dimension and Distribution-Free Sample-Based Testing](https://mlsanity.com/paper/2012.03923/) (2020)
- [Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation](https://mlsanity.com/paper/2408.06967/) (2024)
- [Testing and learning structured quantum Hamiltonians](https://mlsanity.com/paper/2411.00082/) (2024)
- [Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions](https://mlsanity.com/paper/2310.12375/) (2023)
- [Simple constructions of linear-depth t-designs and pseudorandom unitaries](https://mlsanity.com/paper/2404.12647/) (2024)
- [How to Construct Random Unitaries](https://mlsanity.com/paper/2410.10116/) (2024)
- [Efficient unitary designs and pseudorandom unitaries from permutations](https://mlsanity.com/paper/2404.16751/) (2024)
- [Single-copy stabilizer testing](https://mlsanity.com/paper/2410.07986/) (2024)
- [A note on polynomial-time tolerant testing stabilizer states](https://mlsanity.com/paper/2410.22220/) (2024)
- [On active and passive testing](https://mlsanity.com/paper/1307.7364/) (2013)
- [Quantum Algorithm for Monotonicity Testing on the Hypercube](https://mlsanity.com/paper/1503.02868/) (2015)
- [A Characterization of Constant-Sample Testable Properties](https://mlsanity.com/paper/1612.06016/) (2016)
- [Testing matrix product states](https://mlsanity.com/paper/2201.01824/) (2022)
- [Pseudorandomness from Subset States](https://mlsanity.com/paper/2312.09206/) (2023)
- [Pseudorandom and Pseudoentangled States from Subset States](https://mlsanity.com/paper/2312.15285/) (2023)
- [A basic lower bound for property testing](https://mlsanity.com/paper/2403.04999/) (2024)

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

- [Quantum advantage for learning shallow neural networks with natural data distributions](https://mlsanity.com/paper/2503.20879/) (2025)
- [Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography](https://mlsanity.com/paper/2609.04165/) (2026)

## Abstract (arXiv)

Properties of Boolean functions can often be tested much faster than the functions can be learned. However, this advantage usually disappears when testers are limited to random samples of a function f--a natural setting for data science--rather than queries. In this work we initiate the study of a quantum version of this "data science scenario": quantum algorithms that test properties of f solely from quantum data in the form of copies of the function state |frangle propto sumx|x,f(x)rangle. bullet New tests. For three well-established properties--monotonicity, symmetry, and triangle-freeness--we show that the speedup lost when restricting classical testers to sampled data can be recovered by quantum algorithms operating solely from quantum data. bullet Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and we show that this necessary. In particular, there is no constant-complexity tester for symmetry relying solely on Fourier sampling and random classical samples. bullet Classical queries vs. quantum data. We exhibit a testing problem that can be solved from O(1) classical queries but that requires Omega(2n/2) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. bullet Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of Goldreich et al. (2000) and Black (2023), which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.