Depth Optimization of CZ, CNOT, and Clifford Circuits

• Published in: IEEE transactions on quantum engineering 2022, Vol.3, p.1-8
• Main Authors: Maslov, Dmitri, Zindorf, Ben
• Format: Article
• Language: English
• Subjects: Clifford circuits; Color; Costs; Gates (circuits); Ions; Logic gates; Optimization; Quantum circuit; quantum circuit depth; quantum circuit synthesis; quantum circuits; Qubit; Qubits (quantum computing); Upper bound; Upper bounds
• ISSN: 2689-1808; 2689-1808
• DOI: 10.1109/TQE.2022.3180900

We seek to develop better upper bound guarantees on the depth of quantum \text {CZ} gate, cnot gate, and Clifford circuits than those reported previously. We focus on the number of qubits n\,{\leq }\,1 345 000 (de Brugière et al. , 2021), which represents the most practical use case. Our upper bound on the depth of \text {CZ} circuits is \lfloor n/2 + 0.4993{\cdot }\log ^{2}(n) + 3.0191{\cdot }\log (n) - 10.9139\rfloor, improving the 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 \lfloor n + 1.9496{\cdot }\log ^{2}(n) + 3.5075{\cdot }\log (n) - 23.4269 \rfloor for cnot gate circuits, offering an improvement by a factor of roughly 4/3 over the state of the art, and depth upper bound of \lfloor 2n + 2.9487{\cdot }\log ^{2}(n) + 8.4909{\cdot }\log (n) - 44.4798\rfloor for Clifford circuits, offering an improvement by a factor of roughly 5/3.