On the sample complexity of purity and inner product estimation

• DOI: 10.48550/arxiv.2410.12712
• Publication Date: 2024-01-01
• Authors: Gong, Weiyuan; Haferkamp, Jonas; Ye, Qi; Zhang, Zhihan
• Keywords: FOS: Computer and information sciences; Quantum Physics; Computer Science - Machine Learning; Computer Science - Information Theory; Information Theory (cs.IT); Computer Science - Data Structures and Algorithms; FOS: Physical sciences; Data Structures and Algorithms (cs.DS); Quantum Physics (quant-ph); Machine Learning (cs.LG)

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(median\{1/ε^2,2^{n/2}/ε,2^{n-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 $Ω(median\{1/ε^2,2^{n/2}/\sqrtε,2^{n-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 $Ω(\max\{1/ε^2,2^{n/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.<br/>33 pages, 1 figure<br/>