The Quantum Cyclic Rotation Gate
Arianna Pavone, Caterina Viola · SN Computer Science · 2024
Abstract A circular shift operator (or cyclic rotation gate) $${{\,\mathrm{\texttt {ROT}}\,}}_k$$ ROT k applies a rightward (or leftward) shift to an input register of n qubits o by as many positions as encoded by an additional input $$k \in \mathbb N$$ k ∈ N . Specifically, the qubit at position x is moved to position $$(x+k) \mod n$$ ( x + k ) mod n . While it is known that there exists a quantum rotation operator that can be implemented in $${{\,\mathrm{\mathcal {O}}\,}}(\log (n))$$ O ( log ( n ) ) -time, through the repeated parallel application of the elementary $${{\,\mathrm{\texttt {Swap}}\,}}$$ Swap operators, there is no systematic procedure that concretely constructs the quantum operator $${{\,\mathrm{\texttt {ROT}}\,}}$$ ROT for variable size n of the quantum register and a variable parameter k. We fill the gap, providing a systematic implementation of the cyclic rotation operator (denoted $${{\,\mathrm{\texttt {ROT}}\,}}$$ ROT ) in a quantum circuit model of computation whose depth is $${{\,\mathrm{\mathcal {O}}\,}}(\log (n))$$ O ( log ( n ) ) . We show how the circular shift operator can be utilized in quantum approaches to text processing, focusing on the problem of getting all possible cyclic rotations of a string in $${{\,\mathrm{\mathcal {O}}\,}}(\log ^2(n))$$ O ( log 2 ( n ) ) depth.