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:2211.05413 · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Does Qubit Connectivity Impact Quantum Circuit Complexity?

Pei Yuan, Jonathan Allcock, Shengyu Zhang

Published Sep 4, 2023• 17 citations
arXivHTMLPDF

Abstract

Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. These connectivity constraints are commonly viewed as a significant disadvantage. For example, compiling an unrestricted$n$-qubit quantum circuit to one with poor qubit connectivity, such as a 1-D chain, usually results in a blowup of depth by$O(n^{2})$and size by$O(n)$. It is appealing to conjecture that this overhead is unavoidable—a random circuit on$n$qubits has$\Theta (n)$two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance$\Theta (n)$. While it is known that almost all$n$-qubit unitary operations need quantum circuits of$\Omega (4^{n}/n)$depth and$\Omega (4^{n})$size to realize with all-to-all qubit connectivity, in this article, we show that all$n$-qubit unitary operations can be implemented by quantum circuits of$O(4^{n}/n)$depth and$O(4^{n})$size even under 1-D chain qubit connectivity constraint. We extend this result and investigate qubit connectivity in three directions. First, we consider more general connectivity graphs and show that the circuit size can always be made$O(4^{n})$as long as the graph is connected. For circuit depth, we study$d$-dimensional grids, complete$d$-ary trees and expander graphs, and show results similar to the 1-D chain. Second, we consider the case when ancillary qubits are available. We show that, with ancilla, the circuit depth can be made polynomial, and the space-depth trade-off is not impaired by connectivity constraints unless we have exponentially many ancillary qubits. Third, we obtain nearly optimal results on special families of unitaries, including diagonal unitaries, 2-by-2 block diagonal unitaries, and quantum state preparation (QSP) unitaries, the last being a fundamental task used in many quantum algorithms for machine learning and linear algebra.

DOI
10.1109/tcad.2023.3311734

Related papers

Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint

Pei Yuan, Shengyu Zhang

In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits. Compilation of a quantum circuit into one compliant to such qubit connectivity constraint results in an increase of circuit depth. Various compilation algorithms were studied, yet what this depth overhead is remains elusive. In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph, a graph-theoretic measure which has been studied for 3 decades. We also give reduction algorithms between different graphs, which allow compilation for one graph to be transferred to one for another. These results, when combined with existing routing algorithms, give asymptotically optimal compilation for all commonly seen connectivity graphs in quantum computing.

arXiv:2402.02403•Quantum•May 28, 2025•4 citations

Optimization of CNOT circuits under topological constraints.

Bujiao Wu, Xiaoyu He, Shuai Yang +4 more

CNOT circuit is the key gadget for entangling qubits in quantum computing systems. However, the qubit connectivity of noisy intermediate-scale quantum (NISQ) devices is constrained by their topological structures. To improve the performance of CNOT circuits on NISQ devices, we investigate the optimization of the size/depth of CNOT circuits under topological constraints. We firstly present a method that can optimize the size of any $n$-qubit CNOT circuit to less than $2n^2$ on any connected graph, which is optimal for sparsely connected structures. The simulation experiment shows that our method performs better than state-of-the-art results. Specifically, we present two detailed examples to illustrate the applicability of our algorithm. Furthermore, for the future device with a denser structure, we give a better optimization method that achieves $O(n^2/\log \delta)$ size on a graph with the minimum degree $\delta$, which is optimal on the regular graph. Secondly, for the grid structure, which is commonly used in current quantum devices, we demonstrate that the depth of any $n$-qubit CNOT circuit can be optimized to be linear in $n$ with certain ancillary qubits (ancillas). Our experimental results indicate this method has significant improvements compared with all of the existing methods. We further implement the two circuits commonly used in quantum variational algorithms and quantum chemistry on the 5-qubit IBMQ devices by leverage of our optimization algorithm, the experimental results show the optimized circuit has far less error when there exists noise compared to IBM mapping method.

•Oct 31, 2019•5 citations

The power of constant-depth quantum circuits of unbounded size

Sergii Strelchuk, Sathyawageeswar Subramanian, Máté Weisz

Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension $d$ and $M\geq d^2-1$ ports, we construct a unitary circuit of depth $O(\sqrt d)$, independent of $M$ and including resource preparation and port selection, with entanglement fidelity at least $(1-(d^2-1)/(2M))^2$. Thus, at fixed $d$, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on $d$ can also be removed remains open.

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

All Unitaries Have Constant Depth Quantum Circuits

Barak Nehoran, Joseph Slote, Henry Yuen

It is well-known that every $n$-qubit unitary can be implemented by a $2^{O(n)}$-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth $\mathsf{poly}(n)$ with $2^{O(n)}$ ancilla qubits. In other words, every $n$-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in $n$, which is the best possible, and an exponential improvement on the previous best bound of $2^{n/2}$ due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.

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

Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications

Xiao‐Ming Zhang, Tongyang Li, Xiao Yuan

Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.

arXiv:2201.11495•Physical Review Letters•Nov 30, 2022•176 citations

Worst-case depth hierarchy for shallow quantum circuits

Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian +1 more

Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.

