The Quantum Cyclic Rotation Gate

Abstract

A circular shift operator (or cyclic rotation gate) ROTk applies a rightward (or leftward) shift of k positions to a register of n qubits so that the element at position x is moved to position (x + k) mod n. While it is known that there exists a quantum rotation operator that can be implemented in O(log(n))-time, through the repeated parallel application of the elementary Swap operators, there is no systematic procedure that concretely constructs the quantum operator ROT for variable size n of the quantum register and a variable parameter k. We show a concrete implementation of the cyclic rotation operator (denoted ROT) in a quantum circuit model of computation. The depth of the obtained circuit implementing the cyclic rotation operator is upper-bounded by log n; therefore, the operator ROTk can be implemented in O(log(n))-time. When the parameter k dictating the magnitude of the rotation is a power of 2, namely when k = 2m for some 2, the depth of the circuit is exactly log(n) - log(k).