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

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

Kosuke Matsui, Jun-Yi Wu, Min-Hsiu Hsieh, Mio Murao

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
15 pages, 6 figures, 1 table

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

Entanglement-efficient bipartite-distributed quantum computing

Jun-Yi Wu, Kosuke Matsui, Tim Forrer +5 more

In noisy intermediate-scale quantum computing, the limited scalability of a single quantum processing unit (QPU) can be extended through distributed quantum computing (DQC), in which one can implement global operations over two QPUs by entanglement-assisted local operations and classical communication. To facilitate this type of DQC in experiments, we need an entanglement-efficient protocol. To this end, we extend the protocol in [Eisert et. al., PRA, 62:052317(2000)] implementing each nonlocal controlled-unitary gate locally with one maximally entangled pair to a packing protocol, which can pack multiple nonlocal controlled-unitary gates locally using one maximally entangled pair. In particular, two types of packing processes are introduced as the building blocks, namely the distributing processes and embedding processes. Each distributing process distributes corresponding gates locally with one entangled pair. The efficiency of entanglement is then enhanced by embedding processes, which merge two non-sequential distributing processes and hence save the entanglement cost. We show that the structure of distributability and embeddability of a quantum circuit can be fully represented by the corresponding packing graphs and conflict graphs. Based on these graphs, we derive heuristic algorithms for finding an entanglement-efficient packing of distributing processes for a given quantum circuit to be implemented by two parties. These algorithms can determine the required number of local auxiliary qubits in the DQC. We apply these algorithms for bipartite DQC of unitary coupled-cluster circuits and find a significant reduction of entanglement cost through embeddings. This method can determine a constructive upper bound on the entanglement cost for the DQC of quantum circuits.

arXiv:2212.12688•Quantum•Dec 5, 2023•32 citations

Advantage in distributed quantum computing with slow interconnects

Evan E Dobbs, Nicolas Delfosse, Aharon Brodutch

The main bottleneck for distributed quantum computing is the rate at which entanglement is produced between quantum processing units (QPUs). In this work, we prove that multiple QPUs connected through slow interconnects can outperform a monolithic architecture made with a single QPU. We consider a distributed quantum computing model with the following assumptions: (1) each QPU is linked to only two other QPUs, (2) each link produces only one Bell pair at a time, (3) the time to generate a Bell pair is $τ_e$ times longer than the gate time. We propose a distributed version of the CliNR partial error correction scheme respecting these constraints and we show through circuit level simulations that, even if the entanglement generation time $τ_e$ is up to five times longer than the gate time, distributed CliNR can achieve simultaneously a lower logical error rate and a shorter depth than both the direct implementation and the monolithic CliNR implementation of random Clifford circuits. In the asymptotic regime, we relax assumption (2) and we prove that links producing $O(t/\ln t)$ Bell pairs in parallel, where $t$ is the number of QPUs, is sufficient to avoid stalling distributed CliNR, independently of the number of qubits per QPU. This demonstrates the potential of distributed CliNR for near-term multi-QPU devices. Moreover, we envision a distributed quantum superiority experiment based on the conjugated Clifford circuits of Bouland, Fitzsimons and Koh implemented with distributed CliNR.

quant-pharXiv:2512.10693•Dec 12, 2025•0 citations

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

Network-Assisted Collective Operations for Efficient Distributed Quantum Computing

Iago F. Llovo, Guillermo Díaz-Camacho, Natalia Costas +1 more

Distributed quantum computing relies on coordinated operations between remote quantum processing units (QPUs), yet most existing work either assumes full connectivity, unrealistic for large networks, or relies on entanglement swapping. To mitigate the overhead of communication, we propose a scheme for the distribution of collective quantum operations among remote quantum processing units by exploiting distributed fan-out operations to a central node in network architectures similar to those used for high-performance computing, which requires only pre-shared entanglement, local operations and classical communication. We show that a general diagonal gate can be distributed among any number of nodes and provide the ebit cost bounds. For a single distributed multicontrolled gate, this amounts to a single additional Bell pair over the theoretically optimal calculation with all-to-all pre-shared entanglement, demonstrating better scalability when compared to current proposals based on entanglement swapping through a network. We provide a recipe for the lumped distribution of gates such as arbitrarily-sized Toffoli and multicontrolled Z, and$R_{zz}(\theta)$gates. Finally, we provide an exact implementation of a distributed Grover's search algorithm using this protocol to partition the circuit, with Bell pair cost growing linearly with the number of Grover iterations and the number of partitions, and show how these techniques can be applied to other algorithms such as QAOA. Our results show that alternative approaches to entanglement swapping can provide major benefits in distributed quantum computing, pointing to promising avenues for future research.

