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.

AI Summary

The paper asks whether bipartite unitaries can be implemented with low entanglement consumption when each quantum processor has only constant auxiliary-qubit space. It considers exact, deterministic LOCC protocols supplied with perfect Bell pairs, allowing mid-circuit measurement, reset, and qubit reuse. Entanglement cost counts consumed Bell pairs; auxiliary hardware for generating them is excluded from the space accounting. For every bipartite Clifford unitary $U_c$, it establishes an implementation consuming exactly $\log_2\operatorname{OpSch}(U_c)$ Bell pairs, attaining the operator-Schmidt-rank lower bound with at most two auxiliary qubits per processor. The construction uses the identity $\log_2\operatorname{OpSch}(U_c)=\operatorname{rank}S^{BA}$ for the Clifford’s binary symplectic representation. A recursive rank-reduction procedure decomposes the unitary into local Clifford operations and locally dressed CZ and SWAP blocks whose entanglement costs add to the lower bound. Implementing these blocks sequentially permits auxiliary-qubit reuse. For a unitary $U$ given by an exact Clifford+$T$ decomposition with $T$-count $t$, it gives the same space bound and Bell-pair cost $K\leq\lfloor\log_2\operatorname{OpSch}(U)\rfloor+2t$. This follows by collecting Clifford factors, implementing each resulting Pauli rotation with at most one Bell pair, and bounding the collected Clifford’s operator Schmidt rank by submultiplicativity. The non-Clifford bound is not generally tight and depends on the supplied decomposition. Determining minimum non-Clifford entanglement costs, and whether space constraints increase them, remains open; even the unrestricted-space minimum is not characterized in general.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
15 pages, 6 figures, 1 table

Related papers

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•43 citations

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•1 citation

Asymptotic Compressibility of Entanglement and Classical Communication in Distributed Quantum Computation

Eyuri Wakakuwa, Mio Murao

We consider implementations of a bipartite unitary on many pairs of unknown input states by local operation and classical communication assisted by shared entanglement. We investigate to what extent the entanglement cost and the classical communication cost can be compressed by allowing nonzero but vanishing error in the asymptotic limit of infinite pairs. We show that a lower bound on the minimal entanglement cost, the forward classical communication cost, and the backward classical communication cost per pair is given by the Schmidt strength of the unitary. We also prove that an upper bound on these three kinds of the cost is given by the amount of randomness that is required to partially decouple a tripartite quantum state associated with the unitary. In the proof, we construct a protocol in which quantum state merging is used. For generalized Clifford operators, we show that the lower bound and the upper bound coincide. We then apply our result to the problem of distributed compression of tripartite quantum states, and derive a lower and an upper bound on the optimal quantum communication rate required therein.

arXiv:1310.3991•Oct 15, 2013•6 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•2 citations

A Coding Theorem for Bipartite Unitaries in Distributed Quantum Computation

Eyuri Wakakuwa, Akihito Soeda, Mio Murao

We analyze implementations of bipartite unitaries by means of local operations and classical communication (LOCC) assisted by shared entanglement. We employ concepts and techniques developed in the quantum Shannon theory to study an asymptotic scenario, in which two distant parties perform the same bipartite unitary on infinitely many pairs of inputs. We analyze minimum cost of entanglement and classical communication per copy. For two-round LOCC protocols, we derive a single-letter formula for the minimum cost of entanglement and classical communication, under an additional requirement that the error converges to zero faster than 1/n4, where n is the number of input pairs. The formula is given by the “Markovianizing cost” of a tripartite state associated with the unitary, which can be computed by a finite-step algorithm. We also derive a lower bound on the minimum cost of resources, which applies for protocols with arbitrary number of rounds.

arXiv:1505.04352•IEEE Transactions on Information Theory•May 29, 2017•22 citations

Information Theoretical Analysis of Distributed Quantum Computation

若桑, 江友里

