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

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•0 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•0 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•0 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

Constant-depth adaptive preparation of Dicke and symmetric states

Rui Luo, Junjie Chen, Xiongfeng Ma

Efficient preparation of Dicke states and, more generally, permutation-symmetric states is important for quantum metrology, quantum networking, and collective quantum information processing. Measurements and classical feedforward enable low-depth preparations of these states, with a cost of ancillary qubits. In this work, we introduce an exact constant-depth adaptive preparation protocol for arbitrary Dicke-$(n,k)$ states and further symmetric states. We first provide a protocol preparing the uniform subset superposition state, as a primitive, using constant-depth adaptive circuit with $O(k^2\log^2 n)$ ancillary qubits and success probability at least $1/k$. This yields an exact, probabilistic, constant-depth Dicke-state preparation protocol using $O\left(n^2+k^2\log^2 n+kn\log n\log\log n\right)$ ancillary qubits. Parallel repetition suppresses the failure probability exponentially without increasing the quantum depth. Moreover, the uniform subset superposition state is also of independent interest as the uniform vertex state of the Johnson graph and as the compact uniform subset state appearing in quantum-walk and topological-data-analysis algorithms. We further establish a general lifting framework that coherently combines clean unitary Dicke-state preparation circuits to prepare arbitrary symmetric states with only polynomial ancillary overhead. Combined with recent constant-depth unitary Dicke-state constructions, this gives an exact constant-depth preparation protocol for arbitrary $n$-qubit symmetric states using $O(n^3\sqrt{\log n})$ ancillary qubits.

quant-pharXiv:2608.01144•Aug 4, 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.
Efficient preparation of Dicke states and, more generally, permutation-symmetric states is important for quantum metrology, quantum networking, and collective quantum information processing. Measurements and classical feedforward enable low-depth preparations of these states, with a cost of ancillary qubits. In this work, we introduce an exact constant-depth adaptive preparation protocol for arbitrary Dicke-(n,k)(n,k)(n,k) states and further symmetric states. We first provide a protocol preparing the uniform subset superposition state, as a primitive, using constant-depth adaptive circuit with O(k2log⁡2n)O(k^2\log^2 n)O(k2log2n) ancillary qubits and success probability at least 1/k1/k1/k. This yields an exact, probabilistic, constant-depth Dicke-state preparation protocol using O(n2+k2log⁡2n+knlog⁡nlog⁡log⁡n)O\left(n^2+k^2\log^2 n+kn\log n\log\log n\right)O(n2+k2log2n+knlognloglogn) ancillary qubits. Parallel repetition suppresses the failure probability exponentially without increasing the quantum depth. Moreover, the uniform subset superposition state is also of independent interest as the uniform vertex state of the Johnson graph and as the compact uniform subset state appearing in quantum-walk and topological-data-analysis algorithms. We further establish a general lifting framework that coherently combines clean unitary Dicke-state preparation circuits to prepare arbitrary symmetric states with only polynomial ancillary overhead. Combined with recent constant-depth unitary Dicke-state constructions, this gives an exact constant-depth preparation protocol for arbitrary nnn-qubit symmetric states using O(n3log⁡n)O(n^3\sqrt{\log n})O(n3logn​) ancillary qubits.