Communication Complexity of Distributed Unitary Synthesis
This work provides fundamental communication complexity bounds for distributed quantum computing, which is crucial for scaling quantum processors.
The paper studies the communication complexity of implementing unitaries in distributed quantum processors, measured by the number of nonlocal two-qubit gates. For general n-qubit unitaries, they improve the trivial O(4^n) bound to O(max{4^{(1-1/k)n - m}, n}) for k processors with m ancillas each, and show it is tight. For special unitaries like QFT and Clifford circuits, they achieve linear upper bounds in the exact model, and for QFT a logarithmic bound in the approximation model.
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.