Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2605.14256

Worst-Case Sample Complexity Bounds for Distributed Inner Product Estimation with Local Randomized Measurements

Zhenyuan Huang, Kun Wang, Ping Xu

quant-phSubmitted May 14, 2026• Announced May 15, 2026• 0 citations
arXivHTMLPDF

Abstract

We study distributed inner product estimation for $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 $\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 $\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 $\mathcal{O}(\sqrt{7.5^n})$ for large $n$.

Related papers

Distributed quantum inner product estimation with structured random circuits

Congcong Zheng, Kun Wang, Xutao Yu +2 more

Distributed inner product estimation (DIPE) is a fundamental task in quantum information, aiming to estimate the inner product between two unknown quantum states prepared on distributed quantum platforms. Existing rigorous sample complexity analyses are limited to unitary 4-designs, which pose significant practical challenges for near-term quantum devices. This work addresses this challenge by exploring DIPE with structured random circuits. We first establish that DIPE with an arbitrary unitary 2-design ensemble achieves an average sample complexity of \({\mathcal{O}}(\sqrt{{2}^{n}})\) , where n is the number of qubits. We then analyze ensembles below unitary 2-designs—specifically, the brickwork and local unitary 2-design ensembles—demonstrating average sample complexities of \({\mathcal{O}}(\sqrt{2.1{8}^{n}})\) and \({\mathcal{O}}(\sqrt{2.{5}^{n}})\) , respectively. Furthermore, we analyze the state-dependent sample complexity. For brickwork ensembles, we develop a tensor network approach to compute the asymptotic state-dependent sample complexity, showing that it converges to \({\mathcal{O}}(\sqrt{2.1{8}^{n}})\) as the circuit depth increases. Remarkably, we find that DIPE with the global Clifford ensemble requires \(\Theta (\sqrt{{2}^{n}})\) copies, matching the performance of unitary 4-designs. For both local and global Clifford ensembles, we find that the efficiency can be further enhanced by the nonstabilizerness of states. Additionally, for approximate unitary 4-designs, the performance exponentially approaches that of exact unitary 4-designs as the circuit depth increases. Our results provide theoretically guaranteed methods for implementing DIPE with experimentally feasible unitary ensembles.

arXiv:2506.19574•npj Quantum Information•Apr 21, 2026•0 citations

Closed-form analytic expressions for shadow estimation with brickwork circuits

Mirko Arienzo, Markus Heinrich, Ingo Roth +1 more

Properties of quantum systems can be estimated using classical shadows, which implement measurements based on random ensembles of unitaries. Originally derived for global Clifford unitaries and products of single-qubit Clifford gates, practical implementations are limited to the latter scheme for moderate numbers of qubits. Beyond local gates, the accurate implementation of very short random circuits with two-local gates is still experimentally feasible and, therefore, interesting for implementing measurements in near-term applications. In this work, we derive closed-form analytical expressions for shadow estimation using brickwork circuits with two layers of parallel two-local Haar-random (or Clifford) unitaries. Besides the construction of the classical shadow, our results give rise to sample-complexity guarantees for estimating Pauli observables.We then compare the performance of shadow estimation with brickwork circuits to the established approach using local Clifford unitaries and find improved sample complexity in the estimation of observables supported on sufficiently many qubits.

arXiv:2211.09835•Quantum Information and Computation•Sep 1, 2023•25 citations

Optimal Shadow Estimation with Minimal Measurement Settings

Zhiyao Yang, Datong Chen, Huangjun Zhu

