# Questions tagged [quantum-fourier-transform]

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 logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. (Wikipedia)

30 questions
Filter by
Sorted by
Tagged with
627 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 ...
1k 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 ...
365 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. ...
2k views

### Why is quantum Fourier transform required in Shor's algorithm?

I’m currently studying the Shor’s algorithm and am confused about the matter of complexity. From what I have read, the Shor’s algorithm reduces the factorization problem to the order-finding problem ...
1k 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 ...
158 views

### Shor's algorithm weaknesses & uniqueness of close rational

I'm working through a problem set, and am stuck on the following problem: a) What can go wrong in Shor’s algorithm if Q (the dimension of the Quantum Fourier Transform) is not taken to be ...
117 views

### What happens with first phase factor in QFT?

I'm using Mermin's Quantum Computer Science book to understand Shor's algorithm, but I can't figure out why one of the phase factors drops out of the probability for measuring a certain y. This is ...
40 views

### Is the quantum Fourier transform efficient if only one control-phase is allowed in the gate set

I have seen Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?. This is not a duplicate. I am familiar with the decomposition of the QFT from Nielsen&Chuang ...
70 views

### Weak Fourier Sampling vs Strong Fourier Sampling?

I'm having trouble understanding the difference between weak fourier sampling and strong fourier sampling. From this paper: ...two important variants of the Fourier sampling paradigm have been ...
405 views

### How to describe, or encode, the input vector x of Quantum Fourier Transform?

Firstly, I'd like to specify my goal: to know why QFT runs exponentially faster than classical FFT. I have read many tutorials about QFT (Quantum Fourier Transform), and this tutorial somehow explains ...
84 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 ...
145 views

52 views

### Quantum transformation equivalent to Discrete Wavelet transform

Suppose we have a matrix $A=\begin{bmatrix} 2 &4 \\ 1 & 4\\ \end{bmatrix}$, when applying the discrete wavelet transform to this matrix we get 4 parts i.e smooth part ($1\times 1$) matrix, 3 ...