学 术

分享到微信 ×
打开微信“扫一扫”
即可将网页分享至朋友圈
学术沙龙:Space-Depth Trade-Off of CNOT Circuits
文:人力资源部教师发展中心 来源:计算机学院 党委教师工作部、人力资源部(教师发展中心) 时间:2019-10-10 3922

  人力资源部教师发展中心“学术沙龙”活动特别邀请中国科学院计算所研究员孙晓明教授来校作学术交流。具体安排如下,欢迎广大师生参加。

  一、主  题:Space-Depth Trade-Off of CNOT Circuits

  二、时  间:2019年10月11日(周五)14:30-16:00

  三、地  点:清水河校区宾诺咖啡

  四、主讲人:中国科学院计算所 孙晓明教授

  五、主持人:计算机科学与工程学院(网络空间安全学院) 肖鸣宇教授

  六、内容简介:

  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(n2) ancillae. However, the near-term quantum technologies can only support limited amount of qubits, making space-depth trade-off a fundamental research subject for quantum-circuit synthesis. In this work, we establish an asymptotically optimal space-depth trade-off for the design of CNOT circuits. We prove that for any m>=0, any n-qubit CNOT circuit can be parallelized to O(max{log n; n2/(n+m)log(n+m)}) depth, with m ancillae. We show that this bound is tight by a counting argument, and further show that even with arbitrary two-qubit quantum gates to approximate CNOT circuits, the depth lower bound still meets our construction, illustrating the robustness of our result. Our work improves upon two previous results, one by Moore and Nilsson for O(logn)-depth quantum synthesis, and one by Patel, Markov, and Hayes for m=0: for the former, we reduce the need of ancillae by a factor of log2n by showing that to build O(logn)-depth, O(n2/logn) size, it needs m=O(n2/log2n) additional qubits — which is asymptotically optimal — CNOT circuits; for the later, we reduce the depth by a factor of n to the asymptotically optimal bound O(n/logn). 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 synthesi optimization of CNOT circuits in term of both size and depth.

  七、主讲人简介:

  孙晓明,中国科学院计算所研究员。主要研究领域:算法与计算复杂性,量子计算,社交网络算法研究,判定树复杂性等。曾获首批国家自然科学基金优青资助,中国密码学会优秀青年奖、密码创新二等奖,入选中组部首批万人计划青年拔尖人才。目前担任CCF理论专委副主任、学工委主任助理,国际学术会议COCOON指导委员会委员,还担任《软件学报》《计算机研究与发展》《FCS》《JCST》《中国科学》等杂志编委或青年编委。

  八、主办单位:人力资源部教师发展中心

    承办单位:计算机科学与工程学院(网络空间安全学院)

 

                        人力资源部教师发展中心

                          2019年10月10日


编辑:杨棋凌  / 审核:罗莎  / 发布:陈伟

"