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.
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.
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.
As quantum processors are deployed across different hardware platforms and remote cloud laboratories, a basic physical question is whether two black-box devices realize the same quantum process, without relying on a trusted classical description. We formulate the core primitive for this comparison task as \emph{distributed similarity estimation of quantum channels} (DSEC): given local access to two unknown channels, estimate the normalized inner product of their Choi states. We prove that the optimal query complexity of DSEC is Θ(max{d/ε,1/ε2}), where d is the channel dimension and ε is the additive error. This matching query complexity is nontrivial: channel learning permits input choices and interleaving known operations, which makes channel learning strictly harder than state learning. We first prove an information-theoretic lower bound with this scaling, which holds even in the \emph{strongest setting}, allowing adaptive strategies, multiple rounds of classical communication, and coherent access with arbitrary ancillas. We then give a matching upper bound in the \emph{weakest setting}, namely non-adaptive and ancilla-free incoherent access, via a randomized measurement algorithm achieving this bound. Finally, we show that our algorithm achieves a quadratic improvement over classical shadow baselines. Our results provide theoretically optimal and practical algorithms for quantum device benchmarking and distributed quantum learning.
Optimal single-copy estimation of quantum state moments: why Tr(ρ3) and Tr(ρ4) are equally hard
Estimating nonlinear properties of an unknown quantum state with restrictive experimental accessibility is a fundamental problem in quantum learning. We study the sample complexity of estimating the state moments Tr(ρt), allowing arbitrary adaptive single-copy measurements. While purity estimation has optimal sample complexity Θ(d) at constant additive error, the optimal dimension dependence for higher moments has remained unclear. We resolve this question for every fixed integer t≥2: for any sufficiently small constant additive error, the optimal sample complexity is Θ(d1+⌈log2t⌉⌈log2t⌉) with constant success probability. The complexity thus follows a dyadic hierarchy: for each integer h≥1, all moment orders 2h−1<t≤2h share the same exponent. In particular, the third and fourth moments both require Θ(d2/3) copies. Our results also apply to multistate overlaps, weighted and partial-transpose moments, fixed-rank spectrum estimation, and distributed estimation of nonlinear quantities. We also establish an Ω(d1−1/t) lower bound for arbitrary nonadaptive single-copy protocols, matching the known upper bound and demonstrating an advantage from adaptivity for every t≥4. Our upper bound uses adaptive state filtering to reduce higher-order moment estimation to lower-order moment estimation in a smaller state space. For the lower bound, we directly compare moment-matched ensembles through a smooth interpolation, bypassing the maximally mixed state as an intermediate hypothesis and yielding matching bounds beyond d.
Cross-platform verification is the task of comparing the output states produced by different physical platforms using solely local quantum operations and classical communication. While protocols have previously been suggested for this task, their exponential sample complexity renders them impractical even for intermediate-scale quantum systems. In this work, we propose a novel protocol for this task based on , a subroutine that generates Paulis distributed according to their weight in the expansion of a quantum state in the Pauli basis. We show that our protocols for both Pauli sampling and cross-platform verification are efficient for pure states with low magic and entanglement [i.e., of the order O ( log n ) ]. Conversely, we show superpolynomial lower bounds on the complexity of both tasks for states with ω ( log ( n ) ) magic and entanglement. Interestingly, when considering states with real amplitudes, the requirements of our protocol for cross-platform verification can be significantly weakened.