Linear growth of quantum circuit complexity
Linear growth of quantum circuit complexity
复制标题
DOI：
10.1038/s41567-022-01539-6
复制
发表时间：
2022-03-28
期刊：
影响因子：
19.6
通讯作者：
Halpern, Nicole Yunger
中科院分区：
文献类型：
--
作者：
Haferkamp, Jonas;Faist, Philippe;Halpern, Nicole Yunger
量子态的动力学是热力学甚至是最近的量子引力理论出现的基础。现在已经证明，在随机操作下演化的状态的量子复杂性随时间线性增长。量子态的复杂性已经成为从量子计算到黑洞理论的各个物理学子领域的关键感兴趣的量。一般量子系统的演化可以通过考虑量子比特的集合受到随机幺正门序列的影响来建模。在这里，我们研究如何增加这些随机量子电路的复杂性，考虑如何从哈尔随机两量子比特量子门构造一个幺正操作。精确地实现酉操作需要最少数量的门-这是操作的精确电路复杂度。我们证明了一个猜想，这种复杂性线性增长，饱和之前，当应用的门的数量达到一个阈值，量子位的数量呈指数增长。我们的证明克服了困难，建立准确的电路复杂性的下限相结合的微分拓扑和初等代数几何与Clifford电路的归纳建设。
The dynamics of quantum states underlies the emergence of thermodynamics and even recent theories of quantum gravity. Now it has been proven that the quantum complexity of states evolving under random operations grows linearly in time.The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates-this is the operation's exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.