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

IEEE International Conference on Quantum Computing and Engineering (QCE)

Lower Bounds for the Communication Costs of Distributing Quantum Fourier Transform on Clique Networks

Ali Ebnenasir

Published Aug 30, 2025• 1 citation
Publisher

Abstract

This paper investigates asymptotic lower bounds for the communication costs of distributing Quantum Fourier Transform (QFT) on clique networks of quantum machines. We first show that determining lower/upper bound communication complexity is closely related to the number of machines whose qubit capacity becomes full at different stages of QFT. Subsequently, we provide lower and upper bounds on the number of full machines during the execution of distributed QFT. These bounds help us determine the lower bound of the number of nonlocal operations that should be performed during distribution of QFT on clique networks. We initially analyze the lower bound on communication complexity for the case where machines have capacity two; i.e., each quantum machine can hold at most two qubits. We show that, in this case, the lower bound is$\Omega\left(n^{2}\right)$, where$n$denotes the number of input qubits. Considering the existing quadratic upper bound in related work, our lower bound result implies that the existing upper bound is actually tight when machine capacity is two. This is a significant theoretical boundary for developers of distribution compilers. We also show that if machine capacity$c>2$is a fixed fraction of$n$, then the lower bound becomes linear.

DOI
10.1109/qce65121.2025.00112

Related papers

Communication Complexity of Distributed Unitary Synthesis

Longcheng Li, Xiaoming Sun, Jialin Zhang +1 more

We study space-bounded communication complexity for unitary implementation in distributed quantum processors, where we restrict the number of qubits per processor to ensure practical relevance and technical non-triviality. We model distributed quantum processors using distributed quantum circuits with nonlocal two-qubit gates, defining the distributed communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization, up to permutations of data qubit positions. Our contributions are twofold. First, for general $n$-qubit unitaries, we improve upon the trivial $O(4^n)$ communication bound. Considering $k$ pairwise-connected processors (each with $n/k$ data qubits and $m$ ancillas), we prove the communication complexity satisfies $O\left(\max\{4^{(1-1/k)n - m}, n\}\right)$ -- for example, $O(2^n)$ when $m=0$ and $k=2$ -- and establish the tightness of this upper bound. We further extend the analysis to approximation models and general network topologies. Second, for special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity in the exact model, outperforming the trivial quadratic bounds applicable to these cases. In the approximation model, QFT's communication complexity reduces drastically from linear to logarithmic, while Clifford circuits retain a linear lower bound. These results offer fundamental insights for optimizing communication in distributed quantum unitary implementation, advancing the feasibility of large-scale DQC systems.

quant-pharXiv:2511.04250•IEEE Transactions on Information Theory•Nov 7, 2025•0 citations

Communication-Efficient Distributed Inverse Quantum Fourier Transform

F. Javier Cardama, Jorge Vázquez-Pérez, Tomás F. Pena +1 more

The scalability of quantum computing is currently limited by physical, technological, and architectural constraints that hinder the integration of a large number of qubits within a single quantum processor. Distributed quantum computing (DQC) has therefore emerged as a viable alternative, aiming to interconnect multiple smaller quantum processing units (QPUs) to jointly operate on a global quantum state. While this paradigm enables scalable architectures, it introduces significant communication overhead due to the cost of non-local quantum operations across distant nodes. In this work we propose a distributed formulation of the iQFT over a quantum network composed of $P$ nodes, each hosting $Q$ qubits, enabling the execution on a logical register of size $n = P \cdot Q$. Furthermore, we introduce a communication-efficient variant based on a threshold-driven pruning strategy, referred to as a \emph{communication horizon}, which exploits the exponentially decreasing significance of controlled-phase rotations to safely omit remote gates with negligible impact. By reducing the number of inter-node quantum interactions, the proposed approach significantly lowers the quantum communication requirements of the distributed iQFT while preserving its functional correctness. Crucially, we show that this approach fundamentally alters the scaling of the algorithm: the entanglement resource consumption per node saturates to a constant value, reducing the global communication complexity from quadratic $\mathcal{O}(P^2)$ to linear $\mathcal{O}(P)$. As the iQFT constitutes a critical building block in many quantum algorithms, the techniques presented in this paper directly contribute to improving the practicality and scalability of distributed quantum computation.

