Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis

Understand

Decoherence -- in the current physical implementations of quantum computers -- makes depth reduction a vital task in quantum-circuit design.

• Moore and Nilsson (SIAM Journal of Computing, 2001) demonstrated that additional qubits -- known as ancillae -- can be used to provide an extended space to parallelize quantum circuits.
• Specifically, they proved that, with $O(n^2)$ ancillae, any $n$-qubit CNOT circuit can be transformed into an equivalent one of $O(\log n)$ depth.
• However, the near-term quantum technologies can only support a limited amount of qubits, making space-depth trade-off a fundamental research subject for quantum-circuit synthesis.