Stack Exchange Network

Stack Exchange network consists of 175 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

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)

16
votes
4answers
549 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 ...
10
votes
3answers
908 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 ...
9
votes
2answers
322 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
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 ...
8
votes
2answers
814 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
1answer
147 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 ...
6
votes
1answer
65 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 ...
5
votes
2answers
336 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 ...
5
votes
2answers
81 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 ...
5
votes
1answer
21 views

If 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 ...
4
votes
2answers
131 views

Do the probability amplitudes of the superposition state produced by the QFT transform convey useful information?

I have been studying on Quantum Fourier Transform (QFT) by myself, and I am little bit confused about how could QFT be used. For example, if the QFT of three quantum bits is $a_1|000\rangle + ...
4
votes
1answer
101 views

Why do we use the quantum superposition for a period instead of factors in Shor's algorithm?

I understand in Shor's algorithm we use quantum computers to find the period of a function which can then be used to find N, and we increase the probability of observing the state with the correct ...
4
votes
1answer
99 views

Why does Fourier sampling allow to efficiently recover hidden subgroups?

The hidden subgroup problem is often cited as a generalisation of many problems for which efficient quantum algorithms are known, such as factoring/period finding, the discrete logarithm problem, and ...
4
votes
1answer
344 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 ...
3
votes
1answer
228 views

Implementation of inverse QFT?

When implementing the inverse quantum Fourier transform, in addition to reversing the circuit, does one need to take the conjugate transpose of the phase shift gates in the circuit as well?
3
votes
1answer
95 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 ...
3
votes
1answer
74 views

2-qubit QFT in IBMQ: controlled phase rotation

I've started getting into quantum computing in the last few days. As part of the learning, I've figured it would be fun to implement some circuits on IBMQ Experience as I learn. So now I'm stuck with ...
3
votes
1answer
57 views

Phase estimation error analysis

This question is about Lemma $7.1.2$ in Kaye, Laflamme, and Mosca's textbook: Let $\omega = \frac{x}{2^n} = 0.x_1x_2\ldots x_n$ be some fixed number. The phase estimation algorithm applied to the ...
3
votes
1answer
57 views

Quantum Fourier Transform without SWAPs

The Quantum Fourier Transform from Nielsen and Chuang chapter 5 is pictured here: In the textbook the author refers to "swap gates at the end of the circuit which reverse the order of the qubits". ...
2
votes
1answer
51 views

Why should we use inverse QFT instead of QFT in Shor's algorithm?

Why should we use inverse QFT instead of QFT in Shor's algorithm? When I tried to simulate Shor's algorithm for small numbers, I got an answer even when I used just QFT instead of inverse QFT.
1
vote
1answer
58 views

Quantum Fourier Transform on two qubits: Non orthogonal outputs

We know the QFT gives us a new orthogonal basis from the original one, however, when I apply it on two qubits, I am not getting the output vectors orthogonal. $|out(k)\rangle = \Sigma^{N-1}_{j=0} e^...
1
vote
1answer
49 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 ...
1
vote
1answer
49 views

Why are these circuits not producing the expected output?

This circuit was created on the Quirk platform. I'm trying to implement a basic case of phase estimation. For some reason, I'm getting this strange result. When the Inverse QFT is broken down, it ...
1
vote
1answer
58 views

Why are these circuits not producing the same output?

I am simulating the phase shift algorithm on the Quirk platform. Even when the endian-ness of the built-in inverse QFT gate is corrected for, the circuits still output different results. Shouldn't the ...