Does Qubit Connectivity Impact Quantum Circuit Complexity?

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 <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-qubit quantum circuit to one with poor qubit connectivity, such as a 1-D chain, usually results in a blowup of depth by <inline-formula> <tex-math notation="LaTeX">$O(n^{2})$ </tex-math></inline-formula> and size by <inline-formula> <tex-math notation="LaTeX">$O(n)$ </tex-math></inline-formula>. It is appealing to conjecture that this overhead is unavoidable—a random circuit on <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> qubits has <inline-formula> <tex-math notation="LaTeX">$\Theta (n)$ </tex-math></inline-formula> two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance <inline-formula> <tex-math notation="LaTeX">$\Theta (n)$ </tex-math></inline-formula>. While it is known that almost all <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-qubit unitary operations need quantum circuits of <inline-formula> <tex-math notation="LaTeX">$\Omega (4^{n}/n)$ </tex-math></inline-formula> depth and <inline-formula> <tex-math notation="LaTeX">$\Omega (4^{n})$ </tex-math></inline-formula> size to realize with all-to-all qubit connectivity, in this article, we show that all <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-qubit unitary operations can be implemented by quantum circuits of <inline-formula> <tex-math notation="LaTeX">$O(4^{n}/n)$ </tex-math></inline-formula> depth and <inline-formula> <tex-math notation="LaTeX">$O(4^{n})$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$O(4^{n})$ </tex-math></inline-formula> as long as the graph is connected. For circuit depth, we study <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula>-dimensional grids, complete <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula>-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.