Time：June 3 2021, 14:00-15:00

Venue: Room 526

Tencent Meeting ID: 720144855

Password：0603

Title：Optimization of the depth/size of CNOT circuit with limited ancillas

Host：Dong Liu, Research Scientist, BAQIS；Associate Professor, Department of Physics, Tsinghua University 

Abstract：

Due to the decoherence of the state-of-the-art physical implementations of quantum computers, and the near-term quantum technologies can only support a limited amount of qubits, it is essential to parallelize the quantum circuits with space-depth trade-off. Furthermore, quantum computation is limited to the connection of two qubits in actual physical devices. It is essential to optimize the size and depth of CNOT circuits based on topological superconducting processors.In this work, we establish an asymptotically optimal space-depth trade-off for the design of CNOT circuits of the logical qubits (CNOT can be operated on any two qubits), we show that this bound is tight by a counting argument. For actual physical qubits, we give an algorithm to optimize the size of CNOT circuits under topological structure, and prove our algorithm is optimal when the graph is regular. In addition, we also consider the optimization of the depth of CNOT circuits in d dimensional grid topological structure, by which we can optimize any CNOT circuits to O(n^(1+o(1))/log n)-depth with O(n)-ancillas and d=O(1).

About the Speaker：

Bujiao Wu is a postdoctoral student at Peking University. She obtained her Ph.D. in 2021 from the Institute of Computing, Chinese Academy of sciences. Her primary research interest is in the quantum algorithm and quantum circuit optimization.