Families of Constant-Depth Quantum Circuits for Rotations and Permutations

Abstract

Developing and expanding on the idea by Moore and Nilsson [1], we provide a detailed description of families of logspace uniform quantum circuits that implement cyclic shifts and permutations of qubits. This allows us to formally prove that such operations belong to QNC0, the quantum analogue of the complexity class NC0, which captures highly efficiently parallelizable classical computations.