SoME_Topics In-depth visual exploration of the quantum Fourier transform

About the author

I have an MSc degree in Computational and Cognitive Neuroscience, some background in Calculus and Linear Algebra and a layman's passion for theoretical physics, especially quantum mechanics.

Quick Summary

I would like to give a comprehensive explanation of the quantum Fourier transform (QFT for short), mainly in the context of Shor's algorithm. Building up a complete understanding of the QFT from the most basic concepts of quantum computing is a project I keep returning to in my free time. The content I'm planning to create for SoMe should be the synthesis of this journey. Because - in my experience - the QFT is really difficult to wrap one's head around, while the underlying mathematical objects are relatively easy to illustrate, the explanation would heavily rely on visual tools.

Target medium

An interactive dashboard that allows users to explore related concepts in a non-linear fashion, and even run simulations with custom parameters to get a deeper understanding of the mathematical relations at play. As for the technical details, I'm currently developing a Dash application in Python and deploying it on Heroku. There's already a publicly accessible, very much work in progress pilot version. Note that this dashboard is very fragile, and it might crash if multiple users are interacting with it at the same time, so apologies for that! To resolve this issue, the end product will have to be moved from the current dynamic to a static framework.

👁️ view dashboard

💻 browse source code

What kind of contribution I'm looking for

domain experts, who can provide clarifications, sanity checks and further insights into the topic
anyone with relevant background, who would like to join the creative process
any technical suggestions or help is very much welcome, too, especially with making the application scalable (moving it to a static framework as I mentioned above)

Outline

Here's a rough (and also work in progress) sketch of the contents:

1. The difference between classical and quantum bits

Here I would use the Bloch sphere as the main tool of illustration.

2. The period-finding problem

The key to factorizing a large semiprime $N$ is finding the period of the function $a^n \mod{N}$, where $a$ is a randomly chosen positive integer with some further constraints, and $n \in \mathbb{N}$. The period is the smallest integer $0 < r$ such that $a^r \mod{N} = 1$. With classical computers, finding $r$ virtually requires checking all integers between $0$ and $N$. On a quantum computer, one can compute the function value for all possible solutions in parallel, but can only observe (measure) one of those values randomly with uniform probability. With the help of the QFT, however, it is possible to get the wave function of the quantum system to interfere with itself, amplifying the relevant components and supressing the irrelevant ones. How exactly this is done will be elaborated in section 4.

3. How the classical Fourier transform relates to QFT

Grant has a great video about the classical Fourier transform, so I'll just include a link to that instead of going too deep into the details myself. The point of this section is to illustrate that the QFT is the quantum equivalent of the inverse discrete Fourier transform, and what this means in the context of a quantum system (basically, the QFT generates wave functions with given frequencies).

4. How interference influences measurement probabilities

thereby leading to a faster solution. This is probably the most difficult part of the explanation and is yet to be elaborated. Nevertheless, it will rely on the same central idea as all the sections before: an intuitive, visual demonstration.

Target audience

The explanation would assume at least advanced high-school level familiarity with linear algebra, complex numbers, binary notation and some intuition about quantum mechanics in general. (If I had to start from Schrödinger's cat, I would never get to the end 🤷‍♀️.)

Sources

Quiskit has a great lecture series about Shor's algorithm, in which they dedicate three entire lectures to the QFT and a related concept, Quantum Phase Estimation:

There are some interesting approaches to the shorter, intuitive style of explanation too, such as:

How Quantum Computers Break Encryption | Shor's Algorithm Explained by minutephysics
Hacking at Quantum Speed with Shor's Algorithm by PBS Infinite Series

In my opinion however, although these videos illuminate some interesting aspects of QFT, they don't quite succeed at painting a comprehensive picture, and get a little vague at the point where further elaboration becomes really difficult, which is the gap I hope to fill with the help of this dashboard.

Contact details

If you're interested in joining this project or would like to share your ideas, please leave a comment below ⬇️, or write me an email to [email protected]!

Jun 29 '22 22:06 dormanh

Hello @dormanh I am familiar with the FT but not QFT, but would be interested to read more about it. Regarding software, I have some experience with developing interactive dashboards in python. However I am not sure I understand what do you mean by "static framework". Could you give some examples from your code for instance?

Jul 11 '22 16:07 imadjamil

Hello @dormanh

I see thay the issue has not been closed yet. Are you still working on this topic and need domain expert on QFT?

Thanks, Valeh

Aug 04 '22 08:08 Valeh2012