Space-Depth Trade-Off of CNOT Circuits
时 间：2021年9月3日，星期五，10:00 - 11:00
地 点：腾讯会议，会议ID：234 160 183
讲 者：孙晓明，中国科学院计算技术研究所
摘 要：Due to the decoherence of the state-of-the-art physical implementations of quantum computers, it is essential to parallelize the quantum circuits to reduce their depth. Two decades ago, Moore and Nilsson demonstrated that additional qubits (or ancillae) could be used to design “shallow” parallel circuits for quantumoperators. They proved that any n-qubit CNOT circuit could be parallelized to $O(log n)$ depth, with $O(n^2)$ ancillae. In this work, we establish an asymptotically optimal space-depth trade-off for the design of CNOT circuits. We prove that for any $m \ge 0$, any n-qubit CNOT circuit can be parallelized to $O(max{log n; n^2/(n+m) log(n+m)})$ depth, with m ancillae. Our results can bedirectly extended to stabilizer circuits using an earlier result by Aaronsonand Gottesman. In addition, we provide relevant hardness evidences for synthesis optimization of CNOT circuits in term of both size and depth.
讲者简介：
孙晓明，中国科学院计算所研究员。主要研究领域为算法与计算复杂性、量子计算、近似算法等。曾获基金委首批优青资助，入选中组部首批万人计划青年拔尖人才，中国密码学会优秀青年奖、密码创新二等奖。目前担任中国计算机学会理论专委会主任，还担任《软件学报》《计算机研究与发展》《中国科学:信息科学》《JCST》《FCS》等杂志编委或青年编委。
