Date: Oct. 13 2020
Time: 10:30-11:30

Venue: Meeting room 526 or online @ Tencent Meeting Room：578570892

Topic: Space-Depth Trade-Off of CNOT Circuits

Speaker：Xiao-Ming Sun (Institute of Computing Technology, CAS)

Host：Dong Liu (Physics department, Tsinghua University)
 

Abstract：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 quantum operators. 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 be directly extended to stabilizer circuits using an earlier result by Aaronson and Gottesman. In addition, we provide relevant hardness evidences for synthesis optimization of CNOT circuits in term of both size and depth.

About the speaker：孙晓明，中科院计算所研究员。主要研究领域为量子计算、算法与计算复杂性、近似算法、组合数学等。曾获基金委首批优青资助，入选中组部首批万人计划青年拔尖人才，中国密码学会优秀青年奖、密码创新二等奖。目前担任中国计算机学会理论专委会主任，国际学术会议COCOON指导委员会委员，还担任《软件学报》《JCST》《FCS》等杂志编委和《中国科学:信息科学》青年编委。