论文标题
量子电路复杂性线性生长的简短证明
Short Proofs of Linear Growth of Quantum Circuit Complexity
论文作者
论文摘要
量子门的复杂性（定义为构建它的基本门数量最少）是量子信息和计算中的重要概念。最近表明，由随机量子电路构建的量子门的复杂性几乎肯定会随着构建块的数量线性增长。在本文中，我们提供了两个简短的证据，证明了这一事实。我们还讨论了量子电路复杂度增长的离散版本。
The complexity of a quantum gate, defined as the minimal number of elementary gates to build it, is an important concept in quantum information and computation. It is shown recently that the complexity of quantum gates built from random quantum circuits almost surely grows linearly with the number of building blocks. In this article, we provide two short proofs of this fact. We also discuss a discrete version of quantum circuit complexity growth.
