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)

Filter by
Sorted by
Tagged with
18
votes
4answers
1k 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 ...
16
votes
3answers
4k 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 ...
12
votes
1answer
705 views

How does Fourier sampling actually work (and solve the parity problem)?

I'm writing with respect to part I and part II of the Fourier sampling video lectures by Professor Umesh Vazirani. In part I they start with: In the Hadamard Transform: $$|0...0\rangle \to \sum_{\{...
9
votes
2answers
3k 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 ...
9
votes
2answers
2k 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 ...
9
votes
3answers
850 views

Does the quantum Fourier transform have many applications beyond period finding?

(This is a somewhat soft question.) The quantum Fourier transform is formally quite similar to the fast Fourier transform, but exponentially faster. The QFT is famously at the core of Shor's ...
9
votes
2answers
775 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
570 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 ...
7
votes
2answers
342 views

Shor's algorithm: initialization of second register

I am trying to understand Shor's algorithm. I am not quite sure why the initialization, indicated as $|1\rangle$ in the below image at the bottom left is chosen as it is? I understand the modular ...
6
votes
2answers
738 views

Why can the QFT be replaced by Hadamard gates?

I'm studying Shor's Algorithm. In the book, author explains QFT can be replaced by Hadamard gates? Why this process is possible?? Thank you everybody. This is QPE. I attach part of book!!
6
votes
2answers
1k 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 ...
6
votes
1answer
429 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.
6
votes
1answer
2k 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?
6
votes
2answers
511 views

How to generalize the relationship HXH = Z for higher dimensions

Concerning the Hadamard gate and the Pauli $X$ and $Z$ gates for qubits, it is straightforward to show the following relationship via direct substitution: $$ HXH = Z.\tag{1}$$ And I would like to ...
6
votes
1answer
208 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 ...
6
votes
1answer
73 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 ...
6
votes
1answer
126 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
326 views

Does the Quantum Fourier Transform (QFT) preserve entanglement?

It is well known that entanglement in a quantum state is not affected when you perform a combination of 1-qubit unitary transformations. I have seen that the QFT can be decomposed into product of 1-...
5
votes
3answers
459 views

Why can I not apply a control gate/function to a gate like T, S, S dagger, ... (using IBM Quantum Experience)? Is there another option?

I am trying to use the circuit composer of the IBM QE. I am doing the inverse QFT on 3 qubits and therefore need a control on T and S dagger gates, but it won't let me. Does anyone know why or know a ...
5
votes
2answers
96 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
159 views

Quantum Fourier Transform for general cyclic groups

The QFT on the group $\mathbb{Z}_N$ is given by \begin{equation} QFT\,|k\rangle =\frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} e^{2\pi i\,jk/N}|j\rangle\,. \end{equation} The usual circuit implements the QFT ...
5
votes
1answer
156 views

Question Regarding Quantum Period-Finding Fourier Transform Approximation

I am following the 5.4.1 Period-Finding Algorithm in Nielsen and Chuang as shown below: My confusion lies with the second expression of point 3 in the procedure. Why is the second expression an ...
5
votes
2answers
447 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". ...
4
votes
2answers
283 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
210 views

What is the matrix for a SWAP operation on two qubits?

Say we want to swap qubits $a$, $b$ in the same register, where $a,b \in \left \{ 0, 1,\cdots, n-1 \right \}$. What would be the corresponding matrix. For those interested, I'm curious about this ...
4
votes
1answer
242 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
3answers
376 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 ...
4
votes
1answer
49 views

In Shor's algorithm, how is ${\rm QFT}_n|x\rangle$ split into its even and odd components?

I am auditing a course on quantum computing. Since this is not paid, I dont have any staff support to ask questions. Therefore I am asking the stackoverflow community to help me with it. This is ...
4
votes
1answer
94 views

What is the quantum query complexity of the period finding routine of Shor's algorithm?

It seems like it should be a function of N - O(log N), to minimise probability of getting a multiple of the period. However, Prof Preskill's lec notes mention: Thus we solve Period Finding if the ...
4
votes
1answer
151 views

Shor's algorithm: what to do after reading the QFT's result twice?

I asked about how to identify the period looking at a Fourier transform plot. The answer seems to be to run the fourier transform multiple times getting multiple values associated to high ...
4
votes
1answer
173 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
868 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 ...
4
votes
1answer
133 views

How to write a classical version of Shor's algorithm

For learning purposes, I would like to write a classical version of Shor's algorithm. From what I have read, what makes this algorithm fast is the quantum FFT, which is used to find the period of the ...
4
votes
1answer
67 views

