{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Quantum circuits and simulation of noisy algorithms\n",
"\n",
"Welcome to this hands-on session. The session is build around interactive Notebooks, that include code, explanations and tasks. Please run the code cells on your computer and follow the instructions of the tasks to deepen your learning. \n",
"\n",
"Jami Rönkkö, IQM Quantum Computers, email: jami@meetiqm.com"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Quantum Fourier Transform algorithm\n",
"\n",
"In this notebook you will learn:\n",
"- what is Quantum Fourier Transform (QFT) \n",
"- to implement it as a circuit\n",
"- to transform states between computational basis and Fourier basis with QFT\n",
"\n",
"The Quantum Fourier Transform is central part of many powerful algorithms such as *Phase Estimation* and *Shor's algorithm*. It is the discrete Fourier Transform applied to the probability amplitudes of statevectors. The classical Fourier Transform is widely used in computing and data processing. Maybe the most well known application being the transformation of a signal from time domain to frequency domain; and back again with the inverse Fourier Transform.\n",
"\n",
"Correspondingly, the Quantum Fourier Transform maps statevectors from the ususal **computational basis** (think of states like ∣0⟩, ∣1⟩, ∣011⟩ etc.) to so called **Fourier basis** (think of states like ∣+⟩=(∣0⟩+∣1⟩)/$2^{1/2}$, ∣-⟩=(∣0⟩-∣1⟩)/$2^{1/2}$ and ∣-++⟩ etc).\n",
"\n",
"In the former information (e.g. a number) is encoded in the magnitude (absolute value) of the complex probability amplitudes, whereas in the latter the information is encoded in the phase (argument) of the probability amplitudes. We will visualize this below with Bloch spheres."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Circuit implementation of QFT\n",
"QFT maps basis states from computational basis such as ∣0⟩, ∣01⟩, ∣011⟩ to their counterparts in the Fourier basis. In the Fourier basis, the basis states are equal superpositions of the computational basis states. Each Fourier basis state is defined by unique combination phases of the qubits. For example:\n",
"\\begin{align}\n",
"&\\textrm{QFT}|0\\hspace{-0.1cm}>=\\frac{1}{\\sqrt 2}|0\\hspace{-0.1cm}>+\\frac{1}{\\sqrt 2}|1\\hspace{-0.1cm}> \\\\ \n",
"&\\textrm{QFT}|01\\hspace{-0.1cm}>=\\frac{1}{2}|00\\hspace{-0.1cm}>+\\frac{i}{2}|01\\hspace{-0.1cm}>-\\frac{1}{2}|10\\hspace{-0.1cm}>-\\frac{i}{2}|11\\hspace{-0.1cm}>\\\\\n",
"&\\textrm{QFT}|011\\hspace{-0.1cm}>=\\frac{\\sqrt 2}{4}|000\\hspace{-0.1cm}>+(-\\frac{1}{4}+\\frac{i}{4})|001\\hspace{-0.1cm}>-\\frac{\\sqrt 2 i}{4}|010\\hspace{-0.1cm}>+(\\frac{1}{4}+\\frac{i}{4})|011\\hspace{-0.1cm}>-\\frac{\\sqrt 2}{4}|100\\hspace{-0.1cm}>+(\\frac{1}{4}-\\frac{i}{4})|101\\hspace{-0.1cm}>+\\frac{\\sqrt 2 i}{4}|110\\hspace{-0.1cm}>+(-\\frac{1}{4}-\\frac{i}{4})|111\\hspace{-0.1cm}>\n",
"\\end{align}\n",
"\n",
"In view of this, our QFT circuit needs two main components:\n",
"1) Hadamard gates to create the equal superposition\n",
"2) Phase gates to encode any bitstring unambiguously to the phases\n",
"\n",
"Method chosen for the second part is as follows:\n",
"- convert bit string $x$ of your state to decimal format: e.g. $x=011=3$\n",
"- rotate the phase of the first qubit by $\\frac{x}{2^n} \\times 2\\pi~$ e.g. by $\\frac{3}{2^3} \\times 2\\pi = \\frac{3\\pi}{4}$ if $x=3$\n",
"- rotate the phase of the second qubit double of that: e.g. $\\frac{3\\pi}{2}$ if $x=3$\n",
"- keep on rotating the phases always $2\\times$ that of the previous qubit until all qubits are rotated: e.g. $3\\pi$ for the third qubit if $x=3$\n",
"\n",
"For more indepth explanation and math see: https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## TASK 1

\n",
"> Read through and run the code cells below (until you reach Task 2). Once you have done this for the basic example of ∣000⟩ state, go ahead and verify the results quoted above for states ∣0⟩, ∣01⟩ and ∣011⟩.\n",
">\n",
"> Do this by changing `n_qubits` to correct value and adding `x` gates to prepare the desired computational basis state before applying QFT below."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from qiskit import *\n",
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Function that applies n qubit QFT to a circuit\n",
"def QFT(circuit, n):\n",
" for i in range(n):\n",
" circuit.barrier() # For sake of clarity, insert visual barriers between the QFT segments\n",
" circuit.h(i) # Apply Hadamard to each qubit\n",
" for j in range(i + 1, n): \n",
" circuit.cp(np.pi / 2**(j-i), i, j) # Apply controlled Phase gate with angle pi / 2^(j-i) from qubit i to all qubits with higher index j\n",
" return circuit\n",
"\n",
"# As an example, let's look at a Quantum Fourier Transform (QFT) for 3 qubits\n",
"n_qubits = 3\n",
"circuit = QuantumCircuit(n_qubits) # Create a circuit\n",
"# Add x gates here to prepare desired state\n",
"\n",
"QFT_circuit = QFT(circuit, n_qubits) # Apply our QFT function to it\n",
"\n",
"QFT_circuit.draw(output='mpl')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Execute the circuit with statevector simulator\n",
"simulator = Aer.get_backend(\"statevector_simulator\")\n",
"result = execute(QFT_circuit, backend = simulator).result()\n",
"\n",
"state = result.get_statevector()\n",
"state.draw('latex')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from qiskit.visualization import plot_bloch_multivector\n",
"\n",
"plot_bloch_multivector(state)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that ∣000⟩ state gets mapped to equal superposition of all eight three qubit basis states, where the phase of all states is zero. In Bloch sphere all the states point along the positive X-axis.\n",
"\n",
">Note: Unwanted side effect of the QFT circuit is that it actually inverts the order of qubits. Hence, if we want to keep the bit order of our register, we would have to add SWAP gates at the end of the QFT circuit. In practice with real quantum computers, people want to use as few gates as possible to mitigate the effect of noise on their circuits. So, in reality it might be better to just remember that the bit order is flipped after QFT instead of reverting it with SWAP gates."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## TASK 2

\n",
"> Naturally, computational basis states can be though of as numbers. ∣0⟩=0, ∣1⟩=1, ∣01⟩=3, ..., ∣1100⟩=12 etc. With QFT, these numbers can be encoded in the Fourier basis.\n",
"> \n",
"> Encode the numbers 4, 7 and 25 one at a time into a register of qubits in a Fourier basis. \n",
"> - start by writing the number in binary format as a bitsring\n",
"> - create a `QuantumCircuit` with enough qubits to store the bitstring\n",
"> - use X gates to encode this bitsring into a computational basis state \n",
"> - use the `QFT` function from above to transform the state into fourier basis\n",
"> - print the Bloch spheres of your qubits to visualize the phase encoding "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Use Python's bin function to convert integers to binary. Ignore the '0b' at the beginning of the string, it just specifies that the string is binary\n",
"bin(4)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Remember that in the notation here, bits are read from right to left. I.e. in '0b100' first and second bits (qubits) are 0 and third is 1. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Create circuit with as many qubits as your binary has bits\n",
"n_qubits = 3\n",
"circuit = QuantumCircuit(n_qubits)\n",
"\n",
"# Apply X gates to qubits that should store 1 \n",
"circuit.x(2)\n",
"\n",
"# Print the computational basis statevector \n",
"result = execute(circuit, backend = simulator).result()\n",
"state = result.get_statevector() \n",
"state.draw('latex')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Plot the Bloch spheres of the computatinal basis state \n",
"plot_bloch_multivector(state)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Transform the state to Fourier basis by using the QFT function we defined above (the circuit and number of qubits as input)\n",
"QFT(circuit, n_qubits)\n",
"\n",
"# Visualize the circuit\n",
"circuit.draw(output=\"mpl\")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Print the Fourier basis statevector \n",
"result = execute(circuit, backend = simulator).result()\n",
"state = result.get_statevector() \n",
"state.draw('latex')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Plot the Bloch spheres of the Fourier basis state \n",
"plot_bloch_multivector(state)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Notice that all the qubits and hence states in the Fourier basis are located at the equator of the Bloch sphere. This means that they are all equal superpositions of 0's and 1's and measurement along the ∣0⟩ - ∣1⟩ axis cannot distinguish any states. Fourier basis is however useful for information processing due to **symmetry of two-qubit phase gates**; effect also known as a **phase kickback**. We will see an example of this later in these Notebooks with the QPE algoritm."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## TASK 3

\n",
"> Read the following section and code about the inverse QFT. Write a code snippet that applies the inverse QFT function to an empty circuit and verify that it is the inverse of ordinary QFT by printing out the circuit.\n",
"> \n",
"> Try changing the number of qubits to see that this works in general."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Inverse Quantum Fourier Transform\n",
"To conclude, let us look at the inverse QFT that transforms Fourier basis states to computational basis states. We can simply use `qiskit`s `inverse` method to get a circuit that reverts the computation of another circuit. Using this, we will build a function for inverse QFT.\n",
"\n",
"When doing the inverse QFT we encounter for the first time in these notebooks the concept of **interference**. \n",
"\n",
"The question is: what happens when we apply inverse QFT circuit, that has Hadamard gates and hence creates superpositions, to a state that already is in a superposition? \n",
"As you will see below, the answer is that instead of remaining in a superposition state, the second application of Hadamart gates (and cP gates) causes probability amplitudes of states to cancel out to zero in most cases and strenghten up to one in a single case. (You will see this in Task 4 below)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Function that applies n-qubit inverse QFT to a circuit\n",
"def inverse_QFT(circuit, n):\n",
" qft_circuit = QFT(QuantumCircuit(n), n) # Create a QFT circuit\n",
" inverse_qft_circuit = qft_circuit.inverse() # Create an inverse of the circuit\n",
" circuit.append(inverse_qft_circuit, circuit.qubits[:n]) # Add the gates of inverse QFT to the first n qubits of the targer circuit\n",
" return circuit.decompose() # .decompose() allows us to see the individual gates when printing the circuit"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# First view normal QFT for comparison\n",
"n_qubits = 3\n",
"circuit = QuantumCircuit(n_qubits)\n",
"\n",
"circuit = QFT(circuit, n_qubits)\n",
"\n",
"circuit.draw(output='mpl')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Implement here a code that uses our inverse_QFT function. Draw the circuit."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## TASK 4

\n",
"> Verify that the inverse QFT undoes ordinary QFT i.e. takes statevector back to computational basis from Fourier basis. \n",
">\n",
"> Encode below the binary representation of 24 to statevector of qubit register in Fourier basis. Subsequently, transform the Fourier basis state back to computatonal basis."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Number 24 as bitstring\n",
"bin(24)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Encode it to qubit register in computational basis\n",
"n_qubits = 5\n",
"circuit = QuantumCircuit(n_qubits)\n",
"# Add x gates below\n",
"\n",
"\n",
"# Print the statevector\n",
"result = execute(circuit, backend = simulator).result()\n",
"state = result.get_statevector() \n",
"\n",
"# Plot the Bloch spheres \n",
"plot_bloch_multivector(state)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Apply QFT\n",
"circuit = QFT(circuit, n_qubits)\n",
"\n",
"# Print the statevector\n",
"result = execute(circuit, backend = simulator).result()\n",
"state = result.get_statevector() \n",
"#state.draw('latex')\n",
"\n",
"# Plot the Bloch spheres\n",
"plot_bloch_multivector(state)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Apply the inverse QFT\n",
"circuit = inverse_QFT(circuit, n_qubits)\n",
"\n",
"# Print the statevector\n",
"result = execute(circuit, backend = simulator).result()\n",
"state = result.get_statevector()\n",
"\n",
"# Plot the Bloch spheres (these should match the initial state)\n",
"plot_bloch_multivector(state)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Takeaway\n",
"\n",
"- Quantum Fourier Transform is essential subroutine for many important quantum algorithms like Shor's algorithm and Phase Estimation\n",
"- It maps statevectors from the computational basis to Fourier basis\n",
"- Inverse QFT does the opposite\n",
" \n",
"\n",
"In the next notebook we use QFT circuit as an example and consider compulsory step towards running circuits on real quantum computers: *transpilation*. "
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.13"
},
"vscode": {
"interpreter": {
"hash": "36cf16204b8548560b1c020c4e8fb5b57f0e4c58016f52f2d4be01e192833930"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}