quant-pharXiv:2605.10710•Future Generation Computer Systems•May 12, 2026•0 citations

Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model

Fabien Dufoulon, Frédéric Magniez, Gopal Pandurangan

We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks. These algorithms are (essentially) optimal with respect to their communication (message) complexity in the {\em quantum routing model} introduced in [PODC 2025]. The message complexity of our algorithms is $\tilde{O}(n)$ for leader election, broadcast, and MST, and $\tilde{O}(\sqrt{mn})$ for BFS ($n$ and $m$ are the number of nodes and edges of the network, respectively). These message bounds are nearly tight in the quantum routing model since we show almost matching corresponding quantum message lower bounds. Our results significantly improve on the prior work of [PODC 2025], who presented distributed quantum algorithms under the same model that had a message complexity of $\tilde{O}(\sqrt{mn})$ for leader election. Our algorithms demonstrate the significant communication advantage that quantum routing has over classical in distributed computing, since $Ω(m)$ is a well-established classical message lower bound for leader election, broadcast, MST, and BFS that applies even to randomized Monte-Carlo algorithms [JACM 2015]. Thus, our quantum algorithms can, in general, give a quadratic advantage in the communication cost for these fundamental problems. A main technical tool we use to design our distributed algorithms is quantum walks based on electric networks. We posit a framework for using quantum walks in the distributed setting to design communication-efficient distributed quantum algorithms. Our framework can be used as a black box to significantly reduce communication costs and may be of independent interest. Additionally, our lower-bound technique for establishing distributed quantum message lower bounds can also be applied to other problems.

quant-pharXiv:2602.15529•Feb 18, 2026•0 citations

The exact lower bound of CNOT-complexity for fault-tolerant quantum Fourier transform

Qiqing Xia, Huiqin Xie, Yang, Li

The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-$R_k$ in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-$R_k$ is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10^{-2}. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.

arXiv:2409.02506•Sep 4, 2024•0 citations

Unbounded quantum advantage in communication with minimal input scaling

Sumit Rout, Nitica Sakharwade, Some Sankar Bhattacharya +2 more

In communication complexity-like problems, previous studies have shown either an exponential quantum advantage or an unbounded quantum advantage with an exponentially large input set Θ ( 2 n ) bit with respect to classical communication Θ ( n ) bit. In the former, the quantum and classical separation grows exponentially in input while the latter's quantum communication resource is a constant. Remarkably, it was still open whether an unbounded quantum advantage exists while the inputs do not scale exponentially. Here we answer this question affirmatively using an input size of optimal order. Considering two variants as tasks: (1) distributed computation of relation and (2) , we study the one-way zero-error communication complexity of a relation induced by a distributed clique labeling problem for orthogonality graphs. While we prove no quantum advantage in the first task, we show an in relation reconstruction without public coins. Specifically, for a class of graphs with order m , the quantum complexity is Θ ( 1 ) while the classical complexity is Θ ( log 2 m ) . Remarkably, the input size is Θ ( log 2 m ) bit and the order of its scaling with respect to classical communication is . This is exponentially better compared to previous works. Additionally, we prove a lower bound (linear in the number of maximum cliques) on the amount of classical public coin necessary to overcome the separation in the scenario of restricted communication and connect this to the existence of orthogonal arrays. Finally, we highlight some applications of this task to semi-device-independent dimension witnessing as well as to the detection of mutually unbiased bases.

arXiv:2305.10372•Physical Review Research•Apr 30, 2025•2 citations

Capacity of a continuously distributed quantum network

Xiangzhen Zhou, Xutao Yu, Zaichen Zhang

This paper investigates the capacity of a continuously distributed quantum network. A mathematical model of a multihop quantum communication process is given for capacity analysis. Our model assumes $n$ nodes in a unit square, and both a capacity upper bound for arbitrarily distributed quantum networks and a constructed capacity lower bound for randomly distributed quantum networks are obtained as $n\ensuremath{\rightarrow}\ensuremath{\infty}$. According to our results, the capacity in arbitrarily distributed networks is proportional to $n$ while capacity in randomly distributed networks is independent of $n$. Moreover, our findings exhibit the bounds on quantum network capacity and could open a door to performance analysis for future quantum networking.