Shadow estimation is a powerful framework for predicting quantum properties from randomized measurements. While $3$-design protocols achieve optimal worst-case performance, the minimal number of measurement bases required for such optimality has remained open. Here we prove that $Θ(d^2)$ measurement bases are both necessary and sufficient for worst-case optimal shadow estimation and construct an explicit basis family. In stark contrast, any state $2$-design already suffices for average-case optimality: the mean squared shadow norm of normalized observables is bounded by a universal constant, and we prove strong concentration for Haar-random states, yielding constant sample complexity for generic pure-state fidelity estimation. Easily implementable $2$-designs -- from mutually unbiased bases, cyclic measurements, or shallow $\mathcal{O}(\log n)$-depth circuits -- enable optimal average-case protocols with remarkably simple measurement strategies. Our results establish a fundamental complexity separation: worst-case estimation requires $Θ(d^2)$ bases, whereas average-case performance requires only $Θ(d)$ bases, with broad implications for quantum information theory and near-term experiments.

quant-pharXiv:2606.20003•Jun 19, 2026

Sample complexity of purity and inner product estimation

Weiyuan Gong, Jonas Haferkamp, Qi Ye +1 more

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.

arXiv:2410.12712•Physical Review Research•Jan 8, 2026•1 citation

Sample Complexity for Embedded Multipartite Entanglement Witness via Pauli and Clifford Classical Shadows

Ziran Zhang

Detecting multipartite entanglement in many qubit systems is measurement-intensive, motivating protocols that estimate only selected observables with provable efficiency. In this work we use the classical shadow protocol to study the sample complexity required to estimate a family of subsystem $n$-partite entanglement witness embedded in an larger $N$-qubit system. We derive ensemble dependent variance bounds that lead to qualitatively distinct scaling for the snapshots cost at fixed additive error $ε$ with numerical simulations confirm these trends, exhibiting a clear crossover from Pauli favorable performance for local witness to Clifford favorable performance as the witness becomes more global.

quant-pharXiv:2601.00859•Dec 31, 2025•0 citations

Sample Complexity Bounds for Scalar Parameter Estimation Under Quantum Differential Privacy

Farhad Farokhi

This paper presents tight upper and lower bounds for minimum number of samples (copies of a quantum state) required to attain a prescribed accuracy (measured by error variance) for scalar parameters estimation using unbiased estimators under quantum local differential privacy for qubits. Particularly, the best-case (optimal) scenario is considered by minimizing the sample complexity over all differentially-private channels; the worst-case channels can be arbitrarily uninformative and render the problem ill-defined. In the small privacy budget regime, i.e., 1, the sample complexity scales as (-2). This bound matches that of classical parameter estimation under local differential privacy. The lower bound however loosens in the large privacy budget regime, i.e., 1. The upper bound for the minimum number of samples is generalized to qudits (with dimension d) resulting in sample complexity of O(d-2).

arXiv:2501.14184•IEEE Control Systems Letters•Jan 1, 2025•0 citations
We study distributed inner product estimation for nnn-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 O(4.5n)\mathcal{O}(\sqrt{4.5^n})O(4.5n​), 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 O(3.6n)\mathcal{O}(\sqrt{3.6^n})O(3.6n​) 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 O(7.5n)\mathcal{O}(\sqrt{7.5^n})O(7.5n​) for large nnn.
Distributed inner product estimation (DIPE) is a fundamental task in quantum information, aiming to estimate the inner product between two unknown quantum states prepared on distributed quantum platforms. Existing rigorous sample complexity analyses are limited to unitary 4-designs, which pose significant practical challenges for near-term quantum devices. This work addresses this challenge by exploring DIPE with structured random circuits. We first establish that DIPE with an arbitrary unitary 2-design ensemble achieves an average sample complexity of O(2n){\mathcal{O}}(\sqrt{{2}^{n}})O(2n​) , where n is the number of qubits. We then analyze ensembles below unitary 2-designs—specifically, the brickwork and local unitary 2-design ensembles—demonstrating average sample complexities of O(2.18n){\mathcal{O}}(\sqrt{2.1{8}^{n}})O(2.18n​) and O(2.5n){\mathcal{O}}(\sqrt{2.{5}^{n}})O(2.5n​) , respectively. Furthermore, we analyze the state-dependent sample complexity. For brickwork ensembles, we develop a tensor network approach to compute the asymptotic state-dependent sample complexity, showing that it converges to O(2.18n){\mathcal{O}}(\sqrt{2.1{8}^{n}})O(2.18n​) as the circuit depth increases. Remarkably, we find that DIPE with the global Clifford ensemble requires Θ(2n)\Theta (\sqrt{{2}^{n}})Θ(2n​) copies, matching the performance of unitary 4-designs. For both local and global Clifford ensembles, we find that the efficiency can be further enhanced by the nonstabilizerness of states. Additionally, for approximate unitary 4-designs, the performance exponentially approaches that of exact unitary 4-designs as the circuit depth increases. Our results provide theoretically guaranteed methods for implementing DIPE with experimentally feasible unitary ensembles.
Properties of quantum systems can be estimated using classical shadows, which implement measurements based on random ensembles of unitaries. Originally derived for global Clifford unitaries and products of single-qubit Clifford gates, practical implementations are limited to the latter scheme for moderate numbers of qubits. Beyond local gates, the accurate implementation of very short random circuits with two-local gates is still experimentally feasible and, therefore, interesting for implementing measurements in near-term applications. In this work, we derive closed-form analytical expressions for shadow estimation using brickwork circuits with two layers of parallel two-local Haar-random (or Clifford) unitaries. Besides the construction of the classical shadow, our results give rise to sample-complexity guarantees for estimating Pauli observables.We then compare the performance of shadow estimation with brickwork circuits to the established approach using local Clifford unitaries and find improved sample complexity in the estimation of observables supported on sufficiently many qubits.
Shadow estimation is a powerful framework for predicting quantum properties from randomized measurements. While 333-design protocols achieve optimal worst-case performance, the minimal number of measurement bases required for such optimality has remained open. Here we prove that Θ(d2)Θ(d^2)Θ(d2) measurement bases are both necessary and sufficient for worst-case optimal shadow estimation and construct an explicit basis family. In stark contrast, any state 222-design already suffices for average-case optimality: the mean squared shadow norm of normalized observables is bounded by a universal constant, and we prove strong concentration for Haar-random states, yielding constant sample complexity for generic pure-state fidelity estimation. Easily implementable 222-designs -- from mutually unbiased bases, cyclic measurements, or shallow O(log⁡n)\mathcal{O}(\log n)O(logn)-depth circuits -- enable optimal average-case protocols with remarkably simple measurement strategies. Our results establish a fundamental complexity separation: worst-case estimation requires Θ(d2)Θ(d^2)Θ(d2) bases, whereas average-case performance requires only Θ(d)Θ(d)Θ(d) bases, with broad implications for quantum information theory and near-term experiments.
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.
Detecting multipartite entanglement in many qubit systems is measurement-intensive, motivating protocols that estimate only selected observables with provable efficiency. In this work we use the classical shadow protocol to study the sample complexity required to estimate a family of subsystem nnn-partite entanglement witness embedded in an larger NNN-qubit system. We derive ensemble dependent variance bounds that lead to qualitatively distinct scaling for the snapshots cost at fixed additive error εεε with numerical simulations confirm these trends, exhibiting a clear crossover from Pauli favorable performance for local witness to Clifford favorable performance as the witness becomes more global.
This paper presents tight upper and lower bounds for minimum number of samples (copies of a quantum state) required to attain a prescribed accuracy (measured by error variance) for scalar parameters estimation using unbiased estimators under quantum local differential privacy for qubits. Particularly, the best-case (optimal) scenario is considered by minimizing the sample complexity over all differentially-private channels; the worst-case channels can be arbitrarily uninformative and render the problem ill-defined. In the small privacy budget regime, i.e., 1, the sample complexity scales as (-2). This bound matches that of classical parameter estimation under local differential privacy. The lower bound however loosens in the large privacy budget regime, i.e., 1. The upper bound for the minimum number of samples is generalized to qudits (with dimension d) resulting in sample complexity of O(d-2).