Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

SN Computer Science

The Quantum Cyclic Rotation Gate

Arianna Pavone, Caterina Viola

Published Aug 27, 2024• 6 citations
Publisher

Abstract

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.

DOI
10.1007/s42979-024-03141-4

Related papers

Quantum Shift Register

Jae Weon Lee, Eok Kyun Lee, Jaewan Kim +1 more

We consider a quantum circuit in which shift and rotation operations on qubits are performed by swap gates and controlled swap gates. These operations can be useful for quantum computers performing elementary arithmetic operations such as multiplication and a bit-wise comparison of qubits.

arXiv:quant-ph/0112107•Dec 19, 2001•4 citations

Quantum-state preparation with universal gate decompositions

Martin Plesch, Časlav Brukner

In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of $2$. It also reduces the total number of cnot gates from ${2}^{n}$ to $\frac{23}{24}{2}^{n}$ in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from $11$ cnot gates to $9$ and the depth from $11$ to $5$ steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.

arXiv:1003.5760•Physical Review A•Mar 3, 2011•335 citations

Quantum Bit-Parallel Swap Matching

Simone Faro, Francesco Pio Marino, Arianna Pavone +2 more

Pattern matching with swaps is a well-known non-standard variant of the string matching problem in which adjacent characters of the pattern may be swapped, under the constraint that each character participates in at most one swap. This problem has received considerable attention in the stringology literature due to its applications in areas such as computational biology, error-tolerant text processing, and pattern discovery. In this paper we investigate the problem in the quantum computing model. Building upon the recently introduced framework of quantum bit-parallelism, which provides a systematic way to translate classical bit-parallel string matching algorithms into quantum circuits, we develop the first quantum algorithm for swap matching based on this paradigm. Our approach adapts the classical cross-sampling technique for swap matching into a reversible quantum procedure that simulates the evolution of two interacting automata configurations using quantum registers and bitwise quantum operations. While the resulting quantum circuit preserves the near-linear behavior of its classical counterpart in terms of circuit depth, its integration with Grover’s search enables a quadratic speedup. By embedding the verification procedure within a quantum search framework and carefully controlling the size of the search space, we obtain a quantum algorithm that solves the swap matching problem in \(\tilde{O}(\sqrt {n})\) time. This result extends the applicability of quantum bit-parallelism to non-standard string matching problems and provides further evidence that a broad class of classical text searching techniques can be systematically lifted to the quantum setting while preserving their structural efficiency.

ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC)•Jul 11, 2026•0 citations

Cyclic Quantum Error-Correcting Codes and Quantum Shift Registers

Markus Grassl, Thomas Beth

We transfer the concept of linear feed-back shift registers to quantum circuits. It is shown how to use these quantum linear shift registers for encoding and decoding cyclic quantum error-correcting codes.

•Jan 1, 1999•36 citations

Rotation of bits: a classical and quantum perspective

Peter Nimbe, Benjamin Asubam Weyori, Adebayo Felix Adekoya

Abstract Bit rotation is an operation similar to shift except that the bits that fall off at one end are put back to the other end. In left rotation, the bits that fall off at left end are put back at right end. In right rotation, the bits that fall off at the right end are put back at the left end. Applications of bit rotation include; registers, cryptography, computing with a single bit string circularly shifted to the right or left based on some position but no work has been done with respect to shifting the bits one position at a time generating emergent bit strings equal to the number of bits-1 from the incident bit string, and then recombining or extracting bit(s) from each of the bit strings or words to form back the incident bit string. In this article, the authors present a new approach of rotating classical bit strings known as CRotate. A quantum approach to bit rotation known as QRotate is presented as well. The quantum perspective uses the concept of bit swapping by avenue of the quantum swap gate in jsqubits. Models and algorithms are duly presented.

Journal of Electrical Systems and Information Technology•Feb 27, 2021•1 citation

Efficient Preparation of Cyclic Quantum States

Fereshte Mozafari, Yuxiang Yang, Giovanni De Micheli

