# Entanglement is Necessary for Optimal Quantum Property Testing

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2020.

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

- [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)
- [A Hierarchy for Replica Quantum Advantage](https://mlsanity.com/paper/2111.05874/) (2021)
- [The Complexity of NISQ](https://mlsanity.com/paper/2210.07234/) (2022)
- [Toward Instance-Optimal State Certification With Incoherent Measurements](https://mlsanity.com/paper/2102.13098/) (2021)
- [When Does Adaptivity Help for Quantum State Learning?](https://mlsanity.com/paper/2206.05265/) (2022)
- [Tight Bounds for Quantum State Certification with Incoherent Measurements](https://mlsanity.com/paper/2204.07155/) (2022)
- [Lower Bounds for Learning Quantum States with Single-Copy Measurements](https://mlsanity.com/paper/2207.14438/) (2022)
- [Tight bounds on Pauli channel learning without entanglement](https://mlsanity.com/paper/2309.13461/) (2023)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Transition Role of Entangled Data in Quantum Machine Learning](https://mlsanity.com/paper/2306.03481/) (2023)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [An optimal tradeoff between entanglement and copy complexity for state tomography](https://mlsanity.com/paper/2402.16353/) (2024)
- [Spacetime-Efficient Low-Depth Quantum State Preparation with Applications](https://mlsanity.com/paper/2303.02131/) (2023)
- [Instance-Optimal Quantum State Certification with Entangled Measurements](https://mlsanity.com/paper/2507.06010/) (2025)
- [Efficient learning of bosonic Gaussian unitaries](https://mlsanity.com/paper/2510.05531/) (2025)
- [New Bounds on Quantum Sample Complexity of Measurement Classes](https://mlsanity.com/paper/2408.12683/) (2024)
- [Adaptivity can help exponentially for shadow tomography](https://mlsanity.com/paper/2412.19022/) (2024)
- [Purest Quantum State Identification](https://mlsanity.com/paper/2502.14334/) (2025)
- [Sample-optimal learning of quantum states using gentle measurements](https://mlsanity.com/paper/2505.24587/) (2025)
- [Non-iid hypothesis testing: from classical to quantum](https://mlsanity.com/paper/2510.06147/) (2025)
- [The Sample Complexity of Quantum Entanglement Allocation](https://mlsanity.com/paper/2609.10141/) (2026)

## Abstract (arXiv)

There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity. Unfortunately, they require the use of entangled measurements across many copies of the underlying state and thus remain outside the realm of what is currently experimentally feasible. A natural question is whether one can match the copy complexity of such algorithms using only independent---but possibly adaptively chosen---measurements on individual copies. We answer this in the negative for arguably the most basic quantum testing problem: deciding whether a given d-dimensional quantum state is equal to or ε-far in trace distance from the maximally mixed state. While it is known how to achieve optimal O(d/ε2) copy complexity using entangled measurements, we show that with independent measurements, Omega(d4/3/ε2) is necessary, even if the measurements are chosen adaptively. This resolves a question of Wright. To obtain this lower bound, we develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing, which may be of independent interest.