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:2511.04250 · IEEE Transactions on Information Theory

Space-Bounded Communication Complexity of Unitaries

Longcheng Li, Xiaoming Sun, Jialin Zhang, Jiadong Zhu

quant-phcs.CRSubmitted Nov 6, 2025• Announced Nov 7, 2025• 0 citations
v1 · Nov 6, 2025v2 · Jun 13, 2026
arXivHTMLPDF

Abstract

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 communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization. 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 distributed quantum computing (DQC) systems.

Related papers

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

Ali Ebnenasir

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Scalable Multi-QPU Circuit Design for Dicke State Preparation: Optimizing Communication Complexity and Local Circuit Costs

Ziheng Chen, Junhong Nie, Xiaoming Sun +2 more

Preparing large-qubit Dicke states is of broad interest in quantum computing and quantum metrology. However, the number of qubits available on a single quantum processing unit (QPU) is limited -- motivating the distributed preparation of such states across multiple QPUs as a practical approach to scalability. In this article, we investigate the distributed preparation of $n$-qubit $k$-excitation Dicke states $D(n,k)$ across a general number $p$ of QPUs, presenting a distributed quantum circuit (each QPU hosting approximately $\lceil n/p \rceil$ qubits) that prepares the state with communication complexity $O(p \log k)$, circuit size $O(nk)$, and circuit depth $O\left(p^2 k + \log k \log (n/k)\right)$. To the best of our knowledge, this is the first construction to simultaneously achieve logarithmic communication complexity and polynomial circuit size and depth. We also establish a lower bound on the communication complexity of $p$-QPU distributed state preparation for a general target state. This lower bound is formulated in terms of the canonical polyadic rank (CP-rank) of a tensor associated with the target state. For the special case $p = 2$, we explicitly compute the CP-rank corresponding to the Dicke state $D(n,k)$ and derive a lower bound of $\lceil\log (k + 1)\rceil$, which shows that the communication complexity of our construction matches this fundamental limit.

quant-pharXiv:2601.20393•Jan 29, 2026•0 citations

Reducing the Entanglement Cost of Distributed Bipartite Quantum Computation with Constant Qubit Overhead

Kosuke Matsui, Jun-Yi Wu, Min-Hsiu Hsieh +1 more

Distributed quantum computation connects multiple quantum processing units (QPUs) through quantum communication to jointly perform large-scale quantum computations. Since the number of qubits available at each QPU is limited, it is important to reduce quantum communication while keeping the qubit overhead small. To this end, we study an entanglement-assisted model, in which entanglement consumption serves as a measure of quantum communication cost. For exact deterministic implementations in this model, the operator Schmidt rank of the target bipartite unitary provides a general lower bound on entanglement cost when qubit overhead is unrestricted. However, it has remained unclear how closely this bound can be approached with constant qubit overhead. In this work, we show that this lower bound is attainable for every bipartite Clifford unitary using at most two auxiliary qubits per QPU. In addition, for non-Clifford unitaries specified by exact Clifford+$T$ decompositions with $T$-count $t$, we construct implementations with the same qubit overhead whose entanglement cost is at most $2t$ Bell pairs above this lower bound.

quant-pharXiv:2609.39865•Oct 1, 2026•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

Towards an Optimally Distributed Quantum Fourier Transform Circuit

Zachary Vernec, Michael Silver, Hans-Arno Jacobsen

A promising avenue for scaling quantum computing is to connect quantum processing units (QPUs) by generating entanglement between them. This requires circuit partitioning: partially rewriting quantum circuits to run on a distributed quantum system using quantum teleportation protocols, while preserving the unitary operation implemented by the circuit. The key metric to minimize when partitioning is the e-bit count, defined as the number of maximally entangled qubit pairs that must be generated between QPUs. We focus on partitioning the quantum Fourier transform (QFT) circuit, which is widely used as a subroutine in quantum algorithms such as quantum phase estimation and arithmetic circuits. Specifically, we present an optimal gate-packing-based partitioning scheme under bounded communication ancilla constraints, as well as a novel detached-gate-based partitioning scheme that achieves optimal e-bit consumption when ancilla availability is unrestricted. We compare these schemes against prior analytical partitioning approaches for the QFT and evaluate them against partitions produced by general-purpose circuit partitioning algorithms. We further validate our approach by implementing the bounded-ancilla circuits on quantum hardware.

quant-pharXiv:2606.18494•Jun 18, 2026•0 citations

Clifford Circuit Synthesis for Distributed Quantum Architectures with Arbitrary Network Topology

Tuomas Laakkonen