Physical Review A•Jul 13, 2018•1 citation
This paper investigates asymptotic lower bounds for the communication costs of distributing Quantum Fourier Transform (QFT) on clique networks of quantum machines. We first show that determining lower/upper bound communication complexity is closely related to the number of machines whose qubit capacity becomes full at different stages of QFT. Subsequently, we provide lower and upper bounds on the number of full machines during the execution of distributed QFT. These bounds help us determine the lower bound of the number of nonlocal operations that should be performed during distribution of QFT on clique networks. We initially analyze the lower bound on communication complexity for the case where machines have capacity two; i.e., each quantum machine can hold at most two qubits. We show that, in this case, the lower bound isΩ(n2)\Omega\left(n^{2}\right)Ω(n2), wherennndenotes the number of input qubits. Considering the existing quadratic upper bound in related work, our lower bound result implies that the existing upper bound is actually tight when machine capacity is two. This is a significant theoretical boundary for developers of distribution compilers. We also show that if machine capacityc>2c>2c>2is a fixed fraction ofnnn, then the lower bound becomes linear.
We study space-bounded communication complexity for unitary implementation in distributed quantum processors, where we restrict the number of qubits per processor to ensure practical relevance and technical non-triviality. We model distributed quantum processors using distributed quantum circuits with nonlocal two-qubit gates, defining the distributed communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization, up to permutations of data qubit positions. Our contributions are twofold. First, for general nnn-qubit unitaries, we improve upon the trivial O(4n)O(4^n)O(4n) communication bound. Considering kkk pairwise-connected processors (each with n/kn/kn/k data qubits and mmm ancillas), we prove the communication complexity satisfies O(max⁡{4(1−1/k)n−m,n})O\left(\max\{4^{(1-1/k)n - m}, n\}\right)O(max{4(1−1/k)n−m,n}) -- for example, O(2n)O(2^n)O(2n) when m=0m=0m=0 and k=2k=2k=2 -- and establish the tightness of this upper bound. We further extend the analysis to approximation models and general network topologies. Second, for special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity in the exact model, outperforming the trivial quadratic bounds applicable to these cases. In the approximation model, QFT's communication complexity reduces drastically from linear to logarithmic, while Clifford circuits retain a linear lower bound. These results offer fundamental insights for optimizing communication in distributed quantum unitary implementation, advancing the feasibility of large-scale DQC systems.
The scalability of quantum computing is currently limited by physical, technological, and architectural constraints that hinder the integration of a large number of qubits within a single quantum processor. Distributed quantum computing (DQC) has therefore emerged as a viable alternative, aiming to interconnect multiple smaller quantum processing units (QPUs) to jointly operate on a global quantum state. While this paradigm enables scalable architectures, it introduces significant communication overhead due to the cost of non-local quantum operations across distant nodes. In this work we propose a distributed formulation of the iQFT over a quantum network composed of PPP nodes, each hosting QQQ qubits, enabling the execution on a logical register of size n=P⋅Qn = P \cdot Qn=P⋅Q. Furthermore, we introduce a communication-efficient variant based on a threshold-driven pruning strategy, referred to as a \emph{communication horizon}, which exploits the exponentially decreasing significance of controlled-phase rotations to safely omit remote gates with negligible impact. By reducing the number of inter-node quantum interactions, the proposed approach significantly lowers the quantum communication requirements of the distributed iQFT while preserving its functional correctness. Crucially, we show that this approach fundamentally alters the scaling of the algorithm: the entanglement resource consumption per node saturates to a constant value, reducing the global communication complexity from quadratic O(P2)\mathcal{O}(P^2)O(P2) to linear O(P)\mathcal{O}(P)O(P). As the iQFT constitutes a critical building block in many quantum algorithms, the techniques presented in this paper directly contribute to improving the practicality and scalability of distributed quantum computation.
We present new distributed quantum algorithms for fundamental distributed computing problems, namely, leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks. These algorithms are (essentially) optimal with respect to their communication (message) complexity in the {\em quantum routing model} introduced in [PODC 2025]. The message complexity of our algorithms is O~(n)\tilde{O}(n)O~(n) for leader election, broadcast, and MST, and O~(mn)\tilde{O}(\sqrt{mn})O~(mn​) for BFS (nnn and mmm are the number of nodes and edges of the network, respectively). These message bounds are nearly tight in the quantum routing model since we show almost matching corresponding quantum message lower bounds. Our results significantly improve on the prior work of [PODC 2025], who presented distributed quantum algorithms under the same model that had a message complexity of O~(mn)\tilde{O}(\sqrt{mn})O~(mn​) for leader election. Our algorithms demonstrate the significant communication advantage that quantum routing has over classical in distributed computing, since Ω(m)Ω(m)Ω(m) is a well-established classical message lower bound for leader election, broadcast, MST, and BFS that applies even to randomized Monte-Carlo algorithms [JACM 2015]. Thus, our quantum algorithms can, in general, give a quadratic advantage in the communication cost for these fundamental problems. A main technical tool we use to design our distributed algorithms is quantum walks based on electric networks. We posit a framework for using quantum walks in the distributed setting to design communication-efficient distributed quantum algorithms. Our framework can be used as a black box to significantly reduce communication costs and may be of independent interest. Additionally, our lower-bound technique for establishing distributed quantum message lower bounds can also be applied to other problems.
The quantum Fourier transform (QFT) is a crucial subroutine in many quantum algorithms. In this paper, we study the exact lower bound problem of CNOT gate complexity for fault-tolerant QFT. First, we consider approximating the ancilla-free controlled-RkR_kRk​ in the QFT logical circuit with a standard set of universal gates, aiming to minimize the number of T gates. Various single-qubit gates are generated in addition to CNOT gates when the controlled-RkR_kRk​ is decomposed in different ways, we propose an algorithm that combines numerical and analytical methods to exactly compute the minimum T gate count for approximating any single-qubit gate with any given accuracy. Afterwards, we prove that the exact lower bound problem of T gate complexity for the QFT is NP-complete. Furthermore, we provide the transversal implementation of universal quantum gates and prove that it has the minimum number of CNOT gates and analyze the minimum CNOT count for transversally implementing the T gate. We then exactly compute the exact lower bound of CNOT gate complexity for fault-tolerant QFT with the current maximum fault-tolerant accuracy 10^{-2}. Our work can provide a reference for designing algorithms based on active defense in a quantum setting.
In communication complexity-like problems, previous studies have shown either an exponential quantum advantage or an unbounded quantum advantage with an exponentially large input set Θ ( 2 n ) bit with respect to classical communication Θ ( n ) bit. In the former, the quantum and classical separation grows exponentially in input while the latter's quantum communication resource is a constant. Remarkably, it was still open whether an unbounded quantum advantage exists while the inputs do not scale exponentially. Here we answer this question affirmatively using an input size of optimal order. Considering two variants as tasks: (1) distributed computation of relation and (2) , we study the one-way zero-error communication complexity of a relation induced by a distributed clique labeling problem for orthogonality graphs. While we prove no quantum advantage in the first task, we show an in relation reconstruction without public coins. Specifically, for a class of graphs with order m , the quantum complexity is Θ ( 1 ) while the classical complexity is Θ ( log 2 m ) . Remarkably, the input size is Θ ( log 2 m ) bit and the order of its scaling with respect to classical communication is . This is exponentially better compared to previous works. Additionally, we prove a lower bound (linear in the number of maximum cliques) on the amount of classical public coin necessary to overcome the separation in the scenario of restricted communication and connect this to the existence of orthogonal arrays. Finally, we highlight some applications of this task to semi-device-independent dimension witnessing as well as to the detection of mutually unbiased bases.
This paper investigates the capacity of a continuously distributed quantum network. A mathematical model of a multihop quantum communication process is given for capacity analysis. Our model assumes nnn nodes in a unit square, and both a capacity upper bound for arbitrarily distributed quantum networks and a constructed capacity lower bound for randomly distributed quantum networks are obtained as $n\ensuremath{\rightarrow}\ensuremath{\infty}$. According to our results, the capacity in arbitrarily distributed networks is proportional to nnn while capacity in randomly distributed networks is independent of nnn. Moreover, our findings exhibit the bounds on quantum network capacity and could open a door to performance analysis for future quantum networking.