Distributed quantum computation is a task in which many distant parties perform a large quantum computation in collaboration with each other, by using classical communication, quantum communication or shared entanglement as resources.In this thesis, we consider one of the simplest nontrivial task of distributed quantum computation, that is, implementation of bipartite unitary by LOCC (local operations and classical communication) assisted by shared entanglement.Here, two input states are distributed over two distant parties.Contrary to previous researches, we consider an asymptotic scenario in which the two parties perform the same bipartite unitary on infinitely many independent input pairs.We analyze the minimum amount of resources required for the task by exploiting concepts and techniques developed in the field of quantum Shannon theory, which has originally been developed to analyze quantum communication.As a tool for analyzing distributed quantum computation, we first introduce a task that we call Markovianization.Markovianization is a task in which a tripartite pure state is transformed to a state called quantum Markov chain, by a randomizing operation on one of the three subsystems.We derive the minimum cost of randomness required for Markovianization (Markovianizing cost) by exploiting a novel decomposition of a Hilbert space introduced in the context of quantum cryptography.We then apply the obtained result to distributed quantum computation.We mainly consider implementation of bipartite unitaries by entanglement-assisted LOCC protocols consisting of three steps, called one-round protocols.This is the first nontrivial case because it is not possible to implement bipartite unitaries by protocols consisting of only one or two steps.Our main result is that we derive the minimum costs of entanglement and classical communication.We show that the minimum costs are given by the Markovianizing cost of a tripartite state associated with the unitary.The result indicates that information about input states of computation is divided into three components: one of which only information of amplitude in a basis is required for computation (information of phase is not), another of which both amplitude and phase information are required, and the other of which no information is involved in computation.Our construction of a protocol that requires the smallest amount of resources is based on this decomposition.We also propose a method to compute the Markovianizing cost of a state associated with the unitary.We also consider two-round protocols, that is, protocols consisting of concatenation of two one-round protocols, for two-qubit controlled unitaries.We show that, for a particular class of two-qubit controlled unitaries, the minimum entanglement cost in two-round protocols is strictly smaller than that in one-round protocols.This result is the first reported case that indicates a property of a trade-off relation between entanglement requirement and the number of turns in entanglement-assisted LOCC tasks.The research in this thesis opens a possibility to build a new bridge between quantum computation theory and quantum communication theory, which are the two largest subfield of quantum information theory, by analyzing a problem in the former using concepts and techniques developed in the latter.

