# On the sample complexity of purity and inner product estimation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 71 references that are in the map.
- First posted on arXiv 16 Oct 2024.

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

- [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)
- [Provably efficient machine learning for quantum many-body problems](https://mlsanity.com/paper/2106.12627/) (2021)
- [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)
- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Entanglement is Necessary for Optimal Quantum Property Testing](https://mlsanity.com/paper/2004.07869/) (2020)
- [A Hierarchy for Replica Quantum Advantage](https://mlsanity.com/paper/2111.05874/) (2021)
- [Quantum state certification](https://mlsanity.com/paper/1708.06002/) (2017)
- [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)
- [Multimodal deep representation learning for quantum cross-platform verification](https://mlsanity.com/paper/2311.03713/) (2023)
- [Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates](https://mlsanity.com/paper/2305.13409/) (2023)
- [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)
- [Lower Bounds on Learning Pauli Channels with Individual Measurements](https://mlsanity.com/paper/2301.09192/) (2023)
- [Quantum Channel Certification with Incoherent Strategies](https://mlsanity.com/paper/2303.01188/) (2023)
- [Optimal high-precision shadow estimation](https://mlsanity.com/paper/2407.13874/) (2024)

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

- [Instance-Optimal Quantum State Certification with Entangled Measurements](https://mlsanity.com/paper/2507.06010/) (2025)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [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)
- [Optimal Stabilizer Testing and Learning with Limited Quantum Memory](https://mlsanity.com/paper/2607.02444/) (2026)

## Abstract (arXiv)

We study the sample complexity of the prototypical tasks quantum purity estimation and quantum inner product estimation. In purity estimation, we are to estimate tr(ρ2) of an unknown quantum state ρ to additive error ε. Meanwhile, for quantum inner product estimation, Alice and Bob are to estimate tr(ρσ) to additive error ε given copies of unknown quantum state ρ and σ using classical communication and restricted quantum communication. In this paper, we show a strong connection between the sample complexity of purity estimation with bounded quantum memory and inner product estimation with bounded quantum communication and unentangled measurements. We propose a protocol that solves quantum inner product estimation with k-qubit one-way quantum communication and unentangled local measurements using O(median1/ε2,2n/2/ε,2n-k/ε2) copies of ρ and σ. Our protocol can be modified to estimate the purity of an unknown quantum state ρ using k-qubit quantum memory with the same complexity. We prove that arbitrary protocols with k-qubit quantum memory that estimate purity to error ε require Omega(median1/ε2,2n/2/√ε,2n-k/ε2) copies of ρ. This indicates the same lower bound for quantum inner product estimation with one-way k-qubit quantum communication and classical communication, and unentangled local measurements. For purity estimation, we further improve the lower bound to Omega(max1/ε2,2n/2/ε) for any protocols using an identical single-copy projection-valued measurement. Additionally, we investigate a decisional variant of quantum distributed inner product estimation without quantum communication for mixed state and provide a lower bound on the sample complexity.