1. Introduction

The quantum Fourier transform (QFT) has been applied in a number of different contexts within the field of quantum computation [1, 2, 3]. As this operator is central to so many quantum algorithms, a major thrust of current research is directed toward its efficient implementation [4, 5, 6, 7, 8, 9]. The QFT calculation is, to a degree, based upon the discrete Fourier transform (DFT) where, given a discrete sequence

x=x0x2⋯xN−1E1

of length N, the DFT of x can be computed as

DFTx=FxE2

with DFT matrix elements

Fjk=1Nei2πNjkj,k=0,1,⋯,N−1E3

Since the DFT matrix is N×N, the computational complexity of computing DFTx is ON2. If the input sequence length of the input sequence x can be written as N=2n (i.e. a power of two for some positive integer, n), there exist fast Fourier transform (FFT) implementations that can compute DFTx with ONlogN complexity. While there are other FFT implementations that do not require N=2n, the ‘radix-2’ implementation will be the starting point as it is relevant when introducing quantum computational bases. Before elevating the DFT to its quantum description, in Section 2 we will take a brief tour of quantum computation in order to provide some necessary context. We will then, in Section 3, develop the QFT operator and discuss its quantum implementation. Finally, in Section 4, we will discuss the QFT in the context of universal computation and its formulation in terms of permutation matrices.

2. Quantum computation

A starting point for quantum computation begins with choosing a qubit representation for the computational basis [3]

∣0⟩≡10,∣1⟩≡01E4

This qubit basis forms a complete orthonormal set so that any single qubit quantum mechanical state can be written as the linear superposition

∣ψ⟩=α∣0⟩+β∣1⟩.E5

where the coefficients α and β are complex scalars. If ⟨ψ∣ represents the Hermitian conjugate of ∣ψ⟩, according to quantum mechanics, the inner product

ψψ=α2+β2=1E6

is normalized so that ψ represents a probability density function. This implies that, at any given instance in its time evolution, a quantum system can simultaneously be in the logical states ∣0⟩ and ∣1⟩ with their associated probabilities α2 and β2. This is in stark contrast to classical digital computation whose operations must always exclusively evaluate to a value of either 0 or 1. Quantum computation allows an algorithm to simultaneously visit both logical states ∣0⟩ and ∣1⟩ of a single qubit. If n qubits (i.e. multiple qubits) are applied, then a quantum system, in principal, has the potential to simultaneously visit 2n logical states (again, with their associated probabilities). This exponential computational capacity is the source of quantum parallelism. However, there is a catch. Only when some observable is measured can we ascertain the current logical state of the system. Hence, quantum computers require large samples of measurements in order to build up the statistics necessary to determine the outcome of any given algorithm.

2.1 Unitary operators

The time evolution operator U associated with a quantum system must be unitary meaning that

U†U=IE7

where U† is the conjugate transpose of U. A major implication of this requirement is that the forward time system evolution must (at least mathematically) be reversible. This requirement, in turn, constrains computations that are implemented by quantum operators to be reversible. Therefore, logical operations such as AND, OR, and XOR (exclusive-or) would not be a quantum mechanical possibility unless some additional input information were to be preserved. This is because, in the absence of information about the input, measuring the output of these operations is not enough to ascertain the values of the inputs. Hence, these boolean processes, by themselves, are not reversible. However, there is a theory of reversible computation that can augment these logical operations so that input information is recoverable. Furthermore, much thought has gone into phrasing reversible computation in the context of unitary operators. Given the discussion so far, it is appropriate to give a short list of standard single qubit operators:

I=1001,H=12111−1,Rϕ=100eiϕE8

X=0110,Y=0−ii0,Z=100−1E9

The reader can check that these are all unitary. As a simple example of how to apply such operators, consider the action of X on the basis vector ∣0⟩

X∣0⟩=0110∣0⟩=011010=01=∣1⟩E10

where ∣0⟩ and ∣1⟩ are ‘swapped’, indicating a form of logical inversion. H is a Hadamard transform (i.e. a DFT for a sequence of length N=2). X, Y and Z are Pauli matrices. Rϕ is a generalization of Z=Rπ and I=R0. While these are single quhit operators, the next sections discuss how they can be extended to the multiple qubit case. Amazingly, this set of quantum operators can be applied to devise some very powerful quantum algorithms (e.g. QFT computation) [3, 10].

2.2 Tensor product (Kronecker product)

The Kronecker product of an m×n matrix A with a p×q matrix B is defined to be