Universal quantum algorithms that prepare arbitrary n-qubit quantum states require${O\left(2^{n}\right)}$gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum states that are invariant under permutations, e.g. Dicke states, have intriguing properties. In this paper, we consider states invariant under cyclic permutations, which we call cyclic states. We present a quantum algorithm that deterministically prepares cyclic states with gate complexity${O\left(n\right)}$without requiring any ancillary qubit. Through both analytical and numerical analyses, we show that our algorithm is more efficient than existing ones.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 17, 2022•1 citation
Abstract A circular shift operator (or cyclic rotation gate)  ROT k{{\,\mathrm{\texttt {ROT}}\,}}_kROTk​ 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∈Nk \in \mathbb Nk∈N k ∈ N . Specifically, the qubit at position x is moved to position (x+k)mod  n(x+k) \mod n(x+k)modn ( x + k ) mod n . While it is known that there exists a quantum rotation operator that can be implemented in  O (log⁡(n)){{\,\mathrm{\mathcal {O}}\,}}(\log (n))O(log(n)) O ( log ( n ) ) -time, through the repeated parallel application of the elementary  Swap {{\,\mathrm{\texttt {Swap}}\,}}Swap Swap operators, there is no systematic procedure that concretely constructs the quantum operator  ROT {{\,\mathrm{\texttt {ROT}}\,}}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  ROT {{\,\mathrm{\texttt {ROT}}\,}}ROT ROT ) in a quantum circuit model of computation whose depth is  O (log⁡(n)){{\,\mathrm{\mathcal {O}}\,}}(\log (n))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  O (log⁡2(n)){{\,\mathrm{\mathcal {O}}\,}}(\log ^2(n))O(log2(n)) O ( log 2 ( n ) ) depth.
In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of 222. It also reduces the total number of cnot gates from 2n{2}^{n}2n to 23242n\frac{23}{24}{2}^{n}2423​2n in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from 111111 cnot gates to 999 and the depth from 111111 to 555 steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.
Pattern matching with swaps is a well-known non-standard variant of the string matching problem in which adjacent characters of the pattern may be swapped, under the constraint that each character participates in at most one swap. This problem has received considerable attention in the stringology literature due to its applications in areas such as computational biology, error-tolerant text processing, and pattern discovery. In this paper we investigate the problem in the quantum computing model. Building upon the recently introduced framework of quantum bit-parallelism, which provides a systematic way to translate classical bit-parallel string matching algorithms into quantum circuits, we develop the first quantum algorithm for swap matching based on this paradigm. Our approach adapts the classical cross-sampling technique for swap matching into a reversible quantum procedure that simulates the evolution of two interacting automata configurations using quantum registers and bitwise quantum operations. While the resulting quantum circuit preserves the near-linear behavior of its classical counterpart in terms of circuit depth, its integration with Grover’s search enables a quadratic speedup. By embedding the verification procedure within a quantum search framework and carefully controlling the size of the search space, we obtain a quantum algorithm that solves the swap matching problem in O~(n)\tilde{O}(\sqrt {n})O~(n​) time. This result extends the applicability of quantum bit-parallelism to non-standard string matching problems and provides further evidence that a broad class of classical text searching techniques can be systematically lifted to the quantum setting while preserving their structural efficiency.
Abstract Bit rotation is an operation similar to shift except that the bits that fall off at one end are put back to the other end. In left rotation, the bits that fall off at left end are put back at right end. In right rotation, the bits that fall off at the right end are put back at the left end. Applications of bit rotation include; registers, cryptography, computing with a single bit string circularly shifted to the right or left based on some position but no work has been done with respect to shifting the bits one position at a time generating emergent bit strings equal to the number of bits-1 from the incident bit string, and then recombining or extracting bit(s) from each of the bit strings or words to form back the incident bit string. In this article, the authors present a new approach of rotating classical bit strings known as CRotate. A quantum approach to bit rotation known as QRotate is presented as well. The quantum perspective uses the concept of bit swapping by avenue of the quantum swap gate in jsqubits. Models and algorithms are duly presented.
Universal quantum algorithms that prepare arbitrary n-qubit quantum states requireO(2n){O\left(2^{n}\right)}O(2n)gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum states that are invariant under permutations, e.g. Dicke states, have intriguing properties. In this paper, we consider states invariant under cyclic permutations, which we call cyclic states. We present a quantum algorithm that deterministically prepares cyclic states with gate complexityO(n){O\left(n\right)}O(n)without requiring any ancillary qubit. Through both analytical and numerical analyses, we show that our algorithm is more efficient than existing ones.