Space-Depth Trade-Off of CNOT Circuits (Xiaoming Sun)


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.


2021-06-18  10:30-11:00   


Xiaoming Sun, The Institute of Computing Technology of the Chinese Academy of Sciences 


Guangdong Hotel Shanghai