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:2503.09431

Distributed quantum algorithm for divergence estimation and beyond

Honglin Chen, Weiguang Xie, Youbin Yu, Hao Fu, Xiang‐Yang Li

Published Mar 12, 2025• 0 citations
arXivHTMLPDF

Abstract

With the rapid advancement of quantum information technology, designing efficient distributed quantum algorithms to perform various information processing tasks remains challenging. In this paper, we consider a distributed scenario where two parties, Alice and Bob, given access to matrices $A$ and $B$ respectively, aim to estimate ${\rm Tr}(f(A)g(B))$, where $f$ and $g$ are known functions. In this task, only local quantum operations, classical communication and single-qubit measurements are allowed due to the high cost of quantum communication and entangled measurements. We propose a distributed quantum algorithm framework to compute ${\rm Tr}(f(A)g(B))$ within an additive error $\varepsilon$. The proposed algorithm framework requires $\widetilde{O}\left(d^2 / (δ\varepsilon^2)\right)$ quantum queries and two-qubit gates, assuming that the minimum singular value of each matrix $A, B \in \mathbb{C}^{d \times d}$ is at least $δ$. Additionally, our algorithm framework uses a simple Hadamard test architecture, enabling easier quantum hardware implementation. This algorithm framework allows for various applications including quantum divergence estimation, distributed solving of linear system, and distributed Hamiltonian simulation, while preserving the privacy of both parties. Furthermore, we establish a lower bound of $Ω\left(\max\left\{1 /\varepsilon^2, \sqrt{dr}/\varepsilon\right\}\right)$ on the query complexity for the task, where $r$ denotes the rank of the input matrices. We believe this framework holds broad applicability across a range of distributed quantum computing tasks.

DOI
10.48550/arxiv.2503.09431

Related papers

Optimal Distributed Similarity Estimation of Quantum Channels

Congcong Zheng, Kun Wang, Xutao Yu +2 more

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\{\sqrt{d}/\varepsilon,1/\varepsilon^2\})$, where $d$ is the channel dimension and $\varepsilon$ 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.

quant-pharXiv:2512.10465•Dec 12, 2025•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

The communication complexity of distributed estimation

Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2 more

We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions $p$ and $q$ over domains $X$ and $Y$, respectively. Their goal is to estimate \[ \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] \] to within additive error $\varepsilon$ for a bounded function $f$, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of $f$ and the error parameter $\varepsilon$. The random sampling approach -- estimating the mean by averaging $f$ over $O(1/\varepsilon^2)$ random samples -- requires $O(R(f)/\varepsilon^2)$ total communication, where $R(f)$ is the randomized communication complexity of $f$. We design a new debiasing protocol which improves the dependence on $1/\varepsilon$ to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.

arXiv:2511.21015•Nov 26, 2025•0 citations

Distributed quantum computing models: Study of architectures and models for the distribution of quantum computing tasks across multiple quantum nodes

Akaash Vishal Hazarika, Mahak Shah

The exploration of distributed quantum computing (DQC) represents a significant frontier in quantum information science, aiming to harness the unique properties of quantum mechanics to solve complex computational problems effectively. This paper discusses the diverse architectures and models that facilitate the distribution of quantum computing tasks across multiple quantum nodes, thereby addressing the limitations inherent in single quantum devices. DQC systems exploit the principles of superposition and entanglement to enhance computational capabilities beyond what classical computing systems can achieve. We examine various DQC architectures, including both quantum-classical hybrid systems and fully quantum distributed systems, highlighting their respective benefits and challenges. Key issues such as coherence, communication overhead, and error correction are discussed in detail, and we analyze specific use cases where DQC demonstrates superior performance relative to classical computing approaches, including optimization problems in logistics and finance, as well as quantum simulations for material science. Furthermore, we identify future research directions aimed at overcoming existing barriers to the practical implementation of DQC systems. By assessing the current landscape and future possibilities of DQC, this paper underscores the transformative potential of distributed quantum computing in various fields, paving the way for realizing more complex quantum algorithms and applications.

International Journal of Science and Research Archive•Dec 30, 2024•5 citations

Distributed Quantum Simulation

Anonymous, Jue Xu, Wenjun Yu +3 more

Quantum simulation is a promising pathway toward practical quantum advantage by simulating large-scale quantum systems. In this Letter, we propose communication-efficient distributed quantum simulation protocols by exploring three quantum simulation algorithms, including the product formula, the truncated Taylor series, and quantum signal processing over a quantum network. Crucially, our protocols significantly reduce the local hardware requirements of individual quantum processing units while ensuring the overall gate complexity does not exceed that of standard monolithic architectures. Our protocols are further shown to be optimal by deriving a lower bound on the quantum communication complexity for distributed quantum simulations with respect to evolution time and the number of distributed quantum processing units. Additionally, our distributed techniques go beyond quantum simulation and are applied to distributed versions of Grover's algorithm and quantum phase estimation. Our work not only paves the way for achieving a practical quantum advantage by scalable quantum simulation but also enlightens the design of more general distributed architectures across various physical systems for quantum computation.

arXiv:2411.02881•Physical Review Letters•Sep 14, 2026•0 citations

Quantum Algorithms for Computing Maximal Quantum $f$-divergence and Kubo-Ando means

Trung Hoa Dinh, Nhat A. Nghiem