•Mar 24, 2015•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.
The paper asks whether bipartite unitaries can be implemented with low entanglement consumption when each quantum processor has only constant auxiliary-qubit space. It considers exact, deterministic LOCC protocols supplied with perfect Bell pairs, allowing mid-circuit measurement, reset, and qubit reuse. Entanglement cost counts consumed Bell pairs; auxiliary hardware for generating them is excluded from the space accounting.
For every bipartite Clifford unitary UcU_cUc​, it establishes an implementation consuming exactly log⁡2OpSch⁡(Uc)\log_2\operatorname{OpSch}(U_c)log2​OpSch(Uc​) Bell pairs, attaining the operator-Schmidt-rank lower bound with at most two auxiliary qubits per processor. The construction uses the identity log⁡2OpSch⁡(Uc)=rank⁡SBA\log_2\operatorname{OpSch}(U_c)=\operatorname{rank}S^{BA}log2​OpSch(Uc​)=rankSBA for the Clifford’s binary symplectic representation. A recursive rank-reduction procedure decomposes the unitary into local Clifford operations and locally dressed CZ and SWAP blocks whose entanglement costs add to the lower bound. Implementing these blocks sequentially permits auxiliary-qubit reuse.
For a unitary UUU given by an exact Clifford+TTT decomposition with TTT-count ttt, it gives the same space bound and Bell-pair cost K≤⌊log⁡2OpSch⁡(U)⌋+2tK\leq\lfloor\log_2\operatorname{OpSch}(U)\rfloor+2tK≤⌊log2​OpSch(U)⌋+2t. This follows by collecting Clifford factors, implementing each resulting Pauli rotation with at most one Bell pair, and bounding the collected Clifford’s operator Schmidt rank by submultiplicativity.
The non-Clifford bound is not generally tight and depends on the supplied decomposition. Determining minimum non-Clifford entanglement costs, and whether space constraints increase them, remains open; even the unrestricted-space minimum is not characterized in general.
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.
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.
We consider implementations of a bipartite unitary on many pairs of unknown input states by local operation and classical communication assisted by shared entanglement. We investigate to what extent the entanglement cost and the classical communication cost can be compressed by allowing nonzero but vanishing error in the asymptotic limit of infinite pairs. We show that a lower bound on the minimal entanglement cost, the forward classical communication cost, and the backward classical communication cost per pair is given by the Schmidt strength of the unitary. We also prove that an upper bound on these three kinds of the cost is given by the amount of randomness that is required to partially decouple a tripartite quantum state associated with the unitary. In the proof, we construct a protocol in which quantum state merging is used. For generalized Clifford operators, we show that the lower bound and the upper bound coincide. We then apply our result to the problem of distributed compression of tripartite quantum states, and derive a lower and an upper bound on the optimal quantum communication rate required therein.
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.
We analyze implementations of bipartite unitaries by means of local operations and classical communication (LOCC) assisted by shared entanglement. We employ concepts and techniques developed in the quantum Shannon theory to study an asymptotic scenario, in which two distant parties perform the same bipartite unitary on infinitely many pairs of inputs. We analyze minimum cost of entanglement and classical communication per copy. For two-round LOCC protocols, we derive a single-letter formula for the minimum cost of entanglement and classical communication, under an additional requirement that the error converges to zero faster than 1/n4, where n is the number of input pairs. The formula is given by the “Markovianizing cost” of a tripartite state associated with the unitary, which can be computed by a finite-step algorithm. We also derive a lower bound on the minimum cost of resources, which applies for protocols with arbitrary number of rounds.
Distributed quantum computation is a task in which many distant parties perform a large quantum computation in collaboration with each other, by using classical communication, quantum communication or shared entanglement as resources.In this thesis, we consider one of the simplest nontrivial task of distributed quantum computation, that is, implementation of bipartite unitary by LOCC (local operations and classical communication) assisted by shared entanglement.Here, two input states are distributed over two distant parties.Contrary to previous researches, we consider an asymptotic scenario in which the two parties perform the same bipartite unitary on infinitely many independent input pairs.We analyze the minimum amount of resources required for the task by exploiting concepts and techniques developed in the field of quantum Shannon theory, which has originally been developed to analyze quantum communication.As a tool for analyzing distributed quantum computation, we first introduce a task that we call Markovianization.Markovianization is a task in which a tripartite pure state is transformed to a state called quantum Markov chain, by a randomizing operation on one of the three subsystems.We derive the minimum cost of randomness required for Markovianization (Markovianizing cost) by exploiting a novel decomposition of a Hilbert space introduced in the context of quantum cryptography.We then apply the obtained result to distributed quantum computation.We mainly consider implementation of bipartite unitaries by entanglement-assisted LOCC protocols consisting of three steps, called one-round protocols.This is the first nontrivial case because it is not possible to implement bipartite unitaries by protocols consisting of only one or two steps.Our main result is that we derive the minimum costs of entanglement and classical communication.We show that the minimum costs are given by the Markovianizing cost of a tripartite state associated with the unitary.The result indicates that information about input states of computation is divided into three components: one of which only information of amplitude in a basis is required for computation (information of phase is not), another of which both amplitude and phase information are required, and the other of which no information is involved in computation.Our construction of a protocol that requires the smallest amount of resources is based on this decomposition.We also propose a method to compute the Markovianizing cost of a state associated with the unitary.We also consider two-round protocols, that is, protocols consisting of concatenation of two one-round protocols, for two-qubit controlled unitaries.We show that, for a particular class of two-qubit controlled unitaries, the minimum entanglement cost in two-round protocols is strictly smaller than that in one-round protocols.This result is the first reported case that indicates a property of a trade-off relation between entanglement requirement and the number of turns in entanglement-assisted LOCC tasks.The research in this thesis opens a possibility to build a new bridge between quantum computation theory and quantum communication theory, which are the two largest subfield of quantum information theory, by analyzing a problem in the former using concepts and techniques developed in the latter.