  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.
  In this work, we establish an asymptotically optimal space-depth trade-off
for CNOT circuits. We prove that any $n$-qubit CNOT circuit can be parallelized
to $$O\left(\max\left\{\log n, \frac{n^2}{(n+m)\log (n+m)}\right\}\right)$$
depth with $m$ ancillae. This bound is tight even if the task is expanded from
exact synthesis to the approximation of CNOT circuits with arbitrary two-qubit
quantum gates. Our result can be extended to stabilizer circuits via the
reduction by Aaronson and Gottesman (Physical Review A, 2004). Furthermore, we
provide hardness evidence for optimizing CNOT circuits in terms of size or
depth. Our result has improved upon two previous papers that motivated our
work. Moore-Nilsson's construction (aforementioned) for $O(\log n)$-depth CNOT
circuit synthesis: We have reduced their need for ancillae by a factor of
$\log^2 n$ by showing that $m= O(n^2/\log^2 n)$ additional qubits -- which is
asymptotically optimal -- suffice to build equivalent $O(\log n)$-depth
$O(n^2/\log n)$-size CNOT circuits. Patel-Markov-Hayes's construction (Quantum
Information & Computation 2008) for $m = 0$: We have reduced their depth by a
factor of $n$ and achieved the asymptotically optimal bound of $O(n/\log n)$.
