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 eficiently parallelizable classical computations.
A quantum algorithm is designed to take full advantage of the computational power of quantum machines. In a quantum machine, the fundamental information units called quantum bits or qubits, are simulated by particles whose size is at and below the scale of atoms. The state of each of such particles is described by a wave function, which can be thought of as a probability distribution of the classical states in which the particle can be observed. A quantum computing machine works as predicted by the theory of quantum mechanics and therefore, in particular, a qubit can be in a superposition of the two basis states, and two or more qubits can be entangled, i.e., the probability of their states can be correlated. These peculiar properties of quantum bits allow for an increased amount of information encoded. However, when observing the qubits from the macroscopic world, this great amount of information loses its coherence and the qubits collapse in one of their classical probable states.
A cyclic shifting operator (or rotation operator) ROT applies a rightward (or leftward) shift of positions to a register of qubits, moving the element at position to position ( + ) mod .
Cyclic shifts have various applications, including image and signal processing, where they can be
employed to perform operations such as image rolling [
Algorithms for permutations serve as a filtering technique, commonly known as the counting filter,
to expedite complex combinatorial search problems. The core concept is that in many approximation
scenarios, a substring of the text that matches a given pattern, according to a specific distance
function, is also a permutation of that pattern. The counting filter technique has been applied to solve
approximate string-matching problems involving mismatches [
In a classical model of computation, permuting a multiple system of bits, particularly cyclically shifting it, exhibits linear time complexity because in the worst-case scenario, every element in the array must be shifted. This specialization of cyclic rotation becomes evident when dealing with bit strings on classical machines. While many concrete computers feature a built-in shift instruction that moves bits left or right, achieving a cyclic shift involves more efort than a simple one-sided shift, as it requires handling the wrap-around of the array. Employing a Boolean circuit model of computation, every permutation can be obtained very easily by just permuting the wires of a circuit, which can be done at no cost. It is therefore evident that permuting a multiple system of bits is not a problem susceptible to a computational speed-up due to the adoption of a quantum circuit model rather than a Boolean circuit model.
However, in quantum computing, permutations, especially cyclic shifts, of multiple quantum
bits are essential subroutines within quantum circuits. They enable the creation of superpositions
involving multiple permutations of quantum states, ofering computational advantages in tasks
such as database searching and optimization problems [
While it is known that a quantum rotation operator can be implemented in (log())-time
through repeated parallel applications of elementary Swap operators [
In this paper, we present a detailed description of a family of quantum circuits implementing
the cyclic shifting of the states of an arbitrary finite number of quantum bits; we generalize such
a quantum circuit family to one implementing the permutation of the states of an arbitrary finite
number of quantum bits, for any permutation defined on them. We provide the pseudocodes of the
respective deterministic algorithms computing these quantum circuit families, and we show that, in
fact, such families are logspace uniform. As a consequence, we formally prove that cyclic shiftings
and, more in general, permutations are in the complexity class QNC0, as already noted by Moore
and Nilsson [
Basic Notations. We denote by N and Z, the sets of natural and integer numbers, respectively. For each ∈ N, and , ∈ Z we write = mod if = + for some ∈ Z; furthermore, Z denotes the quotient set { ∈ Z | = ⇔ = mod }. We also recall that the floor operator ⌊·⌋ computes the maximum integer smaller or equal to its argument, while the ceiling operator ⌈·⌉ computes the minimum integer larger or equal to its argument.
Quantum Computational Systems. The fundamental unit in quantum computation is the quantum bit, also known as qubit. Formally, a single qubit is an element of the two-dimensional Hilbert space over the complex numbers, equipped with an inner product, ℋ, which is referred to as the state space. Therefore, the mathematical expression of a qubit, | ⟩, is a linear combination of the two basis states, i.e., | ⟩ = |0⟩ + |1⟩, where and , called amplitudes, are complex numbers such that | |2 + | |2 = 1. The squared magnitudes of and represent the probabilities of measuring the qubit in the state |0⟩ or |1⟩, respectively. A quantum measurement is the only operation through which we can gain some knowledge on the state of a qubit; more precisely, this operation causes the qubit to collapse to one of the two basis states, following the probability distribution described by the squares of its amplitudes before the measure. Multiple systems of qubits are referred to as quantum registers. A quantum register | ⟩ = |0, 1, . . . , − 1⟩ of size is an element from the tensor product of state spaces, ℋ⊗ , and is thus expressed as a linear combination of the 2 states in {0, 1}. Specifically, | ⟩ = ∑︀2− 1
=0 |⟩, where the values represent the probability amplitudes of the corresponding classical states |⟩ and satisfy ∑︀2− 1
=0 | |2 = 1.
Quantum Operations. The allowed operations on (registers of) qubits are those permitted by quantum mechanics. Quantum measurements are operations that cause the collapse of a quantum system into a classical state and result in the loss of the probability amplitude wave. Quantum measurements are needed not only to have access to the elaboration of the information stored in qubits but also for their state preparation [19, Section 1.10].
The evolution of a quantum mechanical system is described by a unitary transformation. A unitary operator is a bounded linear operator on a Hilbert space that satisfies † = † = , where † is the conjugate transpose of , and is the identity operator. In other words, a unitary transformation is an automorphism of the (tensor) state space that preserves the inner product, ⟨ , ⟩ = ⟨, ⟩, thus ensuring the conservation of the probability amplitudes. Formally, each unitary transformation on an -qubit register can be described by a 2 × 2 unitary matrix with complex entries. In particular, unitary transformations are reversible, meaning that no information is lost when performing them, and the composition of multiple unitary transformations is also a unitary transformation. Any unitary transformation on an -qubit register can be implemented by a sequence of 2-qubit unitary transformations.
Quantum Circuits. A quantum algorithm on an -dimensional input register consists of quantum unitary transformations and measurements.
Quantum algorithms can be formalized in various models, each with distinct advantages and challenges: the adiabatic model [20], the topological model [21], and the measurement-based model [22].
This paper adopts the quantum circuits model. Computational circuits are represented as directed acyclic graphs, where nodes denote gates operating on information carried by edges. Unlike classical circuits, quantum circuits must be reversible (excluding measurement gates), ensuring the number of input edges matches the number of output edges. Consequently, quantum circuits cannot join (fan-in) multiple wires or copy/split (fan-out) information due to the No-Cloning Theorem [23]. Thus, the graph representation features parallel wires (qubits) passing through gates. To address the No-Cloning Theorem’s limitations, ancillae qubits are often included in quantum circuits.
Real quantum machines have a finite set of native gates, typically at-most-ternary gates. Therefore, constructing circuits with a minimal number of native gates is crucial not only for speed and eficiency but also to reduce coherent quantum error caused by gate miscalibration and to maximize qubit lifespan. Qubits have a limited coherence time, after which they lose information.
Circuit-Based Quantum Computational Classes. There are two major measures of computational complexity for circuit models. One is the total number of basis gates, referred to as the size of the circuit. The other is the depth of the directed acyclic graph that represents the circuit. Clearly, basis gates have a depth of Θ(1).
A complexity class can be thought of as a collection of computational problems that share common features regarding the computational resources needed to solve them. Perhaps the most well-known complexity classes in classical computation models are P and NP. These classes are defined in terms of the elementary operations that the best-performing Turing Machine needs to execute to solve the target problem. Boolean circuits, on the other hand, are non-uniform models of computation, meaning that inputs of diferent lengths are processed by diferent circuits, in contrast to uniform models such as Turing Machines. A similar distinction arises between Quantum Turing Machines [24] and Quantum Circuits.
Complexity classes defined in terms of Boolean circuits include NC, AC, and P/poly. The class NC captures computations that can be eficiently performed on highly parallel computers. A computational task has an eficient parallel algorithm if instances of size can be solved using a parallel computer with () processors in time log(1)() (see [25] for details).
In the case of a family of quantum circuits, we can give a more concrete idea of what logspace uniform means. We do this in the style of [26, Definition 6.5] (see also [ 24]). To this end, we need to ifx the representation of the quantum circuits.
Definition 2.1. A circuit family {} is a collection of circuits such that for each ∈ N the circuit has inputs. A computational problem is solved by a circuit family {} if, for every ∈ N, the circuit solves the instances of the problem of size .
Definition 2.2. A circuit family {} is logspace uniform if there exists a logarithmic space deterministic Turing Machine mapping 1 to the description of , for all ∈ N.
Remark 2.3. Let be the size of . Since is an acyclic graph, we can assume to represent it
by its × adjacency matrix and by an array of size that encodes the labels of each gate (i.e. a
label that identifies each vertex of the acyclic graph as an input qubit or one of the basis gate to be
applied). Assuming such a representation, a family of quantum circuits {} is logspace uniform if,
and only if, the following functions can be computed in (log()) space: (1) the function SIZE (),
returning the size of the circuit ; (2) the function LABEL (, ), returning the label of the th gate of
(corresponding to the th entry of the labels array); and (3) the function EDGE (, , ) returning 1
whenever there is a direct wire (edge) from the th gate to the th one, and returning 0 otherwise.
Definition 2.4 ([
We conclude this section by highlighting the relationship between space-bounded Turing Machines and depth-bounded Boolean circuits in classical computation. Space-bounded computations can be eficiently simulated by bounded-depth circuits, and vice versa, through depth-first exploration (see [27, 28] for details). However, such a relationship is not established for quantum computations. While space-bounded computations on Quantum Turing Machines can be eficiently simulated by bounded-depth quantum circuits, the reverse is not known and is considered highly unlikely. Beyond theoretical considerations (see [24]), practical quantum computations are constrained by short coherence times, making highly parallelized quantum circuits more feasible than Quantum Turing Machines. 3. Quantum Circuits implementing Rotations and Permutations In this section, we show how to construct a logspace uniform family of constant-depth and linear-size quantum circuits for rotations and, more generally, for permutations. Before going into the details of our solution, some knowledge about rotations and permutations is necessary.
Formally, a rightward rotation (or rightward cyclic shift) is a quantum operator ROT+ that applies a rightward shift of positions to a register of size 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, 1, . . . , − − 1⟩ .
A leftward rotation (or leftward cyclic shift) ROT− applies a leftward shift of positions to a register of size so that the element at position is moved to position ( − ) mod . Formally, the operator ROT− applies the following permutation
|0, 1, . . . , − 1⟩ →↦− | , +1, . . . , − 1, 0, 1, . . . , − 1⟩ .
Example 3.1. Let | ⟩ = |0, 1, 2, 3, 4, 5, 6, 7⟩ be a quantum register of 8 qubits. Right rotating | ⟩ of 5 positions results in the quantum register ROT5+ | ⟩ = |3, 4, 5, 6, 7, 0, 1, 2⟩, while left rotating | ⟩ of 5 positions results in the quantum register ROT−5 | ⟩ = |5, 6, 7, 0, 1, 2, 3, 4⟩
Unless we explicitly declare that this is not the case, in this paper we use the term rotation and the symbol ROT by referring to the rightward version of the quantum operator. However, it is immediate to verify that
ROT− |⟩ = ROT+− |⟩ , for every register of size and every 0 ≤ < . Thus, all the results stated for the rightward rotations hold true for the leftward rotations, too, and the needed modifications in the algorithmic techniques are trivial.
Remark 3.2. Let us consider the -qubit register |⟩ = ⨁︀=−01 |⟩ = ∑︀2=− 0 1 |⟩. Applying a rotation of magnitude , we obtain = ROT |⟩ = ⨁︀− −− 1 |⟩ = ∑︀2ℎ=− 01 ℓℎ |ℎ⟩, where ℓℎ = = for each ℎ, ∈ {0, . . . , 2 − 1} such that the qubit representation of ℎ is a rotation of the qubit representation of by positions.
For every ∈ N, a permutation of elements is a bijection from a set of cardinality || = into itself. The set of all permutations of a set with elements is denoted by and forms a group (the symmetric group) with the composition operation. The composition of two permutations and is the permutation = such that () = ( ()). In general, the composition of permutations is not commutative.
There are several ways to represent a permutation, the one that we use in this paper - and perhaps the most common - is the cycle representation, which we describe in the following definition. Definition 3.3 (Cyclic permutation). For a set of cardinality || = and for ≤ , a cyclic permutation of length (or an -cycle) ∈ is a permutation for which there exists a sequence (0, 1, . . . , − 1) of pairwise distinct elements of such that • (0) = 1, (1) = 2, . . . , (− 1) = 0, i.e. it cyclically permutes all the elements from the sequence; • () = , for all ∈ ∖ {0, 1, . . . , − 1}, i.e. it fixes the elements that are not in the sequence.
The sequence (0, 1, . . . , − 1) = (︀ 0, (0), 2(0), . . . , − 1(0))︀ is the cycle representation of the -cycle , and is unique up to cyclic shifting. The identity is the trivial cyclic permutation which fixes all the elements of . The composition of two disjoint cyclic permutations is commutative. Example 3.4. Let = {a, b, c, d, e, f, g, h} be a set of elements of cardinality || = 8. The permutation = {a, g, b, c, e, f, d, h} is a cyclic permutation of length 4, since the sequence (c, b, g, d) is a sequence of pairwise distinct elements of such that (c) = b, (b) = g, (g) = d and (d) = c. In addition (a) = a, (e) = e, (f) = f and (h) = h.
We now present a foundational result in permutation theory, often referred to as a folklore theorem Theorem 3.5 (Folklore). Every permutation of finitely many elements can be written as the composition of two or more disjoint cyclic permutations. Such a decomposition is unique up to diferent orders of the cycles.
Remark 3.6. Given a diferent representation of a permutation , it is possible to find its decomposition into cycles in polynomial time [29, 30].
Let ∈ be a permutation of elements and let = 1 · · · ℓ be the decomposition of into disjoint cycles. then the cycle representation of is the array (1, . . . , ℓ), where is the sequence representing for every ∈ {1, . . . , ℓ}.
Example 3.7. Let = {a, b, c, d, e, f, g, h} be a set of elements of cardinality || = 8. The permutation = {d, f, h, a, g, e, b, c} can be represented by the following decomposition in disjoint cycles ((a, d), (b, f, e, g), (c, h)), which is the cycle representation of .
Example 3.8. Let = {a, b, c, d, e, f, g, h} be a set of elements of cardinality || = 8. The permutation = {h, c, a, b, e, f, d, g} can be represented by the following decomposition in disjoint cycles ((a, h, g, d, b, c), (e), (f)), which is the cycle representation of .
Remark 3.9. Any rotation, and more generally, any permutation of the states of the qubits within a
register, can be realized through the application of a unitary transformation.2. This implies that the
reordering of qubit states, whether it be a simple rotation or a more complex permutation, can be
efectuated by an appropriate unitary matrix, ensuring the transformation adheres to the principles
of quantum mechanics.
2We recall that a permutation can be formalized through a unitary matrix with entries in {0, 1}
3.2. Quantum Circuits implementing Rotations
In classical circuital models of computation, the wires carrying the information on the state of a bit
can be permuted as desired without any computational cost; the same does not hold true in quantum
circuits. In [
In the remainder of the current section, we will develop their idea and give a constructive proof of this fact, providing both the detailed description of such a circuit and the pseudocode of a logarithmicspace and polynomial-time algorithm constructing such a circuit for any cardinality of the set of qubits and any permutation of elements. As a consequence of this, we will observe that permuting the states of the constituent qubits from a quantum register is in the computational class QNC0.3
We start by focusing on the implementation of the rotation of the states of a quantum register by a given magnitude.
Let us consider a -qubit register |⟩ = ⨁︀=−01 |⟩ to be rotated by positions. Let us arrange the constituent qubits as the vertices of a regular polygon with sides from an Euclidean two-dimensional space. Enumerate such vertices by the indices of the corresponding qubits, i.e., 0, 1, . . . , − 1 or, equivalently, ∈ Z. In such a formulation, a rotation of 0, 1, . . . , − 1 by positions (to the right) corresponds to a rotation of the polygon about its centre of symmetry, .
It is well-known that every rotation of a regular polygon about its centre of symmetry by an angle can be obtained as the composition of two reflections across two axes such that they intersect in the centre of the polygon and form an angle equal to 2 . We remark that even if the observation above is behind our construction, it is not necessary to know it to see the correctness of our algorithm, which will be proved directly.
For every ∈ Z, we have that the angle formed by points , , and + 1 equals 2 radians; therefore, a rotation of the qubits by positions corresponds to a rotation of the polygon by 2 radians about . We have therefore to perform two reflections across two axes ℓ1 and ℓ2 such that they pass through and form an angle of radians. We choose ℓ1 and ℓ2 based on and . Let us ifrst assume that is even. Then ℓ1 is chosen as the line passing through 0 and , which contains the vertex 2 . A reflection across ℓ1 has the efect of swapping the pairs (, − ) for = 1, . . . , 2 − 1, while the vertices 0 and 2 stay fixed. Let us call 0 the initial state of the th qubit , and let 1 and 2 the states of the th qubit after the first and after the second reflection, respectively.
Then, we have that
The definition of ℓ2 depends on whether is even or odd. If is even, then ℓ2 is the line through
2 and , which contains 2 + 2 ; else, if is odd, ℓ2 is the line through the centre and the midpoint
of − 2 1 and +21 , which happens to contain the midpoint of 2 + +21 . The reflection across ℓ2 has
the efect of swapping the pairs ( 2 − , 2 + ) for = 1, . . . , 2 − 1 whenever is even, and has the
efect of swapping the pairs ( +21 − , − 2 1 + ) for = 1, . . . , 2 − 1 whenever is odd. In either
case, we have that after this second reflection
3The authors of [
ALGORITHM 1: Algorithm constructing a quantum circuit for the rotation of a register of size by positions.
Input: , 1 Initialize input wires (qubits) |0⟩ , . . . , |− 1⟩; 2 for = 1 to ⌈ 2 ⌉ − 1 do 3 Swap |, − ⟩
4 for = 1 to ⌈ 2 ⌉ − 1 do 5 Swap ⃒⃒⃒ ⌈ 2 ⌉− , ⌊ 2 ⌋+⟩ (observe that for even , 1 and 12 + 2 stay fixed).
2
Let us now assume that is odd. Then ℓ1 is defined as the line passing through 0 and , which contains the midpoint between −2 1 and +21 . A reflection across ℓ1 has the efect of swapping the pairs (, − ) for = 1, . . . , − 1. The result of this first rotation is
To define ℓ2 for odd, we have, once more, to take into account the parity of . If is even, then ℓ2 is the line through 2 and , which contains the midpoint between −2 1 + 2 and +21 + 2 ; else, if is odd, ℓ2 is the line through the centre and the midpoint of − 2 1 and +21 , which contains 2 + 2 . The reflection across ℓ2 has the efect of swapping the pairs ( 2 − , 2 + ) for = 1, . . . , −2 1 whenever is even, and has the efect of swapping the pairs ( +21 − , − 2 1 + ) for = 1, . . . , −2 1 whenever is odd. In either case, we have that after this second reflection (observe that for even , the state of stays fixed, while, for odd , the state of 2 + 2 stays fixed).
2
Algorithm 1, which runs in linear time, takes as input a pair (, ) of nonnegative integers and constructs a constant-depth and linear-size quantum circuit that performs the rotation of any -qubit register by positions.
It is immediate to see that Algorithm 1 has time-complexity (), that is, it has linear-time complexity.
On input (, ), Algorithm 1 constructs a circuit with wires (qubits). In lines 2-3, are defined ⌈ 2 ⌉ swaps that involve disjoint pairs of qubits and can, therefore, be applied in parallel, we will refer to the swaps defined in lines 2-3 as the first layer of swaps of the circuit ; similarly, we will refer to the swaps defined in lines 2-3 as the second layer of swaps of the circuit. Figures 1 and 2 illustrate a few examples of circuits built by Algorithm 1. Observe that the first layer depends only on the first input parameter .
Remark 3.10. Algorithm 1 works for ≥ 3. Clearly, if the register has only 2 qubits then any rotation either does nothing or simply swaps the states of the two qubits, in which case it is enough to employ an elementary swap gate. In the remainder, we assume to apply Algorithm 1 to registers with at least 3 qubits.
|0⟩ |1⟩ |2⟩ |3⟩ |4⟩ |5⟩ |6⟩ |7⟩ |4⟩ |5⟩ |6⟩ |7⟩ |0⟩ |1⟩ |2⟩ |3⟩ |0⟩ |1⟩ |2⟩ |3⟩ |4⟩ |5⟩ |6⟩ |7⟩ |3⟩ |4⟩ |5⟩ |6⟩ |7⟩ |0⟩ |1⟩ |2⟩
The following Lemma 3.11 represents a significant result regarding the depth and size characteristics of the circuit constructed by Algorithm 1.
Lemma 3.11. The circuit constructed by Algorithm 1 has constant depth (more precisely, the depth equals 6) and linear size. If we run the circuit on a quantum machine so that the CNOT gate is a native one, we get that the depth equals 6 and the size is bounded by 3( − 1).
Proof. The swap gates built in lines 2-3 involve disjoint pairs of qubits, therefore they can be applied in parallel, and form the first layer of parallel swap gates of the circuit. Similarly, the swap gates built in lines 4-5 form the second layer of parallel swap gates. Each layer of the circuit has at most −2 1 gates, therefore we have size bounded by − 1, that is (). Observe that a swap can be implemented by 3 CNOTs (see Section 2). Therefore, if the CNOT elementary gate is a native gate for our quantum machine we get a depth equal to 6 and a size bounded by 3( − 1).
The following Proposition 3.12 instead demonstrates the correctness of Algorithm 1. Proposition 3.12. Algorithm 1 on input (, ) constructs a quantum circuit such that, when applied to a register |⟩ = ⨂︀=−01 |⟩, returns ⨂︀=−01, |− mod ⟩ = ROT |⟩. That is, Algorithm 1 on input (, ) constructs a quantum gate performing the rotation by positions, ROT.
Proof. The first layer of swaps of the circuit, i.e. that constructed in lines 2 and 3 of Algorithm 1, has the efect of swapping the states of and − for every = 1, . . . , ⌈ 2 ⌉ − 1. Therefore, if ⃒⃒ 0⟩︀ is the th qubit of |⟩, and ⃒⃒⃒ 1 ⟩ is the th qubit of |⟩ after the application of the first layer, we have that 0 = 1− mod for = 0, . . . , − 1. The second layer of swaps of the circuit, i.e. that constructed in lines 4 and 5 of Algorithm 1, has the efect of swapping the states of and − for ∈ {0, . . . , − 1} in all cases but that of even and that of odd and odd , in which cases and 2 + 2 , respectively 2 are fixed. However, since − 2 = 2 , we have that 1 = 2− mod , where ⃒⃒ ℎ2⟩︀ denotes the ℎth qubit of |⟩ after the application of the second and last layer of swaps of the circuit. Summing up, we have the circuit built by Algorithm 1 acting on ⃒⃒ 0⟩︀ , for = 0, . . . , − 1 as follows 0 = 1− = 2− + mod = 2+ mod , that is the circuit operates a rotation by positions. |2⟩ |3⟩ |4⟩ |0⟩ |1⟩ |0⟩ |1⟩ |2⟩ |3⟩ |4⟩ |3⟩ |4⟩ |0⟩ |1⟩ |2⟩
We conclude this section with the main result anticipated in the introduction, which establishes the complexity class of the cyclic shift problem for quantum registers.
Corollary 3.13. The problem of cyclically shifting the states of a quantum register by any amount of positions is in QNC0.
Proof. Since Proposition 3.12 holds, to prove the corollary it is enough to observe that the functions SIZE (), LABEL (, ), EDGE (, , ) - corresponding to the circuits constructed by Algorithm 1 - can be computed in logarithmic space (refer to Remark 2.3), by a slight modification of Algorithm 1.
In this Section, we extend our previous result on cyclic shifts to the more general case of arbitrary permutations of a quantum register. This generalization involves defining an algorithm to construct quantum circuits that can perform any given permutation of the states of a quantum register. The main result of this section is encapsulated in the following Proposition 3.14.
Proposition 3.14. Any permutation of the states of qubits can be performed by a quantum circuit , having constant depth and linear size. Furthermore, there exists a polynomial-time algorithm that, on input (, )4, constructs , in polynomial time. Thus, the problem of permuting the states of ifnitely many qubits is in QNC0.
Proof. It is immediate to see that the application of an -cycle ∈ , for > 2, to a
quantum register ⨂︀=−01 |⟩ is equivalent to the rotation of magnitude 1 of the states of the qubits
[0], [
Now, let be a permutation of elements that can be decomposed into cycles as = 1 · · · ℓ. Since a constant-depth and linear-size quantum circuit can implement each cycle ℎ and since the cycles are disjoint, we can run them in parallel getting a larger constant-depth and linear-size quantum circuit , . More precisely, by denoting ℎ the length of the cycle ℎ, the circuit , has still depth equal to 6 and size bounded by 6((1 + 1) + · · · + (ℓ + 1)) = 6( + ℓ) = ().
a register of size by .
ALGORITHM 2: The algorithm constructing a quantum circuit for applying a permutation ∈ to 2 for ℎ = 1 to ℓ do 1 Initialize input wires (qubits) |0⟩ , . . . , |− 1⟩;
Input: ,
= [ [
1], [
Swap ⃒⃒ [ℎ,0], [ℎ,1]︀⟩ for = 1 to ⌈ 2ℎ ⌉ − for = 1 to ⌈ 2ℎ ⌉ − 1 do
Swap ⃒⃒ [ℎ,], [ℎ,ℎ− ]
︀⟩ 1 do Swap ⃒⃒ [ℎ,ℎ+1− ], [ℎ,]
︀⟩
To prove the second part of the statement, it is enough to see that Algorithm 2 constructs the circuit , described in the paragraph above. We remark that a gate of the form Swap |, ⟩ is interpreted as a gate that swaps the state of a qubit with its own, and therefore this does not change the state of system 5. most ∑︀ℓ
︀( ℎ=1 2 ⌈ 2ℎ ⌉ −
︀)
The algorithm consists of a for loop that is nested with two independent for loops and it takes at the functions SIZE (), LABEL (, ), EDGE (, , ) - corresponding to the circuits constructed by Algorithm 2 - can be computed in logarithmic space (refer to Remark 2.3), by a slight modification of 1 ≤ = () steps. To complete the proof, it is enough to observe that
In this paper, we presented a comprehensive framework for constructing logspace uniform families of constant-depth and linear-size quantum circuits capable of performing rotations and permutations of qubit states. We have formally demonstrated that these operations are within the complexity class QNC0, ensuring their eficient parallelizability on quantum computers.
Our work builds upon foundational concepts in quantum circuit design, providing explicit algorithms and detailed constructions that ensure practical implementability. By extending the principles of cyclic shifts to general permutations, we have shown that even complex reordering operations can be achieved with minimal computational overhead, thus reinforcing the versatility and robustness of the quantum circuit model for various computational tasks.
The systematic construction of these circuits, independent of specific rotations or permutations, ofers a significant advantage. It allows these circuits to be hardwired to a control quantum register, enabling the implementation of superpositions of rotations or permutations. This capability can be leveraged in advanced quantum algorithms, enhancing their eficiency and broadening their applicability in fields such as quantum cryptography, error correction, and complex system simulations.
There are several promising directions for future research stemming from our results. One avenue is the exploration of optimized implementations of these quantum circuits on current and near-term quantum hardware, focusing on minimizing gate errors and decoherence. Additionally, investigating the integration of these circuits with quantum algorithms for specific applications, such as large-scale data sorting and molecular simulations, could yield further insights into their practical utility. 5It is possible to have a refined version of the algorithm that recognizes such applications of the swap gate to the same qubit and does nothing. for molecular sciences, Materials Theory 6 (2021) 1–17. URL: https://api.semanticscholar.org/ CorpusID:231979408. [17] F. Bova, A. Goldfarb, R. G. Melko, Commercial applications of quantum computing, Epj Quantum
Technology 8 (2021). URL: https://doi.org/10.1140/epjqt/s40507-021-00091-1. [18] A. Pavone, C. Viola, The quantum cyclic rotation gate, in: G. Castiglione, M. Sciortino (Eds.), Proceedings of the 24th Italian Conference on Theoretical Computer Science (ITCTS 2023), volume Vol-3587 of Italian Chapter of the European Association for Theoretical Computer Science, IC-EATCS, University of Palermo, Italy, 2023, pp. 206–218. [19] N. D. Mermin, Quantum Computer Science: An Introduction, Cambridge University Press, USA, 2007. [20] E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106. [21] E. Witten, Topological quantum field theory, Communications in Mathematical Physics 117 (1988) 353 – 386. [22] R. Jozsa, An introduction to measurement based quantum computation, 2005.
arXiv:quant-ph/0508124. [23] W. K. Wootters, W. K. Wootters, W. H. Zurek, A single quantum cannot be cloned, Nature 299 (1982) 802–803. URL: https://api.semanticscholar.org/CorpusID:4339227. [24] J. Watrous, Quantum Computational Complexity, Springer New York, New York, NY, 2009, pp. 7174–7201. URL: https://doi.org/10.1007/978-0-387-30440-3_428. doi:10.1007/ 978-0-387-30440-3_428. [25] F. T. Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes,
Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1991. [26] S. Arora, B. Barak, Computational Complexity: A Modern Approach, Cambridge University
Press, 2009. [27] A. Borodin, On relating time and space to size and depth, SIAM Journal on Computing 6 (1977) 733–744. URL: https://doi.org/10.1137/0206054. doi:10.1137/0206054. [28] A. Borodin, S. Cook, N. Pippenger, Parallel computation for well-endowed rings and spacebounded probabilistic machines, Information and Control 58 (1983) 113–136. doi:https:// doi.org/10.1016/S0019-9958(83)80060-6. [29] C. C. Sims, Computational methods in the study of permutation groups, in: J. Leech (Ed.), Computational Problems in Abstract Algebra, Pergamon, 1970, pp. 169–183. doi:https://doi. org/10.1016/B978-0-08-012975-4.50020-5. [30] D. E. Knuth, Eficient representation of perm groups, Combinatorica 11 (1991) 33–43. URL: https://api.semanticscholar.org/CorpusID:18263902.