A⊗B=a11Ba12B⋯a1nBa21Ba22B⋯a2nB⋮⋮⋮⋮am1Bam2B⋯amnB.E11

Furthermore, assuming the dimensions are compatible for matrix multiplication, the following identity often proves useful

A⊗BC⊗D=AC⊗BDE12

for matrices A,B,C,D.

The computational basis can be extended to any number of qubits using the tensor product. For example, if two qubits are required for the computational space, using Eq. (2), the basis becomes

∣0⟩≡∣00⟩=∣0⟩⊗∣0⟩=10⊗10=1000∣1⟩≡∣01⟩=∣0⟩⊗∣1⟩=10⊗01=0100∣2⟩≡∣10⟩=∣1⟩⊗∣0⟩=01⊗10=0010∣3⟩≡∣11⟩=∣1⟩⊗∣1⟩=01⊗01=0001E13

To generalize this example for n qubits, the set of computational basis vectors can, for the sake of brevity, be labeled in base 10 as

0⟩1⟩2⟩⋯2n−1⟩.E14

On the other hand, in order to highlight the qubit values, this basis can equivalently be expressed in base 2 as

∣k1k2⋯kn⟩=∣k1⟩⊗∣k2⟩⊗∣⋯⊗∣kn⟩E15

where ki∈01 for i=1,⋯,n. In other words, k1k2⋯kn represents the binary expansion

k=k12n−1+k22n−2+⋯+kn−121+kn20=∑t=1nkt2n−tE16

for the kth basis vector ∣k⟩≡∣k1k2⋯kn⟩. We have chosen this bit index ordering as it will prove convenient for the QFT formulation in the next section. An equally acceptable (and, quite typical) bit index convention for an n qubit system could, for example, be ∣q⟩≡∣qn−1qn−2⋯q1q0⟩.

Eq. (15) tells us that the n qubit basis is derived from the tensor product of single qubits. This is important to keep in mind in order to avoid confusion when using the symbol ∣0⟩. For example, when using n=1 qubit, ∣0⟩ in decimal is equivalent to ∣0⟩ in binary; however,, when using n=3 qubits, ∣0⟩ in decimal is equivalent to ∣000⟩ in binary. Hence, the number of qubits n is the anchor for the relationship between Eq. (14) and Eq. (15). Assuming n qubits, there are 2n basis vectors that can be used to construct a quantum state. Hence, all 2n basis vectors will simultaneously evolve with their associated probabilities; again, this is the source of quantum parallelism.

2.3 Quantum circuits

One particularly useful application of Eq. (12) arises when building up n qubit quantum circuits (i.e. schematic depictions of quantum operations on qubits). For instance, assume a two qubit system ∣q1q0⟩ where two unitary operators H and Z act on single qubits as

H∣q1⟩,Z∣q0⟩E17

and the result is desired to be combined as

H∣q1⟩⊗Z∣q0⟩.E18

Eq. (12) tells us that this action is equivalent to

H⊗Zq1⟩⊗q0⟩.E19

However, by construction, ∣q1⟩⊗∣q0⟩=∣q1q0⟩. Therefore,

H∣q1⟩⊗Z∣q0⟩=H⊗Z∣q1q0⟩E20

making it straightforward to develop multiple qubit quantum systems from unitary operators. The schematic representation of H⊗Z∣q1q0⟩ is show in Figure 1.

Figure 1.
Two qubit quantum circuit for H⊗Z∣q1q0⟩.

With the groundwork laid for multiple qubits, it becomes possible to introduce more unitary operators that facilitate reversible computation. For example, the controlled NOT (CNOT) function can be phrased as a two qubit reversible XOR operator

CNOT=1000010000010010.E21

where c represents the control bit, t represents the target XOR function and ∣q1q0⟩=∣ct⟩. This operator is a permutation matrix that is consistent with Table 1 in that it swaps the ∣11⟩ and ∣10⟩ qubits. The XOR operation, by itself, can act as an irreversible controlled NOT operation. For the sake of quantum computation, the CNOT operator is unitary and a reversible XOR function is achieved because the control bit ∣q1⟩ is preserved from input to output.

cin	tin	cout	tout
0	0	0	0
0	1	0	1
1	0	1	1
1	1	1	0

Table 1.

Controlled NOT.

There exist powerful tools for the simulation of quantum operations (referred to as ‘quantum gates’) and for the rendering of multiple qubit quantum circuits [11]. Figure 2 shows a schematic representation of the CNOT circuit corresponding to Table 1. In this circuit, the control bit is used to swap the target ∣q0⟩ (using an X gate) if ∣q1⟩=∣1⟩.

