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

Scalable Multi-QPU Circuit Design for Dicke State Preparation: Optimizing Communication Complexity and Local Circuit Costs

Ziheng Chen, Junhong Nie, Xiaoming Sun, Jialin Zhang, Jiadong Zhu

quant-phSubmitted Jan 28, 2026• Announced Jan 29, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

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

Depth-Efficient Quantum Circuit Synthesis for Deterministic Dicke State Preparation

Pei Yuan, Shengyu Zhang

The $n$-qubit $k$-weight Dicke states $|D^n_k\rangle$, defined as the uniform superposition of all computational basis states with exactly $k$ qubits in state $|1\rangle$, form a basis of the symmetric subspace and represent an important class of entangled quantum states with broad applications in quantum computing. We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints: 1. All-to-all qubit connectivity: our circuit has depth $O(\log(k)\log(n/k)+k)$, which improves the previous best bound of $O(k\log(n/k))$. 2. Grid qubit connectivity ($(n_1\times n_2)$-grid, $n_1\le n_2$): (a) For $k\ge n_2/n_1$, we design a circuit with depth $O(k\log(n/k)+n_2)$, surpassing the prior $O(\sqrt{nk})$ bound. (b) For $k< n_2/n_1$, we design an optimal-depth circuit with depth $O(n_2)$. Furthermore, we establish the depth lower bounds of $Ω(\log(n))$ for all-to-all qubit connectivity and $Ω(n_2)$ for $(n_1\times n_2)$-grid connectivity constraints, demonstrating the near-optimality of our constructions.

arXiv:2505.15413•May 21, 2025•16 citations

Constant-Depth Unitary Preparation of Dicke States

Malvika Raj Joshi, Francisca Vasconcelos

Dicke states serve as a critical resource in quantum metrology, communication, and computation. However, unitary preparation of Dicke states is limited to logarithmic depth in standard circuit models and existing constant-depth protocols require measurement and feed-forward. In this work, we present the first unitary, constant-depth protocols for exact Dicke state preparation. We overcome the logarithmic-depth barrier by moving beyond the standard circuit model and leveraging global interactions (native to architectures such as neutral atoms and trapped ions). Specifically, utilizing unbounded CZ gates (i.e. within the QAC$^0$ circuit class), we offer circuits for exact computation of constant-weight Dicke states, using polynomial ancillae, and approximation of weight-1 Dicke states (i.e. $W$ states), using only constant ancillae. Granted additional access to the quantum FAN-OUT operation (i.e. upgrading to the QAC$_f^0$ circuit class), we also achieve exact and clean preparation of arbitrary-weight Dicke states, with polynomial ancillae. These protocols distinguish the constant-depth capabilities of quantum architectures based on connectivity and offer a novel path toward resolving a long-standing quantum complexity conjecture.

quant-pharXiv:2601.10693•Jan 16, 2026•6 citations

Efficient circuits for leaf-separable state preparation

Sunil Vittal, Anthony Wilkie, Nika Rastegari +2 more

Efficient state preparation is a challenging and important problem in quantum computing. In this work, we present a recursive state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing ``leaf-separable" quantum states. The algorithm is built on binary partition trees, generalized weight distribution blocks (gWDBs), and leaf-level encoders. We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits. Compared to general state preparation approaches which require $O(2^n)$ CX gates, our algorithm achieves a circuit depth of $O(k\log\frac{n}{k} + 2^k)$ and uses $O(n(k+2^k))$ two-qubit gates, where $k < n$ denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.

quant-pharXiv:2511.11227•Nov 17, 2025•2 citations

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

Kosuke Matsui, Jun-Yi Wu, Min-Hsiu Hsieh +1 more

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.

quant-pharXiv:2609.39865•Oct 1, 2026•0 citations

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
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.
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.
The nnn-qubit kkk-weight Dicke states ∣Dkn⟩|D^n_k\rangle∣Dkn​⟩, defined as the uniform superposition of all computational basis states with exactly kkk qubits in state ∣1⟩|1\rangle∣1⟩, form a basis of the symmetric subspace and represent an important class of entangled quantum states with broad applications in quantum computing. We propose deterministic quantum circuits for Dicke state preparation under two commonly seen qubit connectivity constraints: 1. All-to-all qubit connectivity: our circuit has depth O(log⁡(k)log⁡(n/k)+k)O(\log(k)\log(n/k)+k)O(log(k)log(n/k)+k), which improves the previous best bound of O(klog⁡(n/k))O(k\log(n/k))O(klog(n/k)). 2. Grid qubit connectivity ((n1×n2)(n_1\times n_2)(n1​×n2​)-grid, n1≤n2n_1\le n_2n1​≤n2​): (a) For k≥n2/n1k\ge n_2/n_1k≥n2​/n1​, we design a circuit with depth O(klog⁡(n/k)+n2)O(k\log(n/k)+n_2)O(klog(n/k)+n2​), surpassing the prior O(nk)O(\sqrt{nk})O(nk​) bound. (b) For k<n2/n1k< n_2/n_1k<n2​/n1​, we design an optimal-depth circuit with depth O(n2)O(n_2)O(n2​). Furthermore, we establish the depth lower bounds of Ω(log⁡(n))Ω(\log(n))Ω(log(n)) for all-to-all qubit connectivity and Ω(n2)Ω(n_2)Ω(n2​) for (n1×n2)(n_1\times n_2)(n1​×n2​)-grid connectivity constraints, demonstrating the near-optimality of our constructions.
Dicke states serve as a critical resource in quantum metrology, communication, and computation. However, unitary preparation of Dicke states is limited to logarithmic depth in standard circuit models and existing constant-depth protocols require measurement and feed-forward. In this work, we present the first unitary, constant-depth protocols for exact Dicke state preparation. We overcome the logarithmic-depth barrier by moving beyond the standard circuit model and leveraging global interactions (native to architectures such as neutral atoms and trapped ions). Specifically, utilizing unbounded CZ gates (i.e. within the QAC0^00 circuit class), we offer circuits for exact computation of constant-weight Dicke states, using polynomial ancillae, and approximation of weight-1 Dicke states (i.e. WWW states), using only constant ancillae. Granted additional access to the quantum FAN-OUT operation (i.e. upgrading to the QACf0_f^0f0​ circuit class), we also achieve exact and clean preparation of arbitrary-weight Dicke states, with polynomial ancillae. These protocols distinguish the constant-depth capabilities of quantum architectures based on connectivity and offer a novel path toward resolving a long-standing quantum complexity conjecture.
Efficient state preparation is a challenging and important problem in quantum computing. In this work, we present a recursive state preparation algorithm that combines logarithmic-depth Dicke state circuits with Hamming weight encoders for efficiently preparing ``leaf-separable" quantum states. The algorithm is built on binary partition trees, generalized weight distribution blocks (gWDBs), and leaf-level encoders. We evaluate the performance of the algorithm by numerically simulating it on randomly generated target states with between 4 and 15 qubits. Compared to general state preparation approaches which require O(2n)O(2^n)O(2n) CX gates, our algorithm achieves a circuit depth of O(klog⁡nk+2k)O(k\log\frac{n}{k} + 2^k)O(klogkn​+2k) and uses O(n(k+2k))O(n(k+2^k))O(n(k+2k)) two-qubit gates, where k<nk < nk<n denotes the subtree size. We also compare implementations of the algorithm with and without the use of ancilla qubits, providing a detailed analysis of the trade-offs in circuit depth and two-qubit gate counts. These results contribute to scalable state preparation for quantum algorithms that require structured inputs such as Dicke or near-Dicke states.
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 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.