Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations

Abstract

In this paper we improve the layered implementation of arbitrary stabilizer circuits introduced by Aaronson and Gottesman in Phys. Rev. A 70(052328), 2004: to obtain a general stabilizer circuit, we reduce their $11$-stage computation -H-C-P-C-P-C-H-P-C-P-C- over the gate set consisting of Hadamard, Controlled-NOT, and Phase gates, into a $7$-stage computation of the form -C-CZ-P-H-P-CZ-C-. We show arguments in support of using -CZ- stages over the -C- stages: not only the use of -CZ- stages allows a shorter layered expression, but -CZ- stages are simpler and appear to be easier to implement compared to the -C- stages. Based on this decomposition, we develop a two-qubit gate depth-$(14n-4)$ implementation of stabilizer circuits over the gate library $\{$H, P, CNOT$\}$, executable in the Linear Nearest Neighbor (LNN) architecture, improving best previously known depth-$25n$ circuit, also executable in the LNN architecture. Our constructions rely on Bruhat decomposition of the symplectic group and on folding arbitrarily long sequences of the form $($-P-C-${)}^m$ into a 3-stage computation -P-CZ-C-. Our results include the reduction of the $11$-stage decomposition -H-C-P-C-P-C-H-P-C-P-C- into a $9$-stage decomposition of the form -C-P-C-P-H-C-P-C-P-. This reduction is based on the Bruhat decomposition of the symplectic group. This result also implies a new normal form for stabilizer circuits. We show that a circuit in this normal form is optimal in the number of Hadamard gates used. We also show that the normal form has an asymptotically optimal number of parameters.

Supersedes arXiv:1703.00874

References in corpus (3)

• Randomized Benchmarking of Quantum Gates
• Demonstration of a small programmable quantum computer with atomic qubits
• Basic circuit compilation techniques for an ion-trap quantum machine

Cited by in corpus (39)

• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
• Universal behavior beyond multifractality of wave-functions at measurement--induced phase transitions
• Hadamard-free circuits expose the structure of the Clifford group
• Crosstalk Suppression for Fault-tolerant Quantum Error Correction with Trapped Ions
• Optimized compiler for Distributed Quantum Computing
• Learning quantum circuits of some $T$ gates
• Reducing the Depth of Linear Reversible Quantum Circuits
• State preparation by shallow circuits using feed forward
• Optimising Clifford Circuits with Quantomatic
• Synthesis of and compilation with time-optimal multi-qubit gates
• Techniques to Reduce $\pi /4$-Parity-Phase Circuits, Motivated by the ZX Calculus
• Enumerating all bilocal Clifford distillation protocols through symmetry reduction
• A Practical Introduction to Benchmarking and Characterization of Quantum Computers
• Logical Clifford Synthesis for Stabilizer Codes
• Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits
• The Classification of Clifford Gates over Qubits
• No-Go Theorems for Universal Entanglement Purification
• Constant depth fault-tolerant Clifford circuits for multi-qubit large block codes
• CNOT circuits need little help to implement arbitrary Hadamard-free Clifford transformations they generate
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• Kerdock Codes Determine Unitary 2-Designs
• The power and limitations of learning quantum dynamics incoherently
• Synthesis of CNOT-Dihedral circuits with optimal number of two qubit gates
• Decomposition of Clifford Gates
• Counting stabiliser codes for arbitrary dimension
• Symbolic Synthesis of Clifford Circuits and Beyond
• A quantum computing approach to fixed-node Monte Carlo using classical shadows
• Extending Classically Simulatable Bounds of Clifford Circuits with Nonstabilizer States via Framed Wigner Functions
• Universal framework for simultaneous tomography of quantum states and SPAM noise
• Multipartite Greenberger-Horne-Zeilinger Entanglement in Monitored Random Clifford Circuits
• Quantum resource estimates for computing binary elliptic curve discrete logarithms
• Global Synthesis of CNOT Circuits with Holes
• Targeted Clifford logical gates for hypergraph product codes
• A graph-state based synthesis framework for Clifford isometries
• Resource-efficient shadow tomography using equatorial stabilizer measurements
• Optimal randomized measurements for a family of non-linear quantum properties
• Approximate Quantum Error Correction with 1D Log-Depth Circuits