Figure 2.
Two qubit CNOT quantum circuit swap of ∣11⟩ and ∣10⟩ using Qiskit [11].

For the sake of this work, we point out that an equally valid interpretation of the quantum CNOT function can be realized if the roles of the control and target are interchanged where ∣q1q0⟩=∣tc⟩ (see Table 2). In this case the CNOT operator becomes

tin	cin	tout	cout
0	0	0	0
0	1	1	1
1	0	1	0
1	1	0	1

Table 2.

Controlled NOT where ∣q1q0⟩=∣tc⟩.

CNOT=1000000100100100.E22

which is a permutation matrix that swaps the ∣11⟩ and ∣01⟩ qubits and corresponds to the circuit in Figure 3.

Figure 3.
Two qubit CNOT quantum circuit swap of ∣11⟩ and ∣01⟩.

We shall have more to say about this implementation in the following sections. For now, with this brief overview of quantum computation, we can now introduce the quantum Fourier transform.

3. The quantum Fourier transform

It should be clear that the DFT matrix in Eq. (2) is unitary where

F†F=IE23

and F† is the Hermitian conjugate of F. Because of this unitarity, the potential for using the DFT within the context of quantum computation naturally follows. However, such an application requires a decomposition involving tensor products of unitary operations typically applied in quantum computation. As with the FFT, the choice of the decomposition dictates the algorithmic complexity. There is much introductory literature available regarding the QFT [3, 12, 13, 14]. Given a specific quantum algorithm where the QFT is applied, current research endeavors reside in attempts to improve the computational complexity [4, 7, 9, 15, 16].

The QFT matrix is defined as

Q=1N∑j=0N−1∑k=0N−1ei2πNjk∣k⟩⟨j∣.E24

For example, with N=2n and n = 1, we recover the Hadamard matrix

Q=12111−1,E25

or, for n = 2,

Q=1211111i−1−i111−11−i−1i.E26

As expected, this operator is unitary where, with

Q†=1N∑j=0N−1∑k=0N−1e−i2πNjk∣j⟩⟨k∣,E27

it should be clear that

QQ†=1N∑j=0N−1∑k=0N−1ei2πNjkk⟩⟨j1N∑j′=0N−1∑k′=0N−1e−i2πNj′k′∣j′⟩⟨k′∣=1N∑k′=0N−1∑k=0N−1∑j′=0N−1∑j=0N−1ei2πNjk−j′k′∣k⟩jj′⟨k′∣=1N∑k′=0N−1∑k=0N−1∑j′=0N−1∑j=0N−1ei2πNjk−j′k′δj′j∣k⟩⟨k′∣=1N∑k′=0N−1∑k=0N−1∑j=0N−1ei2πNjk−k′∣k⟩⟨k′∣=1N∑k′=0N−1∑k=0N−1Nδk′k∣k⟩⟨k′∣=∑k=0N−1∣k⟩⟨k∣=I.E28

In general, given a state vector

∣ψ⟩=∑j=0N−1aj∣j⟩E29

the QFT operates on ∣ψ⟩ to form

∣Ψ⟩=QFTψ⟩=QFT∑j=0N−1ajj⟩=∑j=0N−1ajQFTj⟩=∑j=0N−1ajQ∣j⟩.E30

Given this result, let us consider the QFT of a single n qubit basis vector ∣j⟩ where N=2n. First, observe that while

QFTj⟩=Q∣j⟩=12n/2∑j′=0N−1∑k=0N−1ei2πNj′k∣k⟩j′j=12n/2∑j′=0N−1∑k=0N−1ei2πNj′k∣k⟩δj′j=12n/2∑k=02n−1ei2π2njk∣k⟩,E31

given Eqs. (15) and (16), it will be more helpful to express this relation as

QFTj⟩=12n/2∑k1=01∑k2=01⋯∑kn=01ei2πj∑t=1nkt2−t∣k1k2⋯kn⟩.=12n/2∑k1=01∑k2=01⋯∑kn=01ei2πjk12−1+k22−2+⋯+kn−12−n−1+kn2−n∣k1k2⋯kn⟩.=12n/2∑k1=01∑k2=01⋯∑kn=01ei2πjk12−1+k22−2+⋯+kn−12−n−1+kn2−n∣k1⟩⊗∣k2⟩⊗∣⋯⊗∣kn⟩.=12n/2⊗v=1n∑kv=01ei2πjkv2−v∣kv⟩.E32

