量子逻辑合成中CNOT电路的最佳空间-深度交错

作者：Jiaqing Jiang,Xiaoming Sun,Shang-Hua Teng,Bujiao Wu,Kewen Wu,Jialin Zhang

摘要：由于量子计算机的最先进的物理实现的退相干，因此必须并行化量子电路以减小其深度。二十年前，摩尔等人。证明了额外的量子位（或ancillae）可用于为量子算子设计“浅”并联电路。他们证明任何n-qubit CNOT电路都可以并行化为O（logn）深度，具有O（n2）ancillae。然而，近期量子技术只能支持有限数量的量子比特，使得空间深度权衡成为量子电路综合的基础研究课题。

在这项工作中，我们为CNOT电路的设计建立了渐近最优的空间 - 深度权衡。我们证明，对于任何m≥0，任何n-qubit CNOT电路都可以并行化为O（max {logn，n2（n + m）log（n + m）}）深度，具有O（m）ancillae。我们通过计数参数表明这个界限是紧的，并且进一步表明即使使用任意的双量子比特量子门来近似CNOT电路，深度下限仍然符合我们的结构，说明了我们的结果的稳健性。我们的工作改进了之前的两个结果，一个由Moore等人提出。用于O（logn） - 深度量子合成，以及Patel等人的一种。对于m = 0：对于前者，我们通过显示m = O（n2 / log2n）附加量子位足以构建O（logn）-deth，O（n2 / logn）大小，将ancillae的需要减少log2n因子---渐近最优的--- CNOT电路;对于后者，我们将深度减小n倍，得到渐近最优边界O（n / logn）。我们的结果可以使用Aaronson等人的早期结果直接扩展到稳定器电路。此外，我们还提供了相关的硬度证据，用于CNOT电路在尺寸和深度方面的综合优化。

原文标题：Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis

原文摘要：

地址：https://arxiv.org/abs/1907.05087