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)
62
questions
2
votes
1answer
25 views
How to apply QFT to a quantum state in superposition?
Given the following quantum state:
$\frac{1}{2}(|0000\rangle + |0100\rangle + |1000\rangle + |1100\rangle)$
How do I apply a QFT (given by the formula below) to that state in superposition?
$QFT_n|j\...
3
votes
1answer
65 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 ...
2
votes
1answer
27 views
Prove that QFT and Walsh-Hadamard gates give the same output when acting on $\lvert x\rangle\lvert 0\rangle$ [duplicate]
I know that $QFT_n|0\rangle$ is equivalent to $H_n|0\rangle$
(mathematical proof).
And it is also easy to prove that $QFT_1$ is equivalent to $H_1$ (applied to one QuBit).
From looking at the circuit ...
3
votes
1answer
51 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 ...
2
votes
1answer
50 views
N-Qubit Hadamard vs Quantum Fourier Transform
Both Simon's algorithm and the algorithm for period finding begin by placing qubits in the equal superposition state, but Simon's algorithm uses the n-qubit Hadamard $H^{\otimes n}$ while the period ...
1
vote
1answer
122 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 ...
1
vote
0answers
52 views
QFT on timeseries Data and compare results with classical FFT
Intention - To learn and apply QFT on time-series data and compare the result with classical FFT.
Data Used - Small timeseries data of 16 points -
...
1
vote
2answers
114 views
Is there a quantum operation to change a phase $e^{(0.q_0 q_1 q_2 q_3)}$ into $e^{(0.q_1 q_2 q_3)}$?
Given a set of four qubits, say $q_{0},q_{1},q_{2},q_{3}$ which represent a $4$-bit binary number with $q_{0}$ as the MSB. After applying QFT on these qubits the phase of $q_{0}$using the concept of ...
4
votes
2answers
128 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 ...
2
votes
1answer
40 views
Indexing an “unknown” quantum state
Assuming I have a state
$$|x\rangle = \frac{1}{\sqrt{n}}\sum_n |x_n\rangle$$
where $|x_n\rangle$ are quantum state vectors
$$|x_n\rangle = \frac{1}{\|x_n\|}\sum_i x_{in}|i\rangle$$
and that I have a ...
2
votes
1answer
23 views
Proof of QFT for a Periodic Function
For Mosca Keynes, ex 7.1.5:
You are asked to prove:
$\text{QFT}^{-1}_{mr}|\phi_{r,b}\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-2\pi i \frac{b}{r}k}|mk\rangle$
where
$|\phi_{r,b}\rangle = \...
0
votes
1answer
87 views
How to obtain the density matrix using tomography in the real device?
I am trying to run the QFT algorithm for n=5 (n number of qubits). The number of experiments that it generates is bigger than the one allowed by the IBM devices (i.e. 75). Therefore, I have tried to ...
0
votes
1answer
46 views
QFT of 3-bit system
Recently I was learning about QFT(Quantum Fourier Transform). I was learning how QFT is applied with H and cROT gates. I was playing with QFT here. I was testing with 3-Qubit set as you can see in the ...
3
votes
0answers
68 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 ...
2
votes
2answers
113 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 ...
1
vote
1answer
66 views
How does Inverse QFT work in Quantum Phase Estimation?
I'm trying to implement Quantum Phase Estimation from qiskit textbook.
Below is the implementation circuit taken from the above-mentioned site:
The output at position 2 will be as follows:
$$|\psi ...
2
votes
2answers
122 views
Quantum computers don't try all the possible solutions, so how does the QFT really work?
Scott Aaronson is fond of saying "Quantum computers do not solve hard search problems instantaneously by simply trying all the possible solutions at once." That is, they are not non-deterministic ...
3
votes
2answers
52 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
3answers
208 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 ...
1
vote
2answers
65 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
...
1
vote
1answer
155 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 ...
1
vote
0answers
41 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. ...
5
votes
2answers
146 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-...
7
votes
2answers
360 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 ...
6
votes
2answers
551 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!!
3
votes
1answer
274 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 ...
2
votes
1answer
240 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 (...
1
vote
1answer
39 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 ...
3
votes
1answer
86 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. ...
1
vote
1answer
60 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 ...
1
vote
0answers
91 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$ ...
2
votes
2answers
78 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=...
2
votes
1answer
79 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 . ...
4
votes
0answers
92 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 ...
2
votes
1answer
150 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.
2
votes
1answer
216 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 ...
1
vote
1answer
127 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 ...
6
votes
1answer
56 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 ...
5
votes
2answers
277 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
1answer
288 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.
3
votes
1answer
287 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 ...
4
votes
2answers
217 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 ...
1
vote
1answer
63 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 ...
4
votes
1answer
182 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 ...
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 ...
6
votes
1answer
180 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 ...
1
vote
1answer
80 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 ...
5
votes
1answer
1k 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?
1
vote
1answer
72 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 ...
6
votes
2answers
775 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 ...
