Depth optimization of CZ, CNOT, and Clifford circuits

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 $n\le$1,345,000 [1], which represents the most practical use case. Our upper bound on the depth of CZ circuits is $\lfloor n/2+0.4993\cdot {\log }^2(n)+3.0191\cdot \log (n)-10.9139\rfloor$, 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 $\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 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$.

References in corpus (4)

• Randomized Benchmarking of Quantum Gates
• Robust randomized benchmarking of quantum processes
• Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
• Reducing the Depth of Linear Reversible Quantum Circuits

Cited by in corpus (14)

• Synthesis of and compilation with time-optimal multi-qubit gates
• Constant-cost implementations of Clifford operations and multiply controlled gates using global interactions
• Approximate complex amplitude encoding algorithm and its application to data classification problems
• Automated Synthesis of Fault-Tolerant State Preparation Circuits for Quantum Error Correction Codes
• CNOT circuits need little help to implement arbitrary Hadamard-free Clifford transformations they generate
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Constant Depth Code Deformations in the Parity Architecture
• Time-optimal multi-qubit gates: Complexity, efficient heuristic and gate-time bounds
• Quantum resource estimates for computing binary elliptic curve discrete logarithms
• Resource-efficient shadow tomography using equatorial stabilizer measurements
• A graph-state based synthesis framework for Clifford isometries
• All You Need is pi: Quantum Computing with Hermitian Gates
• Minimum Synthesis Cost of CNOT Circuits
• Quantum Circuit Optimization by Graph Coloring