A circular shift operator (or cyclic rotation gate) ROT applies a rightward (or leftward) shift of positions to a register of qubits so that the element at position is moved to position ( + ) mod . While it is known that there exists a quantum rotation operator that can be implemented in (log())-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 of the quantum register and a variable parameter . 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 ; therefore, the operator ROT can be implemented in (log())-time. When the parameter dictating the magnitude of the rotation is a power of 2, namely when = 2 for some 2, the depth of the circuit is exactly log() − log().
Quantum computing represents an avant-garde domain within the realm of computer science, where the intricate principles of quantum mechanics are harnessed to engineer formidable computing systems that manifest striking deviations from classical counterparts. In stark contrast to classical computers, which process information using discrete binary bits constrained to exclusively one of the states 0 and 1, quantum computing harnesses the power of quantum bits, or qubits, which efortlessly inhabit superpositions of multiple states. Moreover, the entangled configuration of two or more qubits bestows upon them the extraordinary ability to execute synchronized operations, transcending the computational eficiency of classical bits. These distinctive attributes endow quantum computers with a momentous advantage over their classical counterparts.
There are several models of quantum computation, with their own advantages and challenges.
These include the adiabatic model [
The complexity of a quantum circuit can be measured in several ways. One of these is the number of gates used within the circuit to manipulate the qubits, but since it is often possible to run two or more gates in parallel when operating on disjoint registers, a more appropriate measure is the depth of the circuit, i.e., the number of steps performed before the output of the circuit is obtained.
The design and simulation of eficient quantum circuits capable of solving specific tasks,
including through the use of artificial intelligence models [
In this paper, we address the problem constructing of a quantum cyclic shift (or cyclic rotation) operator, in the quantum circuit model of computation.
Given a vector of length and an input parameter < , a cyclic rotation of a vector is a transformation that shifts the elements of the vector in circular positions, while maintaining their relative order. In other words, each element of the vector is moved by positions, and the last elements are brought back to the first positions of the vector.
Cyclic rotations of vectors have various applications, including, for instance, image and signal
processing where they can be employed to perform cyclic shifts on images or signals, such as
image rolling [
In the field of quantum computation, cyclic rotation of a register has been efectively used
in solutions for text processing, and specifically in string matching. The recent algorithm
by Niroula and Nam [
Since a cyclic rotation of a vector of elements of positions to the right consists essentially of a permutation of the input vector in which each element of position is moved to position (+) mod (), it is easy to construct a classical procedure capable of achieving such a rotation in linear time.
In quantum computation, on the other hand, it is possible to exploit the parallelism of gate
execution within a circuit to achieve significant speed-up. Niroula and Nam [
In an attempt to fill the gap, this paper aims to provide a precise method for the construction of a circular rotation operator for a vector of dimension as the parameter , indicating the shift relative to the rotation, varies. As far as we know, this is the first work ofering such a procedure. A proof of the correctness of our procedure is also provided, along with an analysis of the time complexity of the resulting circuit. We believe that this result may be of interest to the scientific community concerned with the design and simulation of quantum algorithms, especially in the area of text processing.
The paper is organized as follows. In Section 2 we recall some basic notions, introduce some useful notations adopted along the paper and give a more formal definition of the problem. In Section 3 we present a solution for the specific case where = 2 for some ∈ N, prove its correctness and discuss its complexity analysis. In Section 4 we extend our solution to the general case. Finally we draw our conclusions in Section 5.
The fundamental unit in quantum computation is the qubit. A qubit is a coherent superposition of the two orthonormal basis states, which are denoted by |0⟩ and |1⟩, using the conventional bra–ket notation. The mathematical formulation for a qubit | ⟩ is then a linear combination of the two basis states, i.e., | ⟩ = |0⟩ + |1⟩, where the values and , called amplitudes, are complex numbers such that | |2 + | |2 = 1, representing the probability of finding the qubit in the state |0⟩ or |1⟩, respectively, when measured. A quantum measurement is the only operation through which information is gained about the state of a qubit, however causing the qubit to collapse to one of the two basis states. The measurement of the state of a qubit is irreversible, meaning that it irreversibly alters the magnitudes of and . If is a binary value, equal to 0 or 1, we use the symbol |⟩ to indicate the qubit in the corresponding basis state, |0⟩ or |1⟩, respectively. Multiple qubits taken together are referred to as quantum registers. A quantum register |⟩ = |0, 1, .., − 1⟩ of qubits is the tensor product of the constituent qubits, i.e., |⟩ = ⨂︀
=−01 |⟩.
If is an integer value that can be represented by a binary string of length , we use the symbol |⟩ to denote the register of qubits such that |⟩ = ⨂︀ =−01 |⟩, where |⟩ takes the value of the -th least significant binary digit of . For example, the quantum register |9⟩ with 4 qubits is given by |9⟩ = |1⟩ ⊗ | 0⟩ ⊗ | 0⟩ ⊗ | 1⟩. The mathematical formulation of a quantum register is then |⟩ = ∑︀2− 1
=0 |⟩, where the values represent the probability of finding the register in the state |⟩ when measured, with ∑︀2− 1 | |2 = 1. =0
The model of computation we adopt in this paper is that of reversible circuits. Circuits are networks composed of wires that carry qubit values to gates that perform elementary operations on qubits. The qubits move through the circuit in a linear fashion, where the input values are written onto the wires entering the circuit from the left side, while the output values are read-of the wires leaving the circuit on the right side. At every time step, each wire can enter at most one gate. In the definition of a circuit, it is often necessary to include ancillae qubits, which are needed to achieve some specific tasks in computation that otherwise could not be achieved.
For the circuit model of computation, a natural measure of complexity is the number of gates used in the circuit. If we assume the circuit as being divided into a sequence of discrete = time-steps, where the application of a single gate requires a single time-step, another measure of complexity is the depth of the circuit, which is the total number of required time-steps. We observe that this is not necessarily the same as the total number of gates in the circuit, since gates that act on disjoint qubits can often be applied in parallel.
There is a variety of quantum operators capable of operating on quantum registers to perform widely-ranging manipulations. Here we simply list the two gates that will be used in this work: the CNOT gate and the Swap gate.
The controlled NOT gate (or CNOT) is a quantum logic gate operating on a register of two qubits |0, 1⟩. If the control qubit |0⟩ is set to 1, it inverts the target qubit |1⟩, otherwise all qubits stay the same. Formally, it maps |0, 1⟩ to |0, 0 ⊕ 1⟩. The Swap gate is a two-qubit operator: expressed in basis states, it swaps the state of the two qubits |0, 1⟩ involved in the operation, mapping them to |1, 0⟩. Interestingly, the swap gate can be achieved by the application of three CNOT operators.
Fig. 1 shows the representation of the CNOT and Swap gates.
A circular shift operator (or rotation operator) ROT applies a rightward shift of positions to a register of qubits so that the element at position is moved to position ( + ) mod . In other words, the elements whose position exceeds the size of the register are moved, in a circular fashion, to the first positions of the register. Formally, the operator ROT applies the following permutation
|0, 1, . . . , − 1⟩ →− | − , − +1, . . . , − 1, 0, 2, . . . , − − 1⟩.
Throughout the document we assume that the size of the qubit to be rotated is of the form 2 for some ∈ N, observe that this assumption is not restrictive since for quantum registers made of qubits this is always the case; nevertheless, in Section 4.1 we show how to proceed seamlessly in the case that the size of the target register is not a power of 2. 3. An Algorithm for = 2 In this section we describe an algorithm for cyclically rotating a quantum register |⟩ of qubits of positions, with 0 < < . We recall that we assume = 2 for some ∈ N. Without loss of generality, we assume that the rotation operator shifts the qubits to the right. Leftward rotations can occur symmetrically with respect to what is described in this paper.
We first consider the case in which the parameter controlling the rotation is of the form = 2, with < . Actually, it is enough to assume = 2ℎ for some ℎ : 1 ≤ ℎ ≤ − 1. The pseudocode of the quantum procedure performing the cyclic rotation is presented in Algorithm 1.
ALGORITHM 1: Algorithm for = 2
Input: a -qubit register := ⨂︀− 1
=0 |⟩, and := 2.
Output: a -qubit register ′ := ⨂︀− 1
=0 |+ mod ()⟩. 1 for = 1, . . . , log() − log(); + + do 2 for = 0, . . . , 2 − 1; + + do 3 for = 2, . . . , (2 + 1) − 1; + + do 4 Swap(, +2− 1)
The procedure performs a permutation of the qubits contained in the input quantum register. This is done by means of a sequence of swap operations that exchange the positions of two qubits inside the register. During the execution of the algorithm we distinguish qubits having reached their final position, which we indicate with the term placed qubits. Conversely, qubits having not yet been placed correctly are indicated by the term out-of-place qubits.
In brief, the algorithm works as follows. At the beginning of the procedure the register |⟩ contains not-in-place qubits and no placed qubit. Then, an iterative cycle starts, where at each iteration step, the algorithm selects half of the remaining not-in-place qubits and swaps them to their final positions. This means that the procedure stops in at most log() steps.
The worst case is obtained when each swap operation places only one of the two involved qubits in its final place, terminating in log() steps. When each swap succeeds in placing both qubits in their final positions, then the algorithm obtains its best case ( = 2 ), terminating in constant time.
We now go into more detail on the design of Algorithm 1. It is based on a main iterative loop (line 1) that runs log() − log() times1.
In the first iteration (namely for = 1), the algorithm decomposes the register |⟩ into 2 intervals, each of size 2 (line 2). Let , for 0 < < 2 , be the -th interval into which the register |⟩ has been divided. The algorithm divides each interval into two halves of size . In this context, let ℓ be the left half of the interval and let be the right half of the same interval. The algorithm operates by swapping the qubits in ℓ with the corresponding qubits in (line 3). Specifically it applies a Swap to the pair of qubits (, +) for every corresponding to a position in ℓ, that is ∈ {2, . . . , (2 + 1) − 1}. It is important to stress the fact that the algorithm performs these swaps in parallel for each ∈ {0, . . . , 2 − 1}.
Since this operation shifts the qubits in ℓ exactly positions to the right, after the first iteration, half of the qubits are correctly placed. It is immediate to see, indeed, that the algorithm correcly placed the qubits that have been moved to positions + , for ∈ {2, . . . , (2 + 1) − 1} and for ∈ {0, . . . , 2 − 1}.
We can prove (see Section 3.1) that if = 2 , that is if = 1, we do not need further iterations as also the qubits at positions , for ∈ {2, . . . , (2 + 1) − 1} and for ∈ {0, . . . , 2 − 1}, are correctly placed and the algorithm correctly terminates. Otherwise, the algorithm starts a new iteration.
The interval decomposition that we described in the first iteration can be generalized in subsequent iterations of the main for loop as follows. In the th step, being 1 < ≤ log() − 1We’ll discuss why the iterative loop on line 1 runs log() − log() times later. log()), the algorithm decomposes the register |⟩ into 2 intervals, each of size 2 (line 2).
Now observe that the first elements of the left interval ℓ are in that position as a result of a swap of the previous iteration. We are therefore dealing with not-in-place qubits. The same is true for the first qubits of the interval . Thus, the algorithm operates by swapping the qubits in the first positions of ℓ with the corresponding qubit in the first positions of (line 3). This is done to forbid swaps of qubits that are already correctly placed. 3 0 1 2 7 4 5 6 7 0 1 2 3 4 5 6 2
More formally, the algorithm applies a swap to the pair of qubits (, +2− 1) for every corresponding to a position in the first half of , that is ∈ {2, . . . , (2 + 1) − 1}. Also in this case the algorithm performs these swaps in parallel for each ∈ {0, . . . , 2 − 1}. Figure 2 illustrates the iteration of the algorithm implementing the circular shift operator for a register of 8 qubits in which a rotation of 1 position is performed. Figure 3 provides an illustration of the application of the circular shift operator as prescribed by Algorithm 1, for a register of 8 qubits in which a rightward circular shift of magnitude 1, 2, and 4 is performed. In the representation of each operator, the time-steps, within which the swaps are executed in parallel, have been framed. Each time-step is associated with a label ROT[], where represents the shift amount and represents the number of the iterative step.
Regarding the computational complexity, we observe that in a quantum circuit model of computation the for-loops at lines 2 and 3 of Algorithm 1 can be executed in parallel. To see this it is enough to check that the aim of line 2 is to partition the register in disjoint intervals, while the aim of lines 3-4 is to swap disjoint qubits in such intervals. More precisely, each iteration of line 3 refers to a specific one of the intervals individuated in line 2; because, the intervals are disjoint, the whole computation described at lines 2-4 happens in parallel in one time-step.
It follows that the running time of Algorithm 1 is log() − log(), which is (log()).
In this section, we prove the correctness of Algorithm 1. We start by making the following considerations.
1. At the th iteration, with 1 < ≤ log() − log(), a qubit is not involved in any Swap if and only if it has already been correctly shifted in a previous iteration, i.e. it is a placed qubit. 2. After log() − log() iterations of Algorithm 1, every qubit is correctly cyclically shifted by positions rightwardly, i.e. the th qubit has been placed at position + mod ().
For ∈ {1, . . . , log() − log()}, the symbol denotes the th qubit of the register |⟩ at the end of the th iteration of the algorithm; also, we set 0 := , and |⟩= ⨂︀ =0 , accordingly.
The correctness of Algorithm 1 immediately follow from the next lemma.
Lemma 3.1. If 1 ≤ ≤ log() − log(), at the end of the th iteration of Algorithm 1, for every ∈ {0, . . . , 2 − 1} it holds that • = 0− , for ∈ {(2 + 1), . . . , 2( + 1) − 1}, and • = 0+(1− 2), for ∈ {2, . . . , (2 + 1) − 1}.
In particular, for ℓ = log() − log() it holds ℓ = 0 − , for ∈ {0, . . . , − 1}, that is, after ℓ iterations of Algorithm 1 every qubit is correctly placed.
Proof. We prove the lemma by induction on the number of iterations .
For = 1, it is immediate to see that for every ∈ {0, . . . , 2 − 1}, every ∈ {2, . . . , (2 + 1) − 1}, and every = + 21− 1 = + , the execution of Swap(0, 0) yields 1 = 0 = 0− and 1 = 0 = 0− .
Let 1 ≤ ≤ log() − log(); assume the claim true for |0⟩, . . . ,|⟩, and let us prove it is true for |+1⟩.
By inductive hypothesis, for ∈ {0, . . . , 2 − 1}, it holds = 0− ,
for ∈ {(2 + 1), . . . , 2( + 1) − 1}, and = 0+(1− 2), for ∈ {2, . . . , (2 + 1) − 1}.
It requires no much efort to check that and that {2+1, . . . , (2+1 + 1) − 1 | 0 ≤ ≤ = {2, . . . , (2 + 1) − 1 | 0 ≤ ≤
2+1 − 1} 2 − 2 such that is even}, {(2+1 + 2), . . . , (2+1 + 1 + 2) − 1 | 0 ≤ ≤ = {2, . . . , (2 + 1) − 1 | 0 ≤ ≤ 2 − 1 such that is odd}.
It follows that all the qubits involved in a swap during the ( + 1)st iteration of the algorithm are of the form = 0− (1− 2). Therefore, +1 = for ∈ {(2 + 1), . . . , 2( + 1) − 1} and ∈ {0, . . . , 2 − 1}.
Moreover, during the ( + 1)th iteration, the algorithm executes the operation Swap(, ) for ∈ {2+1, . . . , (2+1 + 1) − 1} and = + 2, where ∈ {0, . . . , 2 +1 − 1}; such swapping results in +1 = = +2 = − (1− 2)+2 = − (1− 2+1), and
0 0 +1 = ++12 = = − (1− 2) = +2− = − .
0 0 0 To complete the proof it is enough to observe that
{(2 + 1), . . . , 2( + 1) − 1 | 0 ≤ ≤ ∪{(2+1 + 2), . . . , (2+1 + 1 + 2) − 1 | 0 ≤ ≤ ={(2+1 + 1), . . . , 2+1( + 1) − 1 | 0 ≤ ≤ 2 − 1}
2+1 − 1}.
2+1 − 1} Indeed, the previous equality implies that +1 = 0− , for ∈ {(2+1 + 1), . . . , 2+1( + 1) − 1}, and ∈ {0, . . . , 2+1 − 1}. Finally, observe that for = ℓ = log() − log(), the variable assumes only the value 0; furthermore, for ∈ {0, . . . , − 1} it holds
ℓ = 0− (1− 2ℓ) = 0− .
Therefore, after ℓ = log() − log() iteration of Algorithm 1 every qubit is correctly placed, that is, rightward cyclically shifted by positions. This completes our proof. 4. The General Algorithm for 1 ≤ ≤ − 1 In this section we present the algorithm implementing the cyclic rotation operator, shifting the input register of positions to the right, for the general case in which 1 ≤ ≤ − 1. ALGORITHM 2: Algorithm for a generic ∈ {1, . . . , − 1}
Input: a -qubit register := ⨂︀− 1
=0 |⟩, and 1 ≤ ≤ − 1.
Output: a -qubit register ′ := ⨂︀− 1
=0 |+ mod ()⟩. 1 ℓ := min{1 ≤ ≤ log() | 2 = 0 mod ()}; 2 for = 1, . . . , ℓ; + + do 3 for = 0, . . . , 2ℓ− − 1; + + do 4 for = 2ℓ 2, . . . , (2 + 1) 2ℓ − 1; + + do 5 Swap(, +2− 1 mod ())
The idea behind the general algorithm is very similar to the idea underlying the algorithm for = 2. The pseudocode of such general procedure is depicted in Algorithm 2.
Specifically, a new parameter ℓ is defined, by setting ℓ := min{1 ≤ ≤ log() | 2 = 0 mod ()}.
To understand the choice of ℓ, imagine the qubits from |⟩ arranged circularly. Observe that, by its definition, ℓ is the smallest positive integer such that an interval of length 2ℓ starting at the qubit 0 finishes at the qubit − 1 when wrapped around |⟩.
Informally, the main dificulty encountered when trying to extend the approach from Algorithm 1 to the general case consists in the fact that it is not possible to decompose the -qubits register |⟩ in disjoint intervals of length 2, 22, etc., in general. However, once again, we can imagine that the qubits from |⟩ are arranged along a circle to which we wrap the decomposition in intervals of length 2 around. Therefore, we can adapt Algorithm 1 to the general case of an arbitrary , by reasoning in the -modular arithmetic. Indeed, by comparing the pseudocodes of the two algorithms, it is immediate to see that in Algorithm 2 we replaced log() − log() by ℓ, and by .
2ℓ
Figure 4 illustrates the iterations of the algorithm implementing the circular shift operator for a register of 8 qubits in which a rotation of 6 position is performed. Figure 5 and Figure 6 provide an illustration of the application of the circular shift operator as prescribed by Algorithm 2, for a register of 8 qubits in which a rightward circular shift of magnitude 3, 5, and 6 is performed.
Regarding the computational complexity, we observe that - as in the case of Algorithm 1 - in a quantum circuit model of computation the for-loops at lines 3 and 4 are executed in parallel. This means that, once ℓ is known, Algorithm 2 executes ℓ ≤ log() time-steps. Furthermore, to compute the number ℓ of iterations needed, the algorithm has to perform at most log() multiplications. Therefore, the overall time-complexity of Algorithm 2 is (log()).
Regarding the correctness of the general algorithm, it can be reduced to the following theorem. Theorem 4.1. Algorithm 2 correctly outputs the rightward circular shifting of an input -qubits register by positions.
Proof. Correctness of Algorithm 2 follows from the correctness of Algorithm 1 and in particular from Lemma 3.1. To verify this claim, it is enough to observe that, by the definition of ℓ, in the -modular arithmetic it holds that 2ℓ = , 2ℓ− 2 , and log() − log( 2ℓ ) = ℓ. 3 4 |0⟩ |1⟩ |2⟩ |3⟩ |4⟩ |5⟩ |6⟩ |7⟩ 5 2 same distance. For instance, in ROT[31], the pair 6 and 1 have distance 1 − 6 = 3 mod (8), which is the same distance between the other swapped pairs of qubits. Similarly, all the swapped pairs of qubits in ROT[32] have distance 6 mod (8).
In Section 2, we assumed to work with registers whose length is a power of 2. This does not make our method less general. It is easy to check, indeed, that the following slight modification of Algorithm 2 realizes the circular shift by position of a qubit-register of any size. It is enough to replace the register of arbitrary size by the register ′ that has size 2⌈log()⌉ and such that
′ = , for 0 ≤ < , and ′ = ⋆, for ≤ < 2⌈log()⌉ − 1, where ⋆ is a special symbol that does not belong to the working alphabet. At this point, it is suficient to rotate ′ by positions, as dictated by Algorithm 2, and drop from the output register the qubits whose state is equal to ⋆. The resulting register will have size and be equal to ⨂︀− 1
=0|+ mod ()⟩, namely the circular shift of by positions.
We have presented a quantum algorithm that performs the rightward circular shift of a quantum
register of arbitrary size by positions. As we already discussed, the circular shift operator is
a staple ingredient of many quantum recipes. For example, in the framework of quantum text
processing, it is employed to get all possible portions of a certain fixed length of a text in the
[
Algorithm 2 can be modified to get an algorithm that constructs a quantum gate that implements the rightward circular shift operator ROT, for any 1 ≤ ≤ − 1, in an obvious way, i.e., replacing line 4 of the algorithm by add Swap(, +2− 1 mod ()). We observe that the quantum gate obtained has still depth equal to (log()). However, there is a non-significant diference between the quantum gate performing ROT and the algorithm that builds it. In fact, during the execution of the quantum gate, there is no need to get the knowledge about the number of needed iterations ℓ (which is already encoded in the circuit implementing the gate), whereas the building algorithm needs to compute it.
We assumed to work with registers of qubits, that is, the register is made of 2-dimensional quantum systems. In the quantum computation landscape, this is however not always the case. For example, qutrits are quantum systems of dimension 3 that have attracted some interest in quantum cryptography [14, 15]. We think that it makes sense and would be interesting - at least from a purely theoretical perspective - to define the -dimensional generalisation of the Swap elementary gate and to understand how to use it to implement non-elementary gates performing -dimensional rotations. To be more concrete, in the framework of qutrits we could define some swap-like elementary gate permuting in some way the states of three qutrits, and then employ it to perform some kind of spherical shift.
We would like to express our gratitude to Simone Faro for participating in constructive discussions on the problem and for valuable advice. We would also like to thank Domenico Cantone for his suggestions regarding the proof of some lemmas presented in this paper. [13] D. Cantone, S. Faro, A. Pavone, Quantum string matching unfolded and extended, in: M. Kutrib, U. Meyer (Eds.), Reversible Computation, Springer Nature Switzerland, Cham, 2023, pp. 117–133. [14] B. P. Lanyon, T. J. Weinhold, N. K. Langford, J. L. O’Brien, K. J. Resch, A. Gilchrist, A. G.
White, Manipulating biphotonic qutrits, Phys. Rev. Lett. 100 (2008) 060504. URL: https://link. aps.org/doi/10.1103/PhysRevLett.100.060504. doi:10.1103/PhysRevLett.100.060504. [15] M. Smania, A. M. Elhassan, A. Tavakoli, M. Bourennane, Experimental quantum multiparty communication protocols, npj Quantum Information 2 (2016) 16010. URL: https://doi.org/ 10.1038/npjqi.2016.10. doi:10.1038/npjqi.2016.10.