论文标题
Qubit连接性会影响量子电路复杂性吗？
Does qubit connectivity impact quantum circuit complexity?
论文作者
论文摘要
量子计算的某些物理实施方案只能在某些量子位上应用两倍的门。这些连通性约束通常被视为重要的缺点。例如，将无限制的$ n $ qubit量子电路汇编为具有不良量子连接性（例如1D链）的一个量子电路，通常会导致深度爆炸，而深度为$ O（n^2）$，大小为$ O（n）$。人们可以猜想这个开销是不可避免的 - $ n $ Qubits上的随机电路在每一层中都有$θ（n）$两倍的门，而其中的恒定分数对量子的量子$θ（n）$。 众所周知，几乎所有$ n $ qubit的统一操作都需要$ω（4^n/n）$深度和$ω（4^n）$大小的量子电路，以全能的量子连接性来实现，在本文中，我们显示所有$ n $ n $ qubit的统一操作都可以通过$ o（$ o（4^n/n）$ o（4^n/n）$ o（4^n/n）实现链条}量子连接约束。 我们扩展了此结果，并在三个方向上研究了量子连接性。首先，我们考虑更通用的连接图，并表明只要连接该图，就可以始终将电路大小$ O（4^n）$。对于电路深度，我们研究了$ D $维网格，完整的$ D $ ARE TROED和扩展器图，并显示与1D链的结果。其次，我们考虑可用辅助量子位的情况。我们表明，使用Ancilla，电路深度可以成为多项式，并且除非我们有指数级的辅助量子，否则连通性限制的空间折衷不会受到连接限制的损害。第三，我们对特殊统一的特殊家庭获得了几乎最佳的结果，包括对角线统一，2 by-2块对角线单位和量子状态制剂（QSP）统一，最后一次是用于机器学习和线性代数的许多量子算法中使用的基本任务。
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 1D 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 $Θ(n)$ two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance $Θ(n)$. While it is known that almost all $n$-qubit unitary operations need quantum circuits of $Ω(4^n/n)$ depth and $Ω(4^n)$ size to realize with all-to-all qubit connectivity, in this paper, 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 {1D 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 1D 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.
