In this work, we consider the fundamental task of distributed inner product estimation when allowed limited communication. Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩,|ϕ⟩ respectively, are allowed to send q qubits to one another, and the task is to estimate |⟨ψ|ϕ⟩|² up to constant additive error. We show that k = Θ(√{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 also consider the task when the goal of the players is to estimate |⟨ψ|M|ϕ⟩|², for arbitrary Hermitian M. For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M|ϕ⟩|² when using only classical communication.
In this work, we consider the fundamental task of distributed inner product estimation when allowed limited communication. Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩,|ϕ⟩ respectively, are allowed to send q qubits to one another, and the task is to estimate |⟨ψ|ϕ⟩|² up to constant additive error. We show that k = Θ(√{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 also consider the task when the goal of the players is to estimate |⟨ψ|M|ϕ⟩|², for arbitrary Hermitian M. For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M|ϕ⟩|² when using only classical communication.
In this work, we consider the fundamental task of distributed inner product estimation when allowed limited communication. Suppose Alice and Bob are given k copies of an unknown n-qubit quantum state |ψ⟩,|ϕ⟩ respectively, are allowed to send q qubits to one another, and the task is to estimate |⟨ψ|ϕ⟩|² up to constant additive error. We show that k = Θ(√{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 also consider the task when the goal of the players is to estimate |⟨ψ|M|ϕ⟩|², for arbitrary Hermitian M. For this task we show that certain norms on M determine the sample complexity of estimating |⟨ψ|M|ϕ⟩|² when using only classical communication.
We study the sample complexity of the prototypical tasks and . The former has been a key subroutine for experimental benchmarking and entropy estimation, while the latter is a core task for cross-platform validation that compares the unknown quantum states produced by different physical platforms. 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 the unknown quantum states ρ and σ using classical communication and restricted quantum communication. We propose a protocol that solves quantum inner product estimation with k -qubit 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 sample complexity. We also prove that arbitrary protocols with k -qubit quantum memory that estimate purity to error ɛ require Ω ( median { 1 / ɛ 2 , 2 n / 2 / ɛ , 2 n − k / ɛ 2 } ) copies of ρ . This indicates the same sample complexity lower bound for quantum inner product estimation with k -qubit quantum communication and classical communication, and unentangled local measurements. We further improve the sample complexity lower bound for any purity estimation protocols using an identical single-copy projection-valued measurement. Last, we investigate a decisional variant of quantum distributed inner product estimation without quantum communication for mixed states and provide a sample complexity lower bound.
As small quantum computers are becoming available on different physical platforms, a benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. This task is fundamentally distributed, as no quantum communication can be performed between the two physical platforms due to hardware constraints, which prohibits a joint SWAP test. In this paper we settle the sample complexity of this task across all measurement and communication settings. The essence of the task, which we call distributed quantum inner product estimation, involves two players Alice and Bob who have k copies of unknown states ρ,σ (acting on ℂd) respectively. Their goal is to estimate Tr(ρσ) up to additive error ε∈(0,1), using local quantum operations and classical communication. In the weakest setting where only non-adaptive single-copy measurements and simultaneous message passing are allowed, we show that k=O(max{1/ε2,√d/ε}) copies suffice. This achieves a savings compared to full tomography which takes Ω(d3) copies with single-copy measurements. Surprisingly, we also show that the sample complexity must be at least Ω(max{1/ε2,√d/ε}), even in the strongest setting where adaptive multi-copy measurements and arbitrary rounds of communication are allowed. This shows that the success achieved by shadow tomography, for sample-efficiently learning the properties of a single system, cannot be generalized to the distributed setting. Furthermore, the fact that the sample complexity remains the same with single and multi-copy measurements contrasts with single system quantum property testing, which often demonstrate exponential separations in sample complexity with single and multi-copy measurements.
We introduce a framework for distributed quantum inference under communication constraints. In our model, m distributed nodes each receive one copy of an unknown d-dimensional quantum state ρ, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of ρ. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT2019], by allowing quantum resources such as quantum communication and shared entanglement. Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state σ, decide whether ρ=σ or ∥ρ−σ∥1≥ε. Additionally, we focus on the case of limited quantum communication between distributed nodes and the central node. We show that when each communication channel is limited to only nq≤logd qubits, then the sample complexity of distributed state certification is O(2nqε2d2) when public randomness is available to all nodes. Moreover, under the assumption that the channels used by the distributed nodes are mixedness-preserving, we prove a matching lower bound. We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an Ω(4nqε2d3) lower bound in the private-coin setting under the same assumption as above. Our lower bounds leverage a recently introduced quantum analogue of the celebrated Ingster-Suslina method and generalize arguments from the classical setting. Together, our work provides the first characterization of distributed quantum state certification in the regime of limited quantum communication and establishes a general framework for distributed quantum inference with communication constraints.
We introduce a framework for distributed quantum inference under communication constraints. In our model, m distributed nodes each receive one copy of an unknown d-dimensional quantum state ρ, before communicating via a constrained one-way communication channel with a central node, which aims to infer some property of ρ. This framework generalizes the classical distributed inference framework introduced by Acharya, Canonne, and Tyagi [COLT 2019], by allowing quantum resources such as quantum communication and shared entanglement.
Within this setting, we focus on the fundamental problem of quantum state certification: Given a complete description of some state σ, decide whether ρ=σ or ∥ρ−σ∥1≥ε. Additionally, we focus on the case of limited communication between distributed nodes and the central node: we assume each communication channel is limited to only nc bits and nq qubits with nc+nq≤logd. When all nodes can make use of a shared source of randomness, we show that the copy complexity of distributed state certification is Θ(2nq2nc/2ε2d2). We further demonstrate that shared randomness is necessary to achieve the above complexity, by proving an Ω(4nq2ncε2d3) lower bound in the private-coin setting. Moreover, we develop a private-coin algorithm that matches this bound up to a logd factor, showing this complexity is near-optimal. Together, our work establishes a general framework for distributed quantum inference with communication constraints and characterizes the complexity of distributed state certification with limited communication.
We study the question of how much classical communication is needed when Alice is given a classical description of a quantum state ∣ψ⟩ for Bob to recover any expectation value ⟨ψ∣M∣ψ⟩ given an observable M with M Hermitian and ∣∣M∣∣op≤1. This task, whose study was initiated by Raz (ACM 1999) and more recently investigated by Gosset and Smolin (TQC 2019), can be thought of as a fully classical version of the pure state case of the well-known classical shadows problem in quantum learning theory. We show how the hardness of these two seemingly distinct problems are connected. We first consider the relative error version of the communication question and prove a lower bound of Ω(2nε−2) on the one-way randomized classical communication, improving upon an additive error lower bound of Ω(2n) as shown by Gosset and Smolin. Notably, we show that this lower bound holds not only for the set of all observables but also when restricted to just the class of Pauli observables. This fact implies a Ω(2n) versus O(poly(n)) separation in the compression size between the relative and additive error settings for non-adaptive Pauli classical shadows with classical memory. Extending this framework, we prove randomized communication lower bounds for other relative error one-way classical communication tasks: an Ω(2nε−2) lower bound when instead Alice is given an observable and Bob is given a quantum state and they are asked to estimate the expectation value, an Ω(nε−2) lower bound when restricted to Paulis, and an Ω(2nε−2) lower bound when Alice and Bob are both given quantum states and asked to estimate the inner product.