Quantum Fourier Transform
The Quantum Fourier Transform acts on a quantum state \(|x\rangle = \sum_{i=0}^{N-1}x_i |i \rangle\) and maps it into a state \(\sum_{i=0}^{N-1}X_i |i\rangle\). This transformation is given by the following equation:
where \(\omega_N= e^\frac{2\pi i}{N}\), which is called the primitive \(N^{th}\) root of unity. Assuming \(|x\rangle\) is a basis state, the QFT can be written as the following mapping:
In the matrix form, the QFT can be written as a unitary matrix.
For a value of \(N = 4\), we can show that \(\omega^0=1,\ \omega^1=i,\ \omega^2=-1,\ \mathrm{and} \ \omega3=-i.\)
Note that the QFT is the transformation from the computational basis to the Fourier basis.The QFT algorithm runs in polynomial time in \(n\), i.e., \(O(n^2)\). The best estimate for classical Discrete Fourier Transform runs in an exponential time \(O(n2^n)\). We can construct the quantum circuit for QFT using \(\frac{n(n+1)}{2}\) Hadamard and controlled U1 gates, and \(\frac{n}{2}\) swap gates. The QFT does provide exponential speedup over classical DFT, but it works on the probability amplitudes of the quantum states. The classical Fourier transforms work on the complex vectors. Hence not all applications that use DFT can benefit from QFT.
For a complete derivation of the quantum transform, see [10].
The following diagram illustrates the forward QFT, drawn in a swapped order:
The inverse QFT is defined as follows:
The Inverse QFT \(\left({QFT}^{-1}\ \mathrm{or} \ IQFT\right)\) can be implemented by reversing the order of the gate operations and by negating the rotational angles.
The following diagram illustrates the inverse QFT:
Note that the Quantum Fourier Transform is unitary, and it satisfies the relation \(U_{QFT}U_{QFT}^\dagger =\ U_{QFT}^\dagger U_{QFT}=I\), where \(U_{QFT}^\dagger\) is the Hermitian adjoint of \(U_{QFT}\) and \(U_{QFT}^\dagger =\ U_{QFT}^{-1}\).
We can use the transformative capabilities of QFT to do arithmatic [21]. A few examples are included in the following sections.
Simple QFT Adder
The algorithm for the QFT based adder was introduced by Draper in 2000 and optimized the number of qubits required to perform the addition. The algorithm takes two numbers, \(a\) and \(b\), as the inputs and computes \(QFT(b)\) as the first step. The number \(a\) is added to this by the application of a set of rotations, moving the system state to \(QFT\left(a+b\right)\) in the Fourier basis.Finally, an inverse QFT transforms the system state to \((a + b)\), which produces the desired output in the computational basis.
The following diagram illustrates the adder circuit, sandwitched between the QFT and Inverse-QFT layers:
Example code to perform addition using QFT:
Note
Be sure to use your API token and your account name.
Step 1. Import the required modules and obtain the backend
import QuantumRingsLib
from QuantumRingsLib import QuantumRegister, AncillaRegister, ClassicalRegister, QuantumCircuit
from QuantumRingsLib import QuantumRingsProvider
from QuantumRingsLib import job_monitor
from QuantumRingsLib import JobStatus
from matplotlib import pyplot as plt
import numpy as np
provider = QuantumRingsProvider(token =<YOUR_TOKEN_HERE>, name=<YOUR_ACCOUNT_NAME_HERE>)
backend = provider.get_backend("scarlet_quantum_rings")
shots = 100
provider.active_account()
Step 2. Define the core methods as reusable compoments
def set_reg(qc, input, q, n):
"""
Sets a quantum register with an input value.
Args:
qc (QuantumCircuit):
The quantum circuit to use
input (int):
The number to be stored in the qubit register
q (QuantumRegister):
The qubit register which is to be programmed with the input number
n (int):
The width of the qubit register to use.
Returns:
None.
"""
for i in range (0, n):
if ((1 << i) & input ):
qc.x(q[i])
return
def add_cct(qc,a, b, n):
"""
The adder circuit in the Fourier Basis
Args:
qc (QuantumCircuit):
The quantum circuit
a (QuantumRegister):
The source register
b (QuantumRegister):
The target register
n (int):
The number of qubits in the registers to use
Returns:
None
"""
while (n):
for i in range(n, 0, -1):
qc.cu1(math.pi/2**(n - i), a[i-1], b[n-1])
n -= 1
qc.barrier()
return
def iqft_cct(qc, b, n):
"""
The inverse QFT circuit
Args:
qc (QuantumCircuit):
The quantum circuit
b (QuantumRegister):
The target register
n (int):
The number of qubits in the registers to use
Returns:
None
"""
for i in range (n):
for j in range (1, i+1):
# for inverse transform, we have to use negative angles
qc.cu1( -math.pi / 2** ( i -j + 1 ), b[j - 1], b[i])
# the H transform should be done after the rotations
qc.h(b[i])
qc.barrier()
return
def qft_cct(qc, b, n):
"""
The Forward QFT circuit
Args:
qc (QuantumCircuit):
The quantum circuit
b (QuantumRegister):
The target register
n (int):
The number of qubits in the registers to use
Returns:
None
"""
while (n):
qc.h(b[n-1])
for i in range (n-1, 0, -1):
qc.cu1(math.pi / 2** (n - i ), b[i - 1], b[n-1])
n -= 1
qc.barrier()
return
def add_qft(qc, input1, input2, a, b, n):
"""
The adder using QFT.
Args:
qc (QuantumCircuit):
The quantum circuit
input1 (int):
The first number
input2 (int):
The second number to add.
a (QuantumRegister):
The source register
b (QuantumRegister):
The target register. Computed value is stored in this register
n (int):
The number of qubits in the registers to use
Returns:
None
"""
set_reg(qc, input1, a, n)
set_reg(qc, input2, b, n)
qft_cct(qc, b, n)
add_cct(qc, a, b, n)
iqft_cct(qc, b, n)
return
def plot_histogram (counts, title=""):
"""
Plots the histogram of the counts
Args:
counts (dict):
The dictionary containing the counts of states
titles (str):
A title for the graph.
Returns:
None
"""
fig, ax = plt.subplots(figsize =(10, 7))
plt.xlabel("States")
plt.ylabel("Counts")
mylist = [key for key, val in counts.items() for _ in range(val)]
unique, inverse = np.unique(mylist, return_inverse=True)
bin_counts = np.bincount(inverse)
plt.bar(unique, bin_counts)
maxFreq = max(counts.values())
plt.ylim(ymax=np.ceil(maxFreq / 10) * 10 if maxFreq % 10 else maxFreq + 10)
# Show plot
plt.title(title)
plt.show()
return
Step 3. Execute the algorithm, plot the results, and clean up
# obtain the hidden string from the user
input_a = int(input("Enter the first number as the binary value: "), 2)
input_b = int(input("Enter the second number as the binary value: "), 2)
# determine the number of qubits required to represent the hidden string
# add one more qubit to handle the carry. This is essentially needed in the second bank, though.
numberofqubits = max(input_a.bit_length(), input_b.bit_length()) + 1
print("Number of qubits required in each register: ", numberofqubits)
q1 = QuantumRegister(numberofqubits , 'a')
q2 = QuantumRegister(numberofqubits , 'b')
c = ClassicalRegister(numberofqubits , 'c')
qc = QuantumCircuit(q1, q2, c)
add_qft(qc, input_a, input_b, q1, q2, numberofqubits)
for i in range (q2.size()):
qc.measure(q2[i])
job = backend.run(qc, shots)
job_monitor(job)
result = job.result()
counts = result.get_counts()
# clean-up the circuit components
del q1
del q2
del c
del qc
plot_histogram(counts,"")
# clean-up
del result
del job
An example histogram is shown below for the input numbers \(111111\) and \(1\). The result is \(1000000\) as expected.
Controlled QFT Adder
With the help of doubly controlled U1 gates, we can construct a fully controlled QFT adder.
The adder circuit shown in the following block diagram illustrates this concept:
This circuit produces an output of \(|a+b+s\rangle\). However, if we start \(|s\rangle\) in a state of \(|0\rangle\), then it produces an output of \(|a+b\rangle1\). Similarly, we can produce controlled versions of QFT and IQFT operations.
Methods for implementing the Controlled QFT Adder
def c_add_cct(qc, a, b, offset, control, n):
"""
The controlled adder circuit module.
Args:
qc (QuantumCircuit):
The quantum circuit
a (QuantumRegister):
The source register
b (QuantumRegister):
The target register. Computed value is stored in this register
offset (int):
The starting qubit in register b to work from
n (int):
The number of qubits in the registers to use
Returns:
None
"""
while (n):
for i in range(n, 0, -1):
ccu1(qc, math.pi/2**(n - i), control, a[i-1], b[n-1+offset])
qc.barrier()
n -= 1
return
def c_iqft_cct (qc, b, offset, control, n):
"""
The controlled Inverse-QFT.
Args:
qc (QuantumCircuit):
The quantum circuit
b (QuantumRegister):
The target register.
offset (int):
The starting qubit in register b to work from
control (int):
The index number of the control qubit
n (int):
The number of qubits in the registers to use
Returns:
None
"""
for i in range (n):
for j in range (1, i+1):
# for inverse transform, we have to use negative angles
ccu1( qc, -math.pi / 2** ( i -j + 1 ), control, b[j - 1+offset], b[i+offset])
# the H transform should be done after the rotations
qc.ch(control, b[i+offset])
qc.barrier()
return
def c_qft_cct(qc, b, offset, control, n):
"""
The controlled QFT.
Args:
qc (QuantumCircuit):
The quantum circuit
b (QuantumRegister):
The target register.
offset (int):
The starting qubit in register b to work from
control (int):
The index number of the control qubit
n (int):
The number of qubits in the registers to use
Returns:
None
"""
while (n):
qc.ch(control, b[n + offset - 1])
for i in range (n-1, 0, -1):
ccu1(qc, math.pi / 2** (n - i), control, b[i - 1 + offset], b[n + offset - 1])
n -= 1
qc.barrier()
return
def c_add_qft(qc, a, b, offset, control, n):
"""
The controlled Adder using QFT.
Args:
qc (QuantumCircuit):
The quantum circuit
a (QuantumRegister):
The source register
b (QuantumRegister):
The target register.
offset (int):
The starting qubit in register b to work from
control (int):
The index number of the control qubit
n (int):
The number of qubits in the registers to use
Returns:
None
"""
c_qft_cct(qc, b, offset, control, n)
c_add_cct(qc, a, b, offset, control, n)
c_iqft_cct(qc, b, offset, control, n)
return
def ccu1(qc, theta, q0, q1, q2):
"""
The controlled Adder using QFT.
Args:
qc (QuantumCircuit):
The quantum circuit
theta (float):
The rotational angle. See :ref:`QuantumCircuit.u1`
q0 (int):
The first control qubit.
q1 (int):
The second control qubit.
q2 (int):
The target qubit.
Returns:
None
"""
qc.cu1(theta/2, q1, q2)
qc.cx(q0, q1)
qc.cu1(-theta/2, q1, q2)
qc.cx(q0, q1)
qc.cu1(theta/2, q0, q2)
return
QFT based Multiplier
By stacking up a series of controlled QFT adder blocks, we can implement a multiplication module. Consider the following block diagram.
The above quantum circuit multiplies two \(n-\) bit numbers \(a\) and \(b\) by performing \(n\) successive controlled QFT additions. The result is stored in the register \(s\) with size \(2n\). The first controlled QFT adder block, labeled as \(2^0\sum_{}^{}\), has the least significant qubit of register \(a_n\) as the control qubit. Register \(s\) is initially prepared in the state \(|0\rangle\).The adder block first performs a QFT on register \(s\), producing the state \(|ϕ(0)\rangle\). After this, the \(2^0\sum_{}^{}\) block applies a series of conditional phase rotation gates to evolve the state into \(|ϕ(0+b)\rangle\). This block is controlled by the least significant qubit of register \(a\). So the state can be written as \(|ϕ(0+a_n 2^0 b) \rangle\).
Finally, the block applies an inverse QFT, moving the system state to \(|0+a_n 2^0 b \rangle\). The qubit \(a_(n-1)\) controls the second controlled QFT adder \(2^1\sum_{}^{}\). The scale factor for the phase addition at this level is \(2^1\). We can calculate the output state of this stage to be \(|0+a_n 2^0 b +a_(n-1) 2^1 b \rangle.\) We continue to apply the rest of the controlled QFT adder blocks in the circuit. When all the blocks are added, the output state becomes:
Code for implementing the quantum multiplier
def mult_cct(qc, input1, input2, a, b, s, n):
"""
The quantum multiplier circuit using QFT
This circuit calculates s = a * b.
Args:
qc (QuantumCircuit):
The quantum circuit
input1 (int):
The multiplicand
input2 (int):
The multiplier
s (QuantumRegister):
The qubit register holding product a * b
Note: s has two times the length of a and b
a (QuantumRegister):
The qubit register for multiplicand
b (QuantumRegister):
The qubit register for multiplier
n (int)
The length of the registers
Returns:
None.
"""
set_reg(qc, input1, a, n)
set_reg(qc, input2, b, n)
for i in range (0, n):
c_add_qft(qc, b, s, i, a[i], n)
return
Code for testing the quantum multiplier
def test_mult( input1, input2):
numberofqubits = max(input1.bit_length(), input2.bit_length(), 4)
a = QuantumRegister(numberofqubits , 'a')
b = QuantumRegister(numberofqubits , 'b')
s = QuantumRegister(numberofqubits*2 , 's')
c = ClassicalRegister(numberofqubits*2 , 'c')
qc = QuantumCircuit(a, b, s, c)
mult_cct(qc, input1, input2, a, b, s, numberofqubits)
for i in range (numberofqubits*2):
qc.measure(s[i],c[i])
job = backend.run(qc, shots)
job_monitor(job) #, quiet = False)
result = job.result()
counts = result.get_counts()
print (counts)
if (1 < len(counts)):
print("Error: More than one result!")
myproduct = 0
else:
scounts = str(counts)
myproduct = int("0b"+scounts[scounts.index("{")+2:scounts.index(":")-1], 2)
# clean-up
del qc
del c
del s
del b
del a
del job
del result
return myproduct
shots = 10
input_a = int(input("Enter the multiplcand: "))
input_b = int(input("Enter the multiplier: "))
res = test_mult(input_a, input_b )
print ("Result is: ", res)