arXiv:2502.19118•IEEE Transactions on Quantum Engineering•Jan 1, 2025•1 citation

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
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.
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.
In noisy intermediate-scale quantum computing, the limited scalability of a single quantum processing unit (QPU) can be extended through distributed quantum computing (DQC), in which one can implement global operations over two QPUs by entanglement-assisted local operations and classical communication. To facilitate this type of DQC in experiments, we need an entanglement-efficient protocol. To this end, we extend the protocol in [Eisert et. al., PRA, 62:052317(2000)] implementing each nonlocal controlled-unitary gate locally with one maximally entangled pair to a packing protocol, which can pack multiple nonlocal controlled-unitary gates locally using one maximally entangled pair. In particular, two types of packing processes are introduced as the building blocks, namely the distributing processes and embedding processes. Each distributing process distributes corresponding gates locally with one entangled pair. The efficiency of entanglement is then enhanced by embedding processes, which merge two non-sequential distributing processes and hence save the entanglement cost. We show that the structure of distributability and embeddability of a quantum circuit can be fully represented by the corresponding packing graphs and conflict graphs. Based on these graphs, we derive heuristic algorithms for finding an entanglement-efficient packing of distributing processes for a given quantum circuit to be implemented by two parties. These algorithms can determine the required number of local auxiliary qubits in the DQC. We apply these algorithms for bipartite DQC of unitary coupled-cluster circuits and find a significant reduction of entanglement cost through embeddings. This method can determine a constructive upper bound on the entanglement cost for the DQC of quantum circuits.
The main bottleneck for distributed quantum computing is the rate at which entanglement is produced between quantum processing units (QPUs). In this work, we prove that multiple QPUs connected through slow interconnects can outperform a monolithic architecture made with a single QPU. We consider a distributed quantum computing model with the following assumptions: (1) each QPU is linked to only two other QPUs, (2) each link produces only one Bell pair at a time, (3) the time to generate a Bell pair is τeτ_eτe​ times longer than the gate time. We propose a distributed version of the CliNR partial error correction scheme respecting these constraints and we show through circuit level simulations that, even if the entanglement generation time τeτ_eτe​ is up to five times longer than the gate time, distributed CliNR can achieve simultaneously a lower logical error rate and a shorter depth than both the direct implementation and the monolithic CliNR implementation of random Clifford circuits. In the asymptotic regime, we relax assumption (2) and we prove that links producing O(t/ln⁡t)O(t/\ln t)O(t/lnt) Bell pairs in parallel, where ttt is the number of QPUs, is sufficient to avoid stalling distributed CliNR, independently of the number of qubits per QPU. This demonstrates the potential of distributed CliNR for near-term multi-QPU devices. Moreover, we envision a distributed quantum superiority experiment based on the conjugated Clifford circuits of Bouland, Fitzsimons and Koh implemented with distributed CliNR.
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 computing relies on coordinated operations between remote quantum processing units (QPUs), yet most existing work either assumes full connectivity, unrealistic for large networks, or relies on entanglement swapping. To mitigate the overhead of communication, we propose a scheme for the distribution of collective quantum operations among remote quantum processing units by exploiting distributed fan-out operations to a central node in network architectures similar to those used for high-performance computing, which requires only pre-shared entanglement, local operations and classical communication. We show that a general diagonal gate can be distributed among any number of nodes and provide the ebit cost bounds. For a single distributed multicontrolled gate, this amounts to a single additional Bell pair over the theoretically optimal calculation with all-to-all pre-shared entanglement, demonstrating better scalability when compared to current proposals based on entanglement swapping through a network. We provide a recipe for the lumped distribution of gates such as arbitrarily-sized Toffoli and multicontrolled Z, andRzz(θ)R_{zz}(\theta)Rzz​(θ)gates. Finally, we provide an exact implementation of a distributed Grover's search algorithm using this protocol to partition the circuit, with Bell pair cost growing linearly with the number of Grover iterations and the number of partitions, and show how these techniques can be applied to other algorithms such as QAOA. Our results show that alternative approaches to entanglement swapping can provide major benefits in distributed quantum computing, pointing to promising avenues for future research.
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.