# A Hierarchy for Replica Quantum Advantage

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 25 references that are in the map.
- First posted on arXiv 10 Nov 2021.

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

- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [Toward Instance-Optimal State Certification With Incoherent Measurements](https://mlsanity.com/paper/2102.13098/) (2021)

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

- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [The Complexity of NISQ](https://mlsanity.com/paper/2210.07234/) (2022)
- [Foundations for learning from noisy quantum experiments](https://mlsanity.com/paper/2204.13691/) (2022)
- [When Does Adaptivity Help for Quantum State Learning?](https://mlsanity.com/paper/2206.05265/) (2022)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [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)
- [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)
- [Learning topological states from randomized measurements using variational tensor network tomography](https://mlsanity.com/paper/2406.00193/) (2024)
- [A Parameter-Efficient Quantum Anomaly Detection Method on a Superconducting Quantum Processor](https://mlsanity.com/paper/2412.16867/) (2024)
- [Instance-Optimal Quantum State Certification with Entangled Measurements](https://mlsanity.com/paper/2507.06010/) (2025)
- [Non-iid hypothesis testing: from classical to quantum](https://mlsanity.com/paper/2510.06147/) (2025)

## Abstract (arXiv)

We prove that given the ability to make entangled measurements on at most k replicas of an n-qubit state ρ simultaneously, there is a property of ρ which requires at least order 2n measurements to learn. However, the same property only requires one measurement to learn if we can make an entangled measurement over a number of replicas polynomial in k, n. Because the above holds for each positive integer k, we obtain a hierarchy of tasks necessitating progressively more replicas to be performed efficiently. We introduce a powerful proof technique to establish our results, and also use this to provide new bounds for testing the mixedness of a quantum state.