# 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)

43 questions
Filter by
Sorted by
Tagged with
3answers
165 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 ...
2answers
284 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 ...
1answer
30 views

### qiskit: IQFT acting on subsystem of reversed-ordered qubits state

I have a state psi as an ndarray of shape (2 ** 3,) s.t. psi[0]= amplitude of 000 ...
2answers
186 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". ...
1answer
110 views

### Is it possible to demonstrate a quadratic speed-up of a quantum algorithm on a classical computer?

In article Quantum computational finance: Monte Carlo pricing of financial derivatives the authors said that: Firstly: While a practical quantum computer has yet to become a reality, we can ...
0answers
39 views

### What does “decoherence attenuates the density matrix” mean?

I'm reading the paper Implementation of the Quantum Fourier Transform. On page 4, they write To a first approximation, decoherence during the course of the QFT attenuates the entire density matrix. ...
2answers
93 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-...
2answers
222 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 ...
2answers
440 views

### Why QFT can 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!!
1answer
153 views

### Implementing QFT for Shor's Algorithm

I’m trying to get a Quantum Fourier Transform working with the rest of a compiled version of Shor’s algorithm, attempting to factor $N=21$. In the following image, there’s an initialization phase (...
1answer
212 views

### Cannot replicate results in article on pricing financial derivatives on IBM Q

I am trying to implement a circuit for searching for the largest eigenvalue and respective eigenvector of an operator, i.e. phase estimation, introduced in article Towards Pricing Financial ...
2answers
169 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 ...
1answer
32 views

### Can a QFT be implemented as a physical change of the measurement basis?

Suppose you had an "analog" quantum computer, where a register would store a wavefunction $\psi(x)$ where $x$ is a continuous variable (with $0\leq x\leq 1$, say). Instead of gates, you would somehow ...
1answer
83 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. ...
0answers
75 views

### What is the cost of implementing the Quantum Fourier transform in a classical computer?

What is the cost of implementing the Quantum Fourier transform (QFT) in a classical computer? We know we require at least $\log{n}$ depth quantum circuits to do a QFT in a quantum computer, with $n$ ...
1answer
43 views

### Unable to recognise little-endian format

I'm told that the input register is in little-endian format. But the vscode gives me error telling me that it is wrong argument for QFT even after using a suitable converter. Am I missing something ...
1answer
59 views

### The control phase gate in Quantum fourier transform and the question it brings up regarding control gates in general

I have a question that's arose from reading "Quantum computing explained" by David McMahon. On page 212 there's an aspect of his description of the quantum Fourier transform which I don't understand . ...
2answers
67 views

### How do I prove that $\sum_{y=0}^{N-1}e^{2\pi i xy/N}=N\delta_{x,0}$?

I am trying to prove the following relation related to the Quantum Fourier Transform: \sum_{y=0}^{N-1}e^{2\pi i\frac{x}{N}y} = \begin{cases}0 & \text{if } x\neq 0\mod N \\ N & \text{if } x=...
1answer
147 views

### Using Quantum Fourier Transform in adding two 2-bit numbers

I am trying to use Qiskit to write a code that uses QFT to add 2 numbers. I am referring to this paper: https://iopscience.iop.org/article/10.1088/1742-6596/735/1/012083 I have a few questions: 1) Is ...
0answers
82 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 ...
1answer
89 views

### How to decompose the Quantum Fourier Inverse matrix into elementary quantum gates?

I am not sure how to find the following matrix (the inverse of Quantum Fourier Transform) in terms of elementary quantum gates? I am using Qiskit to implement it.
1answer
169 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 ...
1answer
97 views

### What is the intuition of using Hadamard gate in quantum fourier transform?

According to this answer by rrtucci, I still cannot catch the spirit of QFT algorithm. So I would like to ask why are we using the Hadamard gate when computing the Fourier Transform? Moreover, what ...
1answer
51 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 ...
1answer
177 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.
1answer
219 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 ...
1answer
85 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 ...
1answer
60 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 ...
1answer
160 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 ...
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 ...
3answers
2k 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 ...
1answer
128 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 ...
1answer
77 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 ...
1answer
66 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 ...
1answer
734 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?
2answers
603 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 ...
2answers
188 views

2answers
91 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 ...
2answers
473 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. ...
4answers
864 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 ...
2answers
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 ...
1answer
530 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 ...