Optimal Distributed Similarity Estimation for Unitary Channels

• URL: http://arxiv.org/abs/2512.10465v1
• Date: Thu, 11 Dec 2025 09:40:31 GMT
• Title: Optimal Distributed Similarity Estimation for Unitary Channels
• Authors: Congcong Zheng, Kun Wang, Xutao Yu, Ping Xu, Zaichen Zhang,
• Abstract summary: We study distributed similarity estimation for unitary channels (DSEU)<n>For $n$-qubit unitary channels, the query complexity of DSEU is $(sqrtd)$, where $d=2n$, for both incoherent and coherent accesses.<n>Our results provide practical and theoretically optimal tools for quantum devices benchmarking and for distributed quantum learning.
• Score: 22.133088494335713
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study distributed similarity estimation for unitary channels (DSEU), the task of estimating the similarity between unitary channels implemented on different quantum devices. We completely address DSEU by showing that, for $n$-qubit unitary channels, the query complexity of DSEU is $Θ(\sqrt{d})$, where $d=2^n$, for both incoherent and coherent accesses. First, we propose two estimation algorithms for DSEU with these accesses utilizing the randomized measurement toolbox. The query complexities of these algorithms are both $O(\sqrt{d})$. Although incoherent access is generally weaker than coherent access, our incoherent algorithm matches this complexity by leveraging additional shared randomness between devices, highlighting the power of shared randomness in distributed quantum learning. We further establish matching lower bounds, proving that $Θ(\sqrt{d})$ queries are both necessary and sufficient for DSEU. Finally, we compare our algorithms with independent classical shadow and show that ours have a square-root advantage. Our results provide practical and theoretically optimal tools for quantum devices benchmarking and for distributed quantum learning.

Related papers

• Random Stinespring superchannel: converting channel queries into dilation isometry queries [9.841060883971746]
  We introduce a channel-level analogue, which we call the random Stinespring superchannel.<n>We show that the optimal query complexity of learning a quantum channel with input dimension $d_A$, output dimension $d_B$, and Choi rank $r$ is $(d_A d_B r)$.
  arXiv  Detail & Related papers  (2025-12-23T18:46:07Z)
• On the query complexity of unitary channel certification [0.0]
  Certifying the correct functioning of a unitary channel is a critical step toward reliable quantum information processing.<n>We show that incoherent algorithms-those without quantum memory-require $Omega(d/varepsilon2)$ queries, matching the known upper bound.
  arXiv  Detail & Related papers  (2025-07-23T06:51:33Z)
• Distributed quantum algorithm for divergence estimation and beyond [12.925989807145301]
  We propose a distributed quantum algorithm framework to compute $rm Tr(f(A)g(B))$ within an additive error $varepsilon$.<n>This framework holds broad applicability across a range of distributed quantum computing tasks.
  arXiv  Detail & Related papers  (2025-03-12T14:28:22Z)
• Majorization-based benchmark of the complexity of quantum processors [105.54048699217668]
  We numerically simulate and characterize the operation of various quantum processors. We identify and assess quantum complexity by comparing the performance of each device against benchmark lines. We find that the majorization-based benchmark holds as long as the circuits' output states have, on average, high purity.
  arXiv  Detail & Related papers  (2023-04-10T23:01:10Z)
• Concise and Efficient Quantum Algorithms for Distribution Closeness Testing [0.2741266294612775]
  We study the impact of quantum computation on the fundamental problem of testing the property of distributions. We propose the currently best quantum algorithms for this problem under the metrics of $l1$-distance and $l2$-distance.
  arXiv  Detail & Related papers  (2023-02-13T04:03:59Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  Unitarity estimation is a basic and important problem in quantum device certification and benchmarking. We provide a unified framework for unitarity estimation, which induces ancilla-efficient algorithms. We show that both the $d$-dependence and $epsilon$-dependence of our algorithms are optimal.
  arXiv  Detail & Related papers  (2022-12-19T09:36:33Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.