quant-pharXiv:2606.16425•Jun 16, 2026•0 citations
Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. These connectivity constraints are commonly viewed as a significant disadvantage. For example, compiling an unrestrictednnn-qubit quantum circuit to one with poor qubit connectivity, such as a 1-D chain, usually results in a blowup of depth byO(n2)O(n^{2})O(n2)and size byO(n)O(n)O(n). It is appealing to conjecture that this overhead is unavoidable—a random circuit onnnnqubits hasΘ(n)\Theta (n)Θ(n)two-qubit gates in each layer and a constant fraction of them act on qubits separated by distanceΘ(n)\Theta (n)Θ(n). While it is known that almost allnnn-qubit unitary operations need quantum circuits ofΩ(4n/n)\Omega (4^{n}/n)Ω(4n/n)depth andΩ(4n)\Omega (4^{n})Ω(4n)size to realize with all-to-all qubit connectivity, in this article, we show that allnnn-qubit unitary operations can be implemented by quantum circuits ofO(4n/n)O(4^{n}/n)O(4n/n)depth andO(4n)O(4^{n})O(4n)size even under 1-D chain qubit connectivity constraint. We extend this result and investigate qubit connectivity in three directions. First, we consider more general connectivity graphs and show that the circuit size can always be madeO(4n)O(4^{n})O(4n)as long as the graph is connected. For circuit depth, we studyddd-dimensional grids, completeddd-ary trees and expander graphs, and show results similar to the 1-D chain. Second, we consider the case when ancillary qubits are available. We show that, with ancilla, the circuit depth can be made polynomial, and the space-depth trade-off is not impaired by connectivity constraints unless we have exponentially many ancillary qubits. Third, we obtain nearly optimal results on special families of unitaries, including diagonal unitaries, 2-by-2 block diagonal unitaries, and quantum state preparation (QSP) unitaries, the last being a fundamental task used in many quantum algorithms for machine learning and linear algebra.
In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits. Compilation of a quantum circuit into one compliant to such qubit connectivity constraint results in an increase of circuit depth. Various compilation algorithms were studied, yet what this depth overhead is remains elusive. In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph, a graph-theoretic measure which has been studied for 3 decades. We also give reduction algorithms between different graphs, which allow compilation for one graph to be transferred to one for another. These results, when combined with existing routing algorithms, give asymptotically optimal compilation for all commonly seen connectivity graphs in quantum computing.
CNOT circuit is the key gadget for entangling qubits in quantum computing systems. However, the qubit connectivity of noisy intermediate-scale quantum (NISQ) devices is constrained by their topological structures. To improve the performance of CNOT circuits on NISQ devices, we investigate the optimization of the size/depth of CNOT circuits under topological constraints. We firstly present a method that can optimize the size of any nnn-qubit CNOT circuit to less than 2n22n^22n2 on any connected graph, which is optimal for sparsely connected structures. The simulation experiment shows that our method performs better than state-of-the-art results. Specifically, we present two detailed examples to illustrate the applicability of our algorithm. Furthermore, for the future device with a denser structure, we give a better optimization method that achieves O(n2/log⁡δ)O(n^2/\log \delta)O(n2/logδ) size on a graph with the minimum degree δ\deltaδ, which is optimal on the regular graph. Secondly, for the grid structure, which is commonly used in current quantum devices, we demonstrate that the depth of any nnn-qubit CNOT circuit can be optimized to be linear in nnn with certain ancillary qubits (ancillas). Our experimental results indicate this method has significant improvements compared with all of the existing methods. We further implement the two circuits commonly used in quantum variational algorithms and quantum chemistry on the 5-qubit IBMQ devices by leverage of our optimization algorithm, the experimental results show the optimized circuit has far less error when there exists noise compared to IBM mapping method.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension ddd and M≥d2−1M\geq d^2-1M≥d2−1 ports, we construct a unitary circuit of depth O(d)O(\sqrt d)O(d​), independent of MMM and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2(1-(d^2-1)/(2M))^2(1−(d2−1)/(2M))2. Thus, at fixed ddd, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on ddd can also be removed remains open.
It is well-known that every nnn-qubit unitary can be implemented by a 2O(n)2^{O(n)}2O(n)-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth poly(n)\mathsf{poly}(n)poly(n) with 2O(n)2^{O(n)}2O(n) ancilla qubits. In other words, every nnn-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in nnn, which is the best possible, and an exponential improvement on the previous best bound of 2n/22^{n/2}2n/2 due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.
Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored. We prove an explicit depth hierarchy theorem for QNC0\mathsf{QNC}^0QNC0. For each d≥12d\ge 12d≥12, we construct a family of two-round interactive problems on which no depth-(d−1)(d-1)(d−1) quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than ddd by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every ddd, yielding a hierarchy of problems that show unconditional quantum advantage of QNC0\mathsf{QNC}^0QNC0 over NC0\mathsf{NC}^0NC0. A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits. These results show that increasing depth strictly increases computational power within QNC0\mathsf{QNC}^0QNC0, establishing a genuinely quantum hierarchy.