This leads to the result that

Q∣j⟩=12n/2⊗v=1n0⟩+ei2πj2−v1⟩.E33

3.1 QFT qubit representation

To forge a path toward efficient implementation, it is important to recognize how Eq. (33) can be decomposed into a set of operators relevant to quantum computation (see Section 2.1). First, consider the n=1 single qubit case,

Q∣j⟩=120⟩+ei2πj21⟩.E34

Then, for each qubit state ∣j⟩=∣0⟩,∣1⟩, it follows that

Q∣0⟩=120⟩+1⟩=1211Q∣1⟩=120⟩−1⟩=121−1E35

as expected since Q=H for the single qubit case. Hence, it should be nn surprise that the v=1 contribution to Eq. (10) should be a Hadamard gate.

To handle the phase factors in the other contributions to the tensor product (where v≥2), the keen eye will recognize that the terms ei2πj2−v could lead to a unitary quantum mechanical operator. Before leveraging this observation in a QFT algorithm, it will be helpful to consider the qubit representation ∣j⟩=∣j1j2⋯jn⟩. As the index v ranges from 1 to n, the index j in the term ei2πj2−v experiences successive divisions by 2 (i.e. successive right shifts of its binary representation by one bit):

v=1:j2−1⇒j1j2⋯jn−1.jnv=2:j2−2⇒j1j2⋯jn−2.jn−1jn⋮v=n−1:j2−n−1⇒j1.j2⋯jn−1jnv=n:j2−n⇒0.j1j2⋯jn−1jnE36

Since these values appear in the phase factor, the integer parts will only result in integer multiples of 2π and can therefore be discarded. Eq. (33) can then be expressed as