To achieve large-scale fault-tolerant quantum computation, it may be easier to combine many small sets of qubits than to construct a single large set. For example via quantum error correction with block codes, or distributed quantum processors utilizing shared entanglement. In these regimes, the time or error budget of the overall quantum computation may be dominated by non-local operations. Hence, it is worthwhile to minimize the number of these operations. We consider the case where both non-local and local connectivity may be arbitrarily restricted, and give an asymptotically optimal synthesis method for distributed CNOT and Clifford circuits, based on block-matrix Gaussian elimination. We extend this to all Clifford+RZ circuits by generalizing the Pauli exponential circuit representation; this naturally integrates with existing methods for optimizing T-count. As an application, we show how to implement CNOT circuits in a CSS code encoding n logical qubits in k blocks using O(nk) inter-block transversal CNOTs and intra-block Pauli measurements.

quant-pharXiv:2608.13543•Aug 14, 2026•0 citations
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 communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization.
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 distributed quantum computing (DQC) systems.
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.
Preparing large-qubit Dicke states is of broad interest in quantum computing and quantum metrology. However, the number of qubits available on a single quantum processing unit (QPU) is limited -- motivating the distributed preparation of such states across multiple QPUs as a practical approach to scalability. In this article, we investigate the distributed preparation of nnn-qubit kkk-excitation Dicke states D(n,k)D(n,k)D(n,k) across a general number ppp of QPUs, presenting a distributed quantum circuit (each QPU hosting approximately ⌈n/p⌉\lceil n/p \rceil⌈n/p⌉ qubits) that prepares the state with communication complexity O(plog⁡k)O(p \log k)O(plogk), circuit size O(nk)O(nk)O(nk), and circuit depth O(p2k+log⁡klog⁡(n/k))O\left(p^2 k + \log k \log (n/k)\right)O(p2k+logklog(n/k)). To the best of our knowledge, this is the first construction to simultaneously achieve logarithmic communication complexity and polynomial circuit size and depth. We also establish a lower bound on the communication complexity of ppp-QPU distributed state preparation for a general target state. This lower bound is formulated in terms of the canonical polyadic rank (CP-rank) of a tensor associated with the target state. For the special case p=2p = 2p=2, we explicitly compute the CP-rank corresponding to the Dicke state D(n,k)D(n,k)D(n,k) and derive a lower bound of ⌈log⁡(k+1)⌉\lceil\log (k + 1)\rceil⌈log(k+1)⌉, which shows that the communication complexity of our construction matches this fundamental limit.
Distributed quantum computation connects multiple quantum processing units (QPUs) through quantum communication to jointly perform large-scale quantum computations. Since the number of qubits available at each QPU is limited, it is important to reduce quantum communication while keeping the qubit overhead small. To this end, we study an entanglement-assisted model, in which entanglement consumption serves as a measure of quantum communication cost. For exact deterministic implementations in this model, the operator Schmidt rank of the target bipartite unitary provides a general lower bound on entanglement cost when qubit overhead is unrestricted. However, it has remained unclear how closely this bound can be approached with constant qubit overhead. In this work, we show that this lower bound is attainable for every bipartite Clifford unitary using at most two auxiliary qubits per QPU. In addition, for non-Clifford unitaries specified by exact Clifford+TTT decompositions with TTT-count ttt, we construct implementations with the same qubit overhead whose entanglement cost is at most 2t2t2t Bell pairs above this lower bound.
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.
A promising avenue for scaling quantum computing is to connect quantum processing units (QPUs) by generating entanglement between them. This requires circuit partitioning: partially rewriting quantum circuits to run on a distributed quantum system using quantum teleportation protocols, while preserving the unitary operation implemented by the circuit. The key metric to minimize when partitioning is the e-bit count, defined as the number of maximally entangled qubit pairs that must be generated between QPUs. We focus on partitioning the quantum Fourier transform (QFT) circuit, which is widely used as a subroutine in quantum algorithms such as quantum phase estimation and arithmetic circuits. Specifically, we present an optimal gate-packing-based partitioning scheme under bounded communication ancilla constraints, as well as a novel detached-gate-based partitioning scheme that achieves optimal e-bit consumption when ancilla availability is unrestricted. We compare these schemes against prior analytical partitioning approaches for the QFT and evaluate them against partitions produced by general-purpose circuit partitioning algorithms. We further validate our approach by implementing the bounded-ancilla circuits on quantum hardware.
To achieve large-scale fault-tolerant quantum computation, it may be easier to combine many small sets of qubits than to construct a single large set. For example via quantum error correction with block codes, or distributed quantum processors utilizing shared entanglement. In these regimes, the time or error budget of the overall quantum computation may be dominated by non-local operations. Hence, it is worthwhile to minimize the number of these operations. We consider the case where both non-local and local connectivity may be arbitrarily restricted, and give an asymptotically optimal synthesis method for distributed CNOT and Clifford circuits, based on block-matrix Gaussian elimination. We extend this to all Clifford+RZ circuits by generalizing the Pauli exponential circuit representation; this naturally integrates with existing methods for optimizing T-count. As an application, we show how to implement CNOT circuits in a CSS code encoding n logical qubits in k blocks using O(nk) inter-block transversal CNOTs and intra-block Pauli measurements.