Quantum Fourier Operators and Their Application

2.1 Unitary operators

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

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:

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

where ∣0⟩and ∣1⟩are ‘swapped’, indicating a form of logical inversion. His a Hadamard transform (i.e. a DFT for a sequence of length N=2). X, Yand Zare 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×nmatrix Awith a p×qmatrix Bis defined to be

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

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

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

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

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

for the kthbasis 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 nqubit system could, for example, be ∣q⟩≡∣qn−1qn−2⋯q1q0⟩.

Eq. (15) tells us that the nqubit 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=1qubit, ∣0⟩in decimal is equivalent to ∣0⟩in binary; however,, when using n=3qubits, ∣0⟩in decimal is equivalent to ∣000⟩in binary. Hence, the number of qubits nis the anchor for the relationship between Eq. (14) and Eq. (15). Assuming nqubits, there are 2nbasis vectors that can be used to construct a quantum state. Hence, all 2nbasis 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 nqubit quantum circuits (i.e. schematic depictions of quantum operations on qubits). For instance, assume a two qubit system ∣q1q0⟩where two unitary operators Hand Zact on single qubits as

and the result is desired to be combined as

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

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

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

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

where crepresents the control bit, trepresents 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.

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 Xgate) if ∣q1⟩=∣1⟩.

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

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

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.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=1single qubit case,

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

as expected since Q=Hfor the single qubit case. Hence, it should be nn surprise that the v=1contribution 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−vcould 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 vranges from 1to n, the index jin the term ei2πj2−vexperiences successive divisions by 2(i.e. successive right shifts of its binary representation by one bit):

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

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=2and ∣j⟩=∣j1j2⟩, then

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

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 Roperator introduced in Section 2.1:

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:

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

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 nqubit QFT. For now, we provide an n=2qubit 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⟩,

1. Apply Hto ∣j1⟩so that

   ∣j1⟩⊗∣j2⟩→H∣j1⟩⊗∣j2⟩=120⟩+ei2πj12−11⟩⊗∣j2⟩E43

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 nqubits, it is possible to apply n/2swaps using, for example, tensor products involving an Xoperator (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 nqubits, it can be shown that the algorithmic complexity is On2. With N=2n, this is a considerable improvement over NlogN=n2nfor the radix-2 FFT. However, algorithmic improvements and variations have been developed that can further reduce QFT complexity to Onlogn[9, 15].