Worst-Case Sample Complexity Bounds for Distributed Inner Product Estimation with Local Randomized Measurements
Zhenyuan Huang, Kun Wang, Ping Xu · 2026
Read Worst-Case Sample Complexity Bounds for Distributed Inner Product Estimation with Local Randomized Measurements by Zhenyuan Huang, Kun Wang, Ping Xu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14256.txt.
Introduction
Huang, Wang and Xu study inner product estimation across sites for n-qubit states with local random measurements. Minimax kernel optimization reduces to one unbiased Hamming kernel. Under Clifford sampling, a sharp fourth-moment bound yields worst-case complexity near the square root of 4.5 to the n, attained by stabilizer states. Under Haar sampling, a twirling identity sets its fourth moment against the Clifford fourth, giving the same bound, though lossy. This motivates a conjectured sharper Haar scaling near the square root of 3.6 to the n, attained by products.
Catalog record
| CREATOR | Zhenyuan Huang, Kun Wang, Ping Xu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 135418 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14256
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Worst-Case Sample Complexity Bounds for Distributed Inner Product Estimation with Local Randomized Measurements Zhenyuan Huang, Kun Wang, Ping Xu Abstract We study distributed inner product estimation for n n -qubit states using local randomized measurements, for which rigorous worst-case guarantees are less understood. We first reduce the minimax kernel optimization to Hamming-distance kernels. Within this class, unbiasedness fixes a unique kernel. For this kernel under local Clifford sampling, we prove a sharp fourth-moment bound using the single-qubit Clifford commutant. This yields worst-case sample complexity 𝒪 ( 4.5 n ) \mathcal{O}(\sqrt{4.5^{n}}) , attained by identical pure product stabilizer states. For the same kernel under local Haar sampling, we prove a local twirling identity that compares its fourth moment with the Clifford fourth moment. This gives the same rigorous upper bound as in the Clifford case, but the comparison is lossy. This motivates the conjectured sharper Haar scaling 𝒪 ( 3.6 n ) \mathcal{O}(\sqrt{3.6^{n}}) attained by product states, and verify it for several important classes of states. We also show that independent single-qubit Pauli shadows have worst-case scaling 𝒪 ( 7.5 n ) \mathcal{O}(\sqrt{7.5^{n}}) for large n n . I Introduction Distributed inner product estimation (DIPE) 8 asks two remote parties, given copies of unknown n -qubit states \rho and \sigma , to estimate the Hilbert–Schmidt inner product \tr\left[\rho\sigma\right] using only local operations and classical communication (LOCC). This task lies at the core of cross-platform verification, distributed benchmarking, and certification of quantum devices prepared on separate platforms 6 ; 13 ; 14 , and has motivated extensive theoretical and experimental work 21 ; 15 ; 19 ; 5 ; 20 ; 10 ; 9 ; 2 ; 18 . The optimal sample complexity of DIPE was established in 1 , where it is achieved by a protocol based on global randomized measurements 7 . The problem addressed in this work is to establish rigorous worst-case sample complexity bounds for experimentally feasible DIPE protocols based on local randomized measurements (LRM) . LRM is a practically significant variant of the randomized measurement toolbox 7 : one samples an n -qubit unitary U=\bigotimes_{\ell=1}^{n}U_{\ell} in product form from single-qubit ensembles and then performs computational basis measurements 8 ; 12 . This differs significantly from global randomized measurements, where one samples a single n -qubit unitary, which may be highly entangling across the full system. LRM is therefore the experimentally favorable setting for distributed architectures: it is compatible with local control and avoids the need for global random circuits across the full system 7 ; 11 ; 4 . Despite this practical appeal, the theoretical picture remains incomplete. Elben et al. 8 proposed the standard local Haar protocol, and Zhu et al. 21 experimentally validated it, but neither work provides a sample complexity analysis. Zheng et al. 19 obtained average-case and state-dependent sample complexity bounds for structured random circuits and related ensembles, while Wu et al. 17 proved a loose upper bound \mathcal{O}(\sqrt{6^{n}}) . These results do not determine the optimal post-processing kernel under worst-case variance, nor do they identify the tight worst-case sample complexity of DIPE with LRM. This gap substantially limits the theoretical understanding of DIPE with LRM and, in turn, impedes its reliable practical use. In this work, we address these gaps in three steps. First, we identify the unique unbiased Hamming-distance kernel selected by the worst-case symmetry reduction. Then, we derive worst-case guarantees for local Clifford and Haar sampling based on this unique kernel. Third, we compare these shared-randomness protocols with independent single-qubit Pauli shadows. The main results are summarized in Tab. 1 . Table 1: Summary of worst-case sample complexity scalings for DIPE with LRM. The table reports the exponential dependence on the number of qubits n , omitting common accuracy and confidence prefactors. The tightness column indicates whether the displayed scaling is attained by an explicit family of input states or remains only an upper bound. The shaded block records the new results obtained in this work. Conjecture 7 is supported by analytical and numerical evidence. † † nicematrix-placeholder: NiceTabular (nicematrix) Organization. This work is organized as follows. Sec. II recalls the DIPE with LRM framework. Sec. III presents our main results, including the Hamming distance kernel reduction, and the single-qubit Clifford and Haar analyses. Sec. IV analyzes DIPE based on independent Pauli shadows for comparison. Notation and conventions. We write \mathscr{D}((\mathbb{C}^{2})^{\otimes n}) for the set of density operators on the n -qubit Hilbert space (\mathbb{C}^{2})^{\otimes n} and \mathbb{R} for the real numbers. For a positive integer m , S_{m} denotes the symmetric group on m elements. Single-qubit binary measurement outcomes are denoted by s,t\in\{0,1\} , whereas bold symbols such as \bm{s},\bm{t}\in\{0,1\}^{n} denote n -qubit outcome strings. Single-qubit subsystems are labeled by letters such as A and B , while \bm{A}=A_{1}\cdots A_{n} and \bm{B}=B_{1}\cdots B_{n} denote the corresponding multipartite registers. The identity operator on the joint register is denoted by \mathbb{I}_{AB} , or equivalently \mathbb{I}_{\bm{A}\bm{B}} when the tensor product structure is emphasized. The full swap between the two global registers is denoted by \mathbb{F}_{AB} , or equivalently \mathbb{F}_{\bm{AB}} when the tensor product structure is emphasized, and more generally \mathbb{F}_{S} denotes the partial swap on a subset S\subseteq[n] . If S is a finite set, then |S| denotes its cardinality. We write \mathbb{E}[\cdot] for expectation and \mathbb{V}[\cdot] for variance. We use \Theta(\cdot) and \mathcal{O}(\cdot) to denote standard asymptotic notation. II DIPE with Local Randomized Measurements We recall the standard kernel estimator formalism for DIPE specialized to the LRM setting. This subsection reviews standard material; the new results begin in the following sections. Let \rho_{\bm{A}},\sigma_{\bm{B}}\in\mathscr{D}((\mathbb{C}^{2})^{\otimes n}) . In one round of local DIPE, Alice and Bob apply the same random product unitary \displaystyle U=\bigotimes_{\ell=1}^{n}U_{\ell}, (1) where each U_{\ell} is sampled independently from a single-qubit ensemble \mathcal{U}_{1} , and then measure in the computational basis, obtaining bit strings \bm{s},\bm{t}\in\{0,1\}^{n} . A kernel estimator is specified by a function \displaystyle f\mathrel{\mathop{\mathchar 58\relax}}\{0,1\}^{n}\times\{0,1\}^{n}\to\mathbb{R}. (2) Given N_{U} independent unitary samples and N_{M} repeated shots for each unitary sample, the empirical estimator reads \displaystyle\widehat{X}_{f}(\rho_{\bm{A}},\sigma_{\bm{B}})=\frac{1}{N_{U}N_{M}^{2}}\sum_{l=1}^{N_{U}}\sum_{j,k=1}^{N_{M}}f(\bm{s}_{l,j},\bm{t}_{l,k}). (3) Since each shot consumes one copy of \rho and one copy of \sigma , the total number of copies used per party is N\mathrel{\mathop{\mathchar 58\relax}}=N_{U}N_{M} ; throughout, we refer to this quantity as the sample complexity. All sample complexity statements below refer to sufficient copy guarantees obtained from variance bounds via Chebyshev’s inequality. In particular, we do not prove matching minimax lower bounds for these estimators or protocols. The averaged estimator can be written as \displaystyle\mathbb{E}[\widehat{X}_{f}(\rho_{\bm{A}},\sigma_{\bm{B}})]=\tr\left[(\rho_{\bm{A}}\otimes\sigma_{\bm{B}})\,\bar{\Omega}_{f}\right], (4) where \displaystyle\bar{\Omega}_{f}\mathrel{\mathop{\mathchar 58\relax}}=\mathbb{E}_{U}\!\left[(U^{\dagger}\otimes U^{\dagger})\Omega_{f}(U\otimes U)\right], (5) with \displaystyle\Omega_{f}\mathrel{\mathop{\mathchar 58\relax}}=\sum_{\bm{s},\bm{t}}f(\bm{s},\bm{t})|{\bm{s}}\rangle\!\langle{\bm{s}}|_{\bm{A}}\otimes|{\bm{t}}\rangle\!\langle{\bm{t}}|_{\bm{B}}. (6) Thus unbiased estimation of \tr\left[\rho\sigma\right] is equivalent to the operator identity \bar{\Omega}_{f}=\mathbb{F}_{\bm{AB}} , where \mathbb{F}_{\bm{AB}} denotes the full swap between the two n -qubit copies \bm{A} and \bm{B} . To expose the variance-based copy scaling, it is convenient to group the data by unitary sample. Define \displaystyle X_{M}^{(l)}\mathrel{\mathop{\mathchar 58\relax}}=\frac{1}{N_{M}^{2}}\sum_{j,k=1}^{N_{M}}f(\bm{s}_{l,j},\bm{t}_{l,k}),\qquad\widehat{X}_{f}=\frac{1}{N_{U}}\sum_{l=1}^{N_{U}}X_{M}^{(l)}. (7) Let X_{M} denote a generic copy of the independent and identically distributed (i.i.d.) random variables X_{M}^{(1)},\dots,X_{M}^{(N_{U})} . Then \displaystyle\mathbb{V}[\widehat{X}_{f}]=\frac{1}{N_{U}}\mathbb{V}[X_{M}]. (8) Applying the law of total variance and classifying the coincidences among the shot indices yields the decomposition into four terms \displaystyle\mathbb{V}[X_{M}]=\mathbb{V}^{(1)}+\mathbb{V}^{(2)}+\mathbb{V}^{(3)}+\mathbb{V}^{(4)}, (9) where \displaystyle\mathbb{V}^{(1)} \displaystyle=-\tr\left[\rho\sigma\right]^{2}, (10a) \displaystyle\mathbb{V}^{(2)} \displaystyle=\frac{1}{N_{M}^{2}}\mathbb{E}_{U}\mathbb{E}_{\bm{s},\bm{t}\mid U}[f(\bm{s},\bm{t})^{2}], (10b) \displaystyle\mathbb{V}^{(3)} \displaystyle=\frac{N_{M}-1}{N_{M}^{2}}\mathbb{E}_{U}\!\left[\Xi_{U}(\rho,\sigma)+\Xi_{U}(\sigma,\rho)\right], (10c) \displaystyle\mathbb{V}^{(4)} \displaystyle=\left(\frac{N_{M}-1}{N_{M}}\right)^{2}\mathbb{E}_{U}[(\mathbb{E}_{\bm{s},\bm{t}\mid U}[f(\bm{s},\bm{t})])^{2}]. (10d) In the above, for a fixed