Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

In quantum computing, the Quantum Fourier Transform (QFT) is a linear transformation on quantum bits and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete ...

4
votes
2answers
53 views

Simplifying Quantum Tensor products with coefficients

$\newcommand{\ket}[1]{\lvert#1\rangle}$I am trying to show equality of two intermediate steps in the rearrangement of the Quantum Fourier transform definition, but I do not know how to rearrange the ...
8
votes
2answers
146 views

Quantum Algorithms for Convolution

I was looking into applications of Quantum Computing for machine learning and encountered the following pre-print from 2003. Quantum Convolution and Correlation Algorithms are Physically Impossible. ...
8
votes
2answers
184 views

Simplified explanation of Shor/QFT transformation as thumbtack

As a non-mathematician/software programmer I'm trying to grasp how QFT (Quantum Fourier Transformation) works. Following this YouTube video: https://www.youtube.com/watch?v=wUwZZaI5u0c And this ...
7
votes
3answers
118 views

Why does the “Phase Kickback” mechanism work in the Quantum phase estimation algorithm?

I've probably read the chapter The quantum Fourier transform and its applications from Nielsen and Chuang (10 th anniversary edition) a couple of times before and this took this thing for granted, but ...
4
votes
1answer
74 views

Example of Quantum Fourier Computation for three qubits

I am currently going through Nielsen's QC bible and having still some foundational / conceptual problems with the matter. I have tried to retrieve this $8 {\times} 8$ matrix describing the QFT of 3 ...
13
votes
4answers
266 views

Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?

It is a well known result that the Discrete Fourier Transform (DFT) of $N=2^n$ numbers has complexity $\mathcal O(n2^n)$ with the best known algorithm, while performing the Fourier transform of the ...