Are there any common applications where one can replace FFT with Quantum Fourier Transform?

I want to apply QFT to some common applications like on wave equations. I haven't found any applications of QFT except Shor's algorithm and I am yet to build an intuition for its use cases. I am a ...
4
votes
2answers
198 views

How to find a circuit for the roots of QFT?

After reading about using quantum gates instead of ancillas, it asserts that every quantum circuit has a square root. Theoretically, they do, but is there a practical method to generate the quantum ...
4
votes
0answers
111 views

Hidden subgroup problem

Let $H$ be a hidden subgroup of $G_1$ that is indistinguishable from subgroup $H^{\prime}$ by quantum Fourier sampling. Now take a larger group $G_2$ such that it contains $G_1$. Now if I do quantum ...
3
votes
3answers
256 views

What is the probability to get all qubits equal zero after QFT

Question from exam: Bob built a quantum computer wiht 10 qubits. All qubits are set to zeroes. Bob performed a quantum Fourier transform on the system and then measured the system. what is the ...
3
votes
2answers
173 views

How does the QFT represent the frequency domain?

QFT is often explained through the classical analogue which converts a certain function from the time domain to the frequency domain. When looking at the discrete Fourier transform, it makes sense to ...
3
votes
1answer
139 views

What is the quantum Fourier transform of $\alpha|0\rangle+\beta|1\rangle$?

Given $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$ and $|\alpha|^2 + |\beta|^2 = 1$, what would the quantum Fourier transform of $|\psi\rangle$ be? I know it is of the form $\frac{1}{\sqrt{2}}(...
3
votes
1answer
189 views

Intuitively, what does the quantum Fourier transform do?

I somewhat understand its practical use in phase estimation and algorithms like Shor's algorithm but is there some more intuitive way of understanding what it does? More concretely, I'd like to know ...
3
votes
1answer
462 views

Why after transpiling a Qiskit circuit we obtain a different result?

I am trying to obtain the correct circuit transpiled for the ibmq_london device, as I want to know what the real gates applied in the quantum computer are. I am implementing the QFT circuit for 5 ...
3
votes
1answer
160 views

What are quantum algorithms with only one possible outcome with probability equal to one?

I would like to study circuits with only one possible outcome. Quantum phase estimation, Bernstein-Vazirani, and in part Deutsch-Jozsa (for constant functions) come to mind - do you know any other ...
3
votes
1answer
127 views

What is the relation between Hadamard transformation and QFT?

I am new to the field and I can't help having a feeling that Hadamard and Fourier Transform are somehow related, but it is not clear to me how. Any explanation on how these two are related would be ...
3
votes
1answer
126 views

Show that Quantum Fourier Transform maps Bell states to Bell states

Given Bell states $\mathcal{B} = \{\left\vert \phi^{\pm} \right\rangle, \left\vert \psi^{\pm} \right\rangle\}$, show that Quantum Fourier Transform(QFT) maps $\mathcal{B}\rightarrow \mathcal{B}$ by ...
3
votes
1answer
209 views

Application of QFT to Order-finding

In the Nielsen & Chuang book, section 5.3.1 page 226, there is a statement which goes like this:- (statement-1) The quantum algorithm for order-finding is just the phase estimation algorithm ...
3
votes
1answer
354 views

Qiskit Inverse of a quantum fourier transformation

In the photo provided the Quantum Fourier Transform is depicted in Qiskit before the barrier. I don't understand the result of inverse. Conceptually, should the inverse of the QFT be the same ...
3
votes
2answers
155 views

How to check if a quantum circuit is deterministic?

I'm trying to find a way to check if a given quantum circuit is essentially a classical one (up to changes in phase). Given a description of a quantum circuit by a list (of size $l$) of ordered ...
3
votes
2answers
90 views

How to implement exponentiation of a gate without breaking complexity?

In the application of QFT for quantum phase estimation (QPE) of a unitary $\mathbf{U}$, one has to perform successive controlled operations using powers of $\mathbf{U}$. In order not to break the ...
3
votes
1answer
90 views

Secret sharing though quantum operations

I have a secret say $s$. I have a dealer $D$ and three participants $A, B, C$. I want to share this secret $s$ in such a way that the participation of all $3$ is essential to reconstruct the secret. ...
3
votes
1answer
102 views

Qiskit's QFT not returning the expected state

I'm currently going through the lab problems for the Qiskit course here. I'm trying to finish lab set number 3 on QPE but I can't seem to get the desired output, even from the solution notebook. I'm ...