Distributed inner product estimation with limited quantum communication

Abstract

We consider the task of distributed inner product estimation when allowed limited quantum communication. Here, Alice and Bob are given $k$ copies of an unknown $n$-qubit quantum states $|\ddot{I}ˆ⟩,|\ddot{I}•⟩$ respectively. They are allowed to communicate $q$ qubits and unlimited classical communication, and their goal is to estimate $|⟨\ddot{I}ˆ|\ddot{I}•⟩{|}^2$ up to constant accuracy. We show that $k=\hat{I}˜(\sqrt{2^{n-q}})$ copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when $q=0$). Additionally, we consider estimating $|⟨\ddot{I}ˆ|M|\ddot{I}•⟩{|}^2$, for arbitrary Hermitian $M$. For this task we show that certain norms on $M$ characterize the sample complexity of estimating $|⟨\ddot{I}ˆ|M|\ddot{I}•⟩{|}^2$ when using only classical~communication.

26 pages, 2 figures