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.
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), wherendenotes 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>2is a fixed fraction ofn, then the lower bound becomes linear.
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(4n) communication bound. Considering k pairwise-connected processors (each with n/k data qubits and m ancillas), we prove the communication complexity satisfies O(max{4(1−1/k)n−m,n}) -- for example, O(2n) 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.
We study lower bounds for quantum distributed computing, where a set of nodes (representing quantum computers) interconnected by an underlying network consisting of (bandwidth-restricted) links, communicate using quantum communication. Nodes have unlimited computational power and may share an unlimited number of entangled qubits. Our main contribution is a simple uniform technique for proving lower bounds for quantum distributed algorithms. In particular, we identify a new quantum communication model called the Server model which provides a connection between distributed algorithms and communication complexity: it is strong enough to capture the hardness of several distributed computing problems, while weak enough that several hard problems in two-party communication complexity remain hard; to this end, we identify a set of communication complexity techniques that can be carried over to the Server model, namely techniques based on nonlocal games. We show that these techniques serve as a fundamental tool in proving lower bounds in quantum distributed computing. The new techniques help us to prove several non-trivial quantum distributed lower bounds (which are the first-known quantum bounds for fundamental global problems such as minimum spanning tree, shortest paths etc.), some of which are new even in the classical setting. First, it allows us to show that all previous classical lower bounds of more than twenty verification and optimization graph problems in [Das Sarma et al., STOC 11] also hold in the quantum setting. Many of these bounds are tight, implying a large class of problems that do not gain an advantage from quantum effects. Our results also imply the following new results in the classical communication models: (1) the first randomized lower bounds for Hamiltonian cycle and spanning tree verification problems in both the distributed computing and the communication complexity model, answering the open problem of Das Sarma et al. and subsuming many bounds in [Babai, Frankl, and Simon, FOCS 96], and (2) the first lower bound that is tight for all weight aspect ratios, matching previous upper bounds of [Elkin, STOC 04]. Submitted for a Regular Presentation. The full version of this paper can be found as [15] at http://arxiv.org/abs/1207.5211. ∗Department of Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel. E-mail: elkinm@cs.bgu.ac.il. †Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Centre for Quantum Technologies, National University of Singapore, Singapore 117543. E-mail: hklauck@gmail.com. Research at the Centre for Quantum Technologies is funded by the Singapore Ministry of Education and the National Research Foundation. ‡Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371. Work partially done while at University of Vienna, Austria. E-mail: danupon@gmail.com. §Division of Mathematical Sciences, Nanyang Technological University, Singapore 637371 & Department of Computer Science, Brown University, Providence, RI 02912, USA. E-mail: gopalpandurangan@gmail.com. Supported in part by the following research grants: Nanyang Technological University grant M58110000, Singapore MOE Academic Research Fund (AcRF) Tier 2 grant MOE2010-T2-2-082, and a grant from the US-Israeli Binational Science Foundation (BSF).
We study the communication complexity of a number of graph properties where the edges of the graph G are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: * An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. * A deterministic upper bound of O(n^{3/2}log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. * A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for the quantum communication complexity of this problem. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if G is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.
A major open question in communication complexity is if randomized and quantum communication are polynomially related for all total functions. So far, no gap larger than a power of two is known, despite significant efforts. We examine this question in the number-on-the-forehead model of multiparty communication complexity. We show that essentially all lower bounds known on randomized complexity in this model also hold for quantum communication. This includes bounds of size Omega(n/2k) for the k-party complexity of explicit functions, bounds for the generalized inner product function, and recent work on the multiparty complexity of disjointness. To the best of our knowledge, these are the first lower bounds of any kind on quantum communication in the general number-on-the-forehead model. We show this result in the following way. In the two-party case, there is a lower bound on quantum communication complexity in terms of a norm gamma2, which is known to subsume nearly all other techniques in the literature. For randomized complexity there is another natural bound in terms of a different norm mu which is also one of the strongest techniques available. A deep theorem in functional analysis, Grothendieck's inequality, implies that gamma2and mu are equivalent up to a constant factor. This connection is one of the major obstacles to showing a larger gap between randomized and quantum communication complexity in the two-party case. The lower bound technique in terms of the norm mu was recently extended to the multiparty number-on-the-forehead model. Here we show how the gamma2norm can be also extended to lower bound quantum multiparty complexity. Surprisingly, even in this general setting the two lower bounds, on quantum and classical communication, are still very closely related. This implies that separating quantum and classical communication in this setting will require the development of new techniques. The relation between these extensions of mu and gamma2is proved by a multi-dimensional version of Grothendieck's inequality.
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⋅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) to linear 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.
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n+log log(1//spl epsiv/)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2/sup n/ with error bounded by /spl epsiv/. Thus, even for exponentially small error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with constant error. Moreover, our circuits have size O(n log(n//spl epsiv/)). As an application of this depth bound, we show that P. Shor's (1997) factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial size, in combination with classical polynomial-time pre- and postprocessing. Next, we prove an /spl Omega/(log n) lower bound on the depth complexity of approximations of the QFT with constant error. This implies that the above upper bound is asymptotically tight (for a reasonable range of values of /spl epsiv/). We also give an upper bound of O(n(log n)/sup 2/ log log n) on the circuit size of the exact QFT modulo 2/sup n/, for which the best previous bound was O(n/sup 2/). Finally, based on our circuits for the QFT with power-of-2 moduli, we show that the QFT with respect to an arbitrary modulus m can be approximated with accuracy /spl epsiv/ with circuits of depth O((log log m)(log log 1//spl epsiv/)) and size polynomial in log m+log(1//spl epsiv/).