Depth Optimization of CZ, CNOT, and Clifford Circuits
Dmitri Maslov, Ben Zindorf
Abstract
We seek to develop better upper bound guarantees on the depth of quantum CZ gate, CNOT gate, and Clifford circuits than those reported previously. We focus on the number of qubits <inline-formula><tex-math notation="LaTeX">$n\,{\leq }\,$</tex-math></inline-formula>1,345,000 [1], which represents the most practical use case. Our upper bound on the depth of <inline-formula><tex-math notation="LaTeX">$\textsc {CZ}$</tex-math></inline-formula> circuits is <inline-formula><tex-math notation="LaTeX">$\lfloor n/2 + 0.4993{\cdot }\log ^{2}(n) + 3.0191{\cdot }\log (n) - 10.9139\rfloor$</tex-math></inline-formula>, improving best known depth by a factor of roughly 2. We extend the constructions used to prove this upper bound to obtain depth upper bound of <inline-formula><tex-math notation="LaTeX">$\lfloor n + 1.9496{\cdot }\log ^{2}(n) + 3.5075{\cdot }\log (n) - 23.4269 \rfloor$</tex-math></inline-formula> for CNOT gate circuits, offering an improvement by a factor of roughly <inline-formula><tex-math notation="LaTeX">$4/3$</tex-math></inline-formula> over state of the art, and depth upper bound of <inline-formula><tex-math notation="LaTeX">$\lfloor 2n + 2.9487{\cdot }\log ^{2}(n) + 8.4909{\cdot }\log (n) - 44.4798\rfloor$</tex-math></inline-formula> for Clifford circuits, offering an improvement by a factor of roughly <inline-formula><tex-math notation="LaTeX">$5/3$</tex-math></inline-formula>.