Space-Depth Trade-Off of CNOT Circuits (Xiaoming Sun)
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 [1] 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 [5]. In addition, we provide relevant hardness evidences for synthesis optimization of CNOT circuits in term of both size and depth.
Time
2021-06-18 10:30-11:00
Speaker
Xiaoming Sun, The Institute of Computing Technology of the Chinese Academy of Sciences
Room
Guangdong Hotel Shanghai