QFTj⟩=12n/2[0⟩+ei2πjn2−11⟩⊗0⟩+ei2πjn−12−1+jn2−21⟩⊗⋯⋯⊗0⟩+ei2πj12−1+j22−2+⋯+jn2−n1⟩.E37

It is often this version of the QFT that is used as a starting point for quantum circuit implementation when N=2n [3].

As an example, consider the two qubit case where n=2 and ∣j⟩=∣j1j2⟩, then

Q∣j⟩=Q∣j1j2⟩=120⟩+ei2πj22−11⟩⊗0⟩+ei2πj12−1+j22−21⟩E38

If we let ∣j1j2⟩=∣01⟩, then

Q∣j⟩=Q∣01⟩=120⟩+ei2π12−11⟩⊗0⟩+ei2π02−1+12−21⟩=120⟩−1⟩⊗0⟩+i1⟩=1200⟩+i01⟩−10⟩−i11⟩E39

which corresponds to the column ∣01⟩ entries in Eq. (26). If not already obvious, it should be emphasized that the tensor product is not commutative and that consistent qubit ordering is instrumental to the success of this calculation.

3.2 Quantum implementation

Based upon Eq. (37), it is sensible to introduce an iterable version of the R operator introduced in Section 2.1:

Rv=100ei2π2v.E40

Furthermore, because each qubit contribution contains phase terms involving the binary expansion of j, one approach to addressing these interactions is to introduce a controlled version of Rv:

CRv=I00Rv.E41

This operator can be used to induce the correct phase factor as follows. Assume tc⟩ is the target/control structure for single qubits jrjs were s>r in the binary representation of ∣j⟩. Then, the following holds true

CRv∣jr0⟩=∣jr0⟩CRv∣jr1⟩=ei2π2vjr∣jr1⟩E42

Hence, the control bit determines when to introduce the phase factor involving the target bit.

The goal of this section is to introduce enough nomenclature in order to put the next section of this work in context. The reader is encouraged to visit the provided references in order to fill in the details of a generalized quantum circuit that can implement an n qubit QFT. For now, we provide an n=2 qubit example to illustrate an algorithm for performing the QFT. Whatever principled series of operations is chosen, the goal of the quantum algorithm (and, hence, the associated quantum circuit) is to reproduce Eq. (11). Starting with ∣j⟩=∣j1j2⟩,

Apply H to ∣j1⟩ so that
∣j1⟩⊗∣j2⟩→H∣j1⟩⊗∣j2⟩=120⟩+ei2πj12−11⟩⊗∣j2⟩E43
Apply CR2 to target qubit j1 controlled by j2. This yields
120⟩+ei2πj12−11⟩⊗∣j2⟩→120⟩+ei2πj22−2+j12−11⟩⊗∣j2⟩E44
Apply H to ∣j2⟩

120⟩+ei2πj22−2+j12−11⟩⊗∣j2⟩→120⟩+ei2πj22−2+j12−11⟩⊗120⟩+ei2πj22−11⟩=120⟩+ei2πj221⟩⊗0⟩+ei2πj211⟩E45

Comparing this result with either Eq. (33) or Eq. (37), it is clear that this algorithm, derived using quantum reversible operators, recovers the QFT from Eq. (38) with one slight difference: the bit ordering is reversed. Given n qubits, it is possible to apply n/2 swaps using, for example, tensor products involving an X operator (see Section 2.1) in order to reverse the bit order. Such bit reversal permutations are reminiscent of the radix-2 FFT algorithm. If one generalizes this algorithm to n qubits, it can be shown that the algorithmic complexity is On2. With N=2n, this is a considerable improvement over NlogN=n2n for the radix-2 FFT. However, algorithmic improvements and variations have been developed that can further reduce QFT complexity to Onlogn [9, 15].

4. QFT permutations

Universal computation, by its very nature, must involve some set of permutation operators [17, 18, 19, 20]. As with other universal gates applied in quantum computation, in this section, we show that the QFT can generate operators that have the properties of a permutation. Consider a successive application of the QFT such as Q2=QQ and let us analyze the matrix elements of such an operation:

QQj,k=1N∑m=0N−1(ei2πNjm∣j⟩⟨m∣)(ei2πNmk∣m⟩⟨k∣)=1N∑m=0N−1ei2πNmj+kmm∣j⟩⟨k∣=0j+k≠0modN1j+k=0modN≡PQ2j,k.E46

For an n qubit system ∣qn−1⋯q1q0⟩, it should be clear that PQ2 is a permutation operator that leaves the position of ∣q0⟩ unchanged and inverts the order of the remaining qubits to form ∣q1⋯qn−1q0⟩. For example, the CNOT operator in Eq. (22) is equal to PQ2 for n=2

CNOT=Q2=1000000100100100=PQ2E47

having properties similar to that of a Sylvester shift matrix (i.e. a generalization of a Pauli matrix). It is sensible that a CNOT operation followed by a CNOT operation should result in the identity operation and, hence, that PQ2PQ2=Q4=I (i.e. a double inversion recovers the original qubit sequence). These results can be generalized for any n. For example, with n=3, Eq. (46) becomes

PQ2=1000000000000001000000100000010000001000000100000010000001000000E48

which, after the appropriate sequence of swaps, can be transformed into a Toffoli (CCNOT) gate. Hence, PQ2 can be thought of as a generalization of swap permutation operators and the QFT can be phrased as its square root. For example, it is common to define a two qubit swap operator as

Sw=1000001001000001E49

along with its square root

Sw=10000121+i121+i00121+i121+i00001.E50

In a similar manner, Eq. (46) leads us to the following

Theorem 1Given theN×Ninversion permutation matrix defined as

PQ2j,k=0j+k≠0mod N1j+k=0mod N,E51

it follows that

Q=PQ2E52

where Q is a QFT matrix.

In addition, given that Q4=I we have the following

Corollary 1 Any algorithm that iteratively applies the QFT can result in only one of the following outcomes

Qk=PQ2 if k=1mod 4.
Qk=PQ2 if k=2mod 4.
Qk=Q−1 if k=3mod 4.
Qk=I if k=0mod 4.

These results indicate a deeper connection between universal computation, permutations and the QFT. Furthermore, decomposing the QFT calculation into a product of permutations indicates a potential for reducing the computational complexity of QFT implementations.

5. Conclusions

In this work, we have revisited the quantum Fourier transform which is central to many algorithms applied in the field of quantum computation. As a natural extension of the discrete Fourier transform, the QFT can be implemented using efficient tensor products of quantum operators. Part of the thrust of current research deals with reducing the QFT computational complexity. With this goal in mind, we have phrased the QFT as a permutation operator. Future research will be directed toward quantum circuit implementation using QFT permutation operators within the context of universal computation.

Acknowledgments

This research is funded by a grant from the National Science Foundation NSF #1560214.

Diego de Ortueta

Chapters authored

Related collaborators

Seyed-Farzad Mohammadi

David Varssano

Hadi Z-Mehrjardi

Maryam Tahvildari

Meritxell Vilaseca

Fernando Díaz-Doutón

Sergio Luque

Mikel Aldaba

Montserrat Arjona

Jaume Pujol