The decomposition of an arbitrary 2w x 2w unitary matrix into signed permutation matrices

Birkhoff's theorem tells that any doubly stochastic matrix can be decomposed as a weighted sum of permutation matrices. A similar theorem reveals that any unitary matrix can be decomposed as a weighted sum of complex permutation matrices. Unitary matrices of dimension equal to a power of 2 (say 2(w)) deserve special attention, as they represent quantum qubit circuits. We investigate which subgroup of the signed permutation matrices suffices to decompose an arbitrary such matrix. It turns out to be a matrix group isomorphic to the extraspecial group E-22w+1(+), of order 2(2w+1). An associated projective group of order 2(2w) equally suffices. (C) 2020 Elsevier Inc. All rights reserved.