The development of quantum computation has resulted in many quantum algorithms for a wide array of tasks. Recently, there is a growing interest in using quantum computing techniques to estimate or compute quantum information-theoretic quantities such as Renyi entropy, Von Neumann entropy, matrix means, etc. Motivated by these results, we present quantum algorithms for computing the maximal quantum $f$-divergences and the operator-theoretic matrix Kubo--Ando means. Both of them involve Renyi entropies, matrix means as special cases, thus implying the universality of our framework.

quant-pharXiv:2511.10607•Quantum Information Processing•Nov 14, 2025•0 citations
With the rapid advancement of quantum information technology, designing efficient distributed quantum algorithms to perform various information processing tasks remains challenging. In this paper, we consider a distributed scenario where two parties, Alice and Bob, given access to matrices AAA and BBB respectively, aim to estimate Tr(f(A)g(B)){\rm Tr}(f(A)g(B))Tr(f(A)g(B)), where fff and ggg are known functions. In this task, only local quantum operations, classical communication and single-qubit measurements are allowed due to the high cost of quantum communication and entangled measurements. We propose a distributed quantum algorithm framework to compute Tr(f(A)g(B)){\rm Tr}(f(A)g(B))Tr(f(A)g(B)) within an additive error ε\varepsilonε. The proposed algorithm framework requires O~(d2/(δε2))\widetilde{O}\left(d^2 / (δ\varepsilon^2)\right)O(d2/(δε2)) quantum queries and two-qubit gates, assuming that the minimum singular value of each matrix A,B∈Cd×dA, B \in \mathbb{C}^{d \times d}A,B∈Cd×d is at least δδδ. Additionally, our algorithm framework uses a simple Hadamard test architecture, enabling easier quantum hardware implementation. This algorithm framework allows for various applications including quantum divergence estimation, distributed solving of linear system, and distributed Hamiltonian simulation, while preserving the privacy of both parties. Furthermore, we establish a lower bound of Ω(max⁡{1/ε2,dr/ε})Ω\left(\max\left\{1 /\varepsilon^2, \sqrt{dr}/\varepsilon\right\}\right)Ω(max{1/ε2,dr​/ε}) on the query complexity for the task, where rrr denotes the rank of the input matrices. We believe this framework holds broad applicability across a range of distributed quantum computing tasks.
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})Θ(\max\{\sqrt{d}/\varepsilon,1/\varepsilon^2\})Θ(max{d​/ε,1/ε2}), where ddd is the channel dimension and ε\varepsilonε 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.
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.
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions ppp and qqq over domains XXX and YYY, respectively. Their goal is to estimate Ex∼p, y∼q[f(x,y)] \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] Ex∼p,y∼q​[f(x,y)] to within additive error ε\varepsilonε for a bounded function fff, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of fff and the error parameter ε\varepsilonε. The random sampling approach -- estimating the mean by averaging fff over O(1/ε2)O(1/\varepsilon^2)O(1/ε2) random samples -- requires O(R(f)/ε2)O(R(f)/\varepsilon^2)O(R(f)/ε2) total communication, where R(f)R(f)R(f) is the randomized communication complexity of fff. We design a new debiasing protocol which improves the dependence on 1/ε1/\varepsilon1/ε to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.
The exploration of distributed quantum computing (DQC) represents a significant frontier in quantum information science, aiming to harness the unique properties of quantum mechanics to solve complex computational problems effectively. This paper discusses the diverse architectures and models that facilitate the distribution of quantum computing tasks across multiple quantum nodes, thereby addressing the limitations inherent in single quantum devices. DQC systems exploit the principles of superposition and entanglement to enhance computational capabilities beyond what classical computing systems can achieve. We examine various DQC architectures, including both quantum-classical hybrid systems and fully quantum distributed systems, highlighting their respective benefits and challenges. Key issues such as coherence, communication overhead, and error correction are discussed in detail, and we analyze specific use cases where DQC demonstrates superior performance relative to classical computing approaches, including optimization problems in logistics and finance, as well as quantum simulations for material science. Furthermore, we identify future research directions aimed at overcoming existing barriers to the practical implementation of DQC systems. By assessing the current landscape and future possibilities of DQC, this paper underscores the transformative potential of distributed quantum computing in various fields, paving the way for realizing more complex quantum algorithms and applications.
Quantum simulation is a promising pathway toward practical quantum advantage by simulating large-scale quantum systems. In this Letter, we propose communication-efficient distributed quantum simulation protocols by exploring three quantum simulation algorithms, including the product formula, the truncated Taylor series, and quantum signal processing over a quantum network. Crucially, our protocols significantly reduce the local hardware requirements of individual quantum processing units while ensuring the overall gate complexity does not exceed that of standard monolithic architectures. Our protocols are further shown to be optimal by deriving a lower bound on the quantum communication complexity for distributed quantum simulations with respect to evolution time and the number of distributed quantum processing units. Additionally, our distributed techniques go beyond quantum simulation and are applied to distributed versions of Grover's algorithm and quantum phase estimation. Our work not only paves the way for achieving a practical quantum advantage by scalable quantum simulation but also enlightens the design of more general distributed architectures across various physical systems for quantum computation.
Quantum Algorithms for Computing Maximal Quantum fff-divergence and Kubo-Ando means
The development of quantum computation has resulted in many quantum algorithms for a wide array of tasks. Recently, there is a growing interest in using quantum computing techniques to estimate or compute quantum information-theoretic quantities such as Renyi entropy, Von Neumann entropy, matrix means, etc. Motivated by these results, we present quantum algorithms for computing the maximal quantum fff-divergences and the operator-theoretic matrix Kubo--Ando means. Both of them involve Renyi entropies, matrix means as special cases, thus implying the universality of our framework.