The Quantum Fourier Transform along with the phase estimation algorithm are the key components to Shor's factoring algorithm and many other quantum algorithms that can be used to solve problems such as factoring numbers. Due to its application to cryptography, Shor's algorithm and the Quantum Fourier Transform have been the subject of extensive research. In particular, it is exponentially faster than any known classical algorithm and therefore poses a potential threat to RSA public key cryptography. A paper published by Google "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits", shows one way to do this. For a general overview of the method, see the MIT Technology Review Article.
With recent advances in quantum computing and Google's claims of "Quantum Supremecy", such algorithms may be implemented much sooner than originally expected. Another important fact to keep in mind is that finding efficient ways to simulate such algorithms may provide a way to run them using classical computers even before the quantum technology is more wide spread. This interactive notebook covers the Quantum Fourier Transform, the Phase Estimation Algorithm, and Shor's Algorithm. It shows an implementation of these algorithms in IBM's Qiskit, and has exercises and examples for practice.
The Phase Estimation Circuit on four qubits can be seen below.
This quantum circuit diagram was rendered using quantikz, a TikZ library. If you are a Donald Knuth fan and love LaTeX too, check it out!
The basic Qiskit Code to generate a Quantum Fourier Transform on four qubits is:
from qiskit import *
%matplotlib inline
q = QuantumRegister(4)
qc = QuantumCircuit(q)
#-------------------
qc.h(0)
qc.cu1(pi/2,q[1],q[0])
qc.cu1(pi/4,q[2],q[0])
qc.cu1(pi/8,q[3],q[0])
#-------------------
qc.barrier()
qc.h(1)
qc.cu1(pi/2,q[2],q[1])
qc.cu1(pi/4,q[3],q[1])
#-------------------
qc.barrier()
qc.h(2)
qc.cu1(pi/2,q[3],q[2])
#-------------------
qc.barrier()
qc.h(3)
#-------------------
qc.draw(output='mpl')The Quantum Fourier Transform implemented in IBM's Qiskit can be seen below.
In the notebook you will find Python functions that have been defined to generate the phase estimation and quantum Fourier transform on an arbitrary number of qubits.
Interactive Jupyter Notebook on Binder
- Reach out via email to: thesingularity.research@gmail.com
- Be sure to include "Hacking the Universe" in the subject line, so that the email doesn't get overlooked.
- Write a paragraph or two about how you would like to contribute.
- Ask to Join the Discord server.
- Ask to Join the Slack Channel.
This is course material for a course on linear algebra and mathematical prerequisites for quantum computing. It contains Jupyter notebooks that can be downloaded as part of the course or opened in Binder as an online interactive notebook.