@techreport{maslov2017shorter,
author = {Maslov, Dmitri and Roetteler, Martin},
title = {Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations},
year = {2017},
month = {May},
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 implement 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 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.},
publisher = {arxiv.org},
url = {http://approjects.co.za/?big=en-us/research/publication/shorter-stabilizer-circuits-via-bruhat-decomposition-quantum-circuit-transformations/},
number = {MSR-TR-2017-20},
}