Space-Bounded Communication Complexity of Unitaries

• URL: http://arxiv.org/abs/2511.04250v1
• Date: Thu, 06 Nov 2025 10:35:28 GMT
• Title: Space-Bounded Communication Complexity of Unitaries
• Authors: Longcheng Li, Xiaoming Sun, Jialin Zhang, Jiadong Zhu,
• Abstract summary: We study space-bounded communication complexity for unitary implementation in distributed quantum processors.<n>For general $n$-qubit unitaries, we improve upon the trivial $O(4n)$ communication bound.<n>For special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity.
• Score: 7.120902966697645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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

• Scalable Multi-QPU Circuit Design for Dicke State Preparation: Optimizing Communication Complexity and Local Circuit Costs [13.575071625377097]
  The number of qubits available on a single quantum processing unit (QPU) is limited.<n>We investigate the distributed preparation of large-qubit Dicke states $D(n,k)$ across a general number $p$ of QPUs.<n>To the best of our knowledge, this is the first construction to simultaneously achieve logarithmic communication complexity and circuit size and depth.
  arXiv  Detail & Related papers  (2026-01-28T09:00:38Z)
• Analytical construction of $(n, n-1)$ quantum random access codes saturating the conjectured bound [0.0]
  Quantum Random Access Codes (QRACs) embody the fundamental trade-off between the compressibility of information into limited quantum resources.<n>We establish an analytical construction method for $(n, n-1)$-QRACs by using an explicit operator formalism.<n>We present a systematic algorithm to decompose the derived optimal POVM into standard quantum gates.
  arXiv  Detail & Related papers  (2026-01-27T04:43:43Z)
• Quantum Communication Complexity of L2-Regularized Linear Regression Protocols [0.0]
  This paper investigates distributed linear regression in the quantum coordinator model.<n>We propose improved and extended quantum protocols for solving both ordinary (unregularized) and L2-regularized (Tikhonov) least squares problems.
  arXiv  Detail & Related papers  (2025-08-22T07:07:14Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Communication-efficient Quantum Algorithm for Distributed Machine Learning [14.546892420890943]
  Our quantum algorithm finds the model parameters with a communication complexity of $O(fraclog_2(N)epsilon)$, where $N$ is the number of data points and $epsilon$ is the bound on parameter errors. The building block of our algorithm, the quantum-accelerated estimation of distributed inner product and Hamming distance, could be further applied to various tasks in distributed machine learning to accelerate communication.
  arXiv  Detail & Related papers  (2022-09-11T15:03:58Z)
• Halving the cost of quantum multiplexed rotations [0.0]
  We improve the number of $T$ gates needed for a $b$-bit approximation of a multiplexed quantum gate with $c$ controls. Our results roughly halve the cost of state-of-art electronic structure simulations based on qubitization of double-factorized or tensor-hypercontracted representations.
  arXiv  Detail & Related papers  (2021-10-26T06:49:44Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions [0.9634136878988853]
  Power-law interactions with strength decaying as $1/ralpha$ in the distance provide an experimentally realizable resource for information processing. We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets. We show that power-law systems with $alpha le D$ are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable.
  arXiv  Detail & Related papers  (2020-07-01T18:00:00Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.