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:2506.19574 · npj Quantum Information

Distributed quantum inner product estimation with structured random circuits

Congcong Zheng, Kun Wang, Xutao Yu, Ping Xu, Zaichen Zhang

Published Apr 21, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1038/s41534-026-01247-6

Related papers

Distributed Inner-Product Estimation for Continuous-Variable Quantum States

Jun Tang, Congcong Zheng, Xutao Yu +1 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. For multimode continuous-variable (CV) systems, the infinite-dimensional Hilbert space poses an additional challenge. In this work, we develop a CV-DIPE protocol using only local homodyne measurements at shared phase settings and classical communication. Under a known bound on the mean energy per mode, we derive explicit finite-sample guarantees and sufficient copy counts for estimating the full inner product to prescribed accuracy and confidence. The energy constraint yields an inverse-square truncation-bias bound, while Gaussian structure strengthens the tail control to exponential decay and improves the resulting accuracy scaling. Numerical simulations with Gaussian and non-Gaussian states illustrate the balance between truncation bias and statistical error and its dependence on mode number and energy. Our results enable independent CV platforms to benchmark their state preparations against one another, even when neither state admits a tractable classical description.

quant-pharXiv:2610.40141•Oct 30, 2026•0 citations

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

Zhenyuan Huang, Kun Wang, Ping Xu

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$.

quant-pharXiv:2605.14256•May 15, 2026•0 citations

Distributed Quantum inner product estimation

Anurag Anshu, Zeph A. Landau, Yunchao Liu

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.

arXiv:2111.03273•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2022•27 citations

Highly-entangled, highly-doped states that are efficiently cross-device verifiable

Janek Denzler, Santiago Varona, Tommaso Guaita +1 more

In this paper, we introduce a class of highly entangled real quantum states that cannot be approximated by circuits with log -many non-Clifford gates and prove that Bell sampling enables efficient cross-device verification (or distributed inner product estimation) for these states. That is, two remote parties can estimate the inner product tr ( ρ σ ) , each having black-box access to copies of a state ρ (or respectively σ ) in this class. This is significant because it is clear that this task can be achieved in those cases (such as low entanglement or low non-Clifford gate count) where one can independently learn efficient classical descriptions of each state using established techniques and share the description to compute the overlap. Instead, our results demonstrate that this is possible even in more complex scenarios where these “learn and share” methods are insufficient. Our proposal is scalable, as it just requires a number of two-copy Bell measurements and single-copy Pauli measurements that grows polynomially with both the number of qubits and the desired inverse error, and can be implemented in the near term. Moreover, the required number of samples can be efficiently experimentally determined by the parties in advance, and our findings are robust against preparation errors. We anticipate that these results could have applications in quantum cryptography and verification.

arXiv:2501.11688•Physical Review Research•Jun 2, 2025•3 citations

Quantum state learning beyond approximate unitary designs

Gyungmin Cho, Changhun Oh, Dohun Kim

Approximate unitary designs reproduce the statistics of Haar-random unitaries to a given order and accuracy. Recent constructions realize such designs with logarithmic-depth circuits, enabling shallow measurement protocols for various quantum state-learning tasks while preserving performance. These results raise the question of whether approximate designs can replace exact designs more generally. We show that even exponentially small design error need not preserve the learning guarantees of exact designs. This motivates deriving learning guarantees directly from the measurement circuit structure. For observable estimation with classical shadows, we prove that logarithmic-depth two-layer Clifford circuits yield an unbiased estimator matching the global Clifford variance scaling for every state and Hermitian observable. Beyond observable estimation, this bound allows shallow measurements to retain global Clifford guarantees for other tasks, including setting-efficient tomography, mixed-state metrology, and stabilizer structure learning. We complement these statistical guarantees with a compact, exact tensor-network representation of the inverse shadow channel. When measurement bases are reused, approximate unitary designs of arbitrarily high order need not uniformly match the Haar variance in the many-shot limit. For the all-to-all random two-local circuits considered, doing so requires nearly linear depth. Together, our results reveal the capabilities and limitations of shallow quantum state learning, highlighting the distinction between approximating Haar randomness and reproducing its learning guarantees.

quant-pharXiv:2609.39994•Oct 1, 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
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.
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. For multimode continuous-variable (CV) systems, the infinite-dimensional Hilbert space poses an additional challenge. In this work, we develop a CV-DIPE protocol using only local homodyne measurements at shared phase settings and classical communication. Under a known bound on the mean energy per mode, we derive explicit finite-sample guarantees and sufficient copy counts for estimating the full inner product to prescribed accuracy and confidence. The energy constraint yields an inverse-square truncation-bias bound, while Gaussian structure strengthens the tail control to exponential decay and improves the resulting accuracy scaling. Numerical simulations with Gaussian and non-Gaussian states illustrate the balance between truncation bias and statistical error and its dependence on mode number and energy. Our results enable independent CV platforms to benchmark their state preparations against one another, even when neither state admits a tractable classical description.
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.
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 paper, we introduce a class of highly entangled real quantum states that cannot be approximated by circuits with log -many non-Clifford gates and prove that Bell sampling enables efficient cross-device verification (or distributed inner product estimation) for these states. That is, two remote parties can estimate the inner product tr ( ρ σ ) , each having black-box access to copies of a state ρ (or respectively σ ) in this class. This is significant because it is clear that this task can be achieved in those cases (such as low entanglement or low non-Clifford gate count) where one can independently learn efficient classical descriptions of each state using established techniques and share the description to compute the overlap. Instead, our results demonstrate that this is possible even in more complex scenarios where these “learn and share” methods are insufficient. Our proposal is scalable, as it just requires a number of two-copy Bell measurements and single-copy Pauli measurements that grows polynomially with both the number of qubits and the desired inverse error, and can be implemented in the near term. Moreover, the required number of samples can be efficiently experimentally determined by the parties in advance, and our findings are robust against preparation errors. We anticipate that these results could have applications in quantum cryptography and verification.
Approximate unitary designs reproduce the statistics of Haar-random unitaries to a given order and accuracy. Recent constructions realize such designs with logarithmic-depth circuits, enabling shallow measurement protocols for various quantum state-learning tasks while preserving performance. These results raise the question of whether approximate designs can replace exact designs more generally. We show that even exponentially small design error need not preserve the learning guarantees of exact designs. This motivates deriving learning guarantees directly from the measurement circuit structure. For observable estimation with classical shadows, we prove that logarithmic-depth two-layer Clifford circuits yield an unbiased estimator matching the global Clifford variance scaling for every state and Hermitian observable. Beyond observable estimation, this bound allows shallow measurements to retain global Clifford guarantees for other tasks, including setting-efficient tomography, mixed-state metrology, and stabilizer structure learning. We complement these statistical guarantees with a compact, exact tensor-network representation of the inverse shadow channel. When measurement bases are reused, approximate unitary designs of arbitrarily high order need not uniformly match the Haar variance in the many-shot limit. For the all-to-all random two-local circuits considered, doing so requires nearly linear depth. Together, our results reveal the capabilities and limitations of shallow quantum state learning, highlighting the distinction between approximating Haar randomness and reproducing its learning guarantees.
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.