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)
159
questions
0
votes
0
answers
9
views
Why are the results of this Fourier adder circuit wrong?
I am attempting to implement the adder found in this paper.
Here is the code:
...
- 205
3
votes
1
answer
83
views
4 qubit QFT decomposition in the qiskit textbook
I am reading about the quantum Fourier transform (QFT) in the qiskit textbook, but got stuck at the last part of it which shows a decomposed version of the 4 qubit QFT circuit.
It seems that the ...
- 31
2
votes
1
answer
61
views
Constructing a controlled phase gate from given gates
As part of a project in a quantum computing course we were asked to classically simulate the quantum phase estimation algorithm, which has inverse QFT as one of its components.
On the Wikipedia page ...
- 21
2
votes
0
answers
57
views
Is the QFT optimal in the quantum phase estimation algorithm?
We can concisely summarise the quantum phase estimation (QPE) algorithm as follows:
Generate the state $\sum_{k=0}^{2^n-1} \lambda^k |k\rangle$ efficiently using a series of controlled-unitary ...
glS♦
- 23k
0
votes
0
answers
16
views
Can I simulate a quantum walk in fourier space?
I would like to simulate a simple quantum walk in Fourier space in Python. I am hoping just to run a 1D quantum walk with a simple Hadamard coin in Fourier space. Is this possible? Do I just need to ...
- 1
10
votes
2
answers
1k
views
Are there any quantum algorithms conjectured to give an exponential speedup for a non-oracle problem that don't use the Quantum Fourier Transform?
The Quantum Fourier Transform (QFT) subroutine seems ubiquitous in most quantum algorithms that are conjectured to give an exponential (or at least superpolynomial) speedup over the best classical ...
- 2,561
0
votes
0
answers
29
views
QFT butterfly structure
Any idea why QFT does not require butterfly structure ?
or probably it is already implied in https://medium.com/a-bit-of-qubit/quantum-fourier-transform-qubits-and-discrete-fourier-transform-...
- 7
2
votes
1
answer
90
views
How to understand Quantum Fourier Transform measurement output?
I have implemented the following 8 qubit QFT circuit similar to the following:
and loaded the coefficients as follows:
The output of the QFT is as follows:
Could anyone help interpret the above ...
- 445
1
vote
1
answer
43
views
Question regarding a step in the computation of $QFT_{16} \frac{1}{2} ( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle )$
In clas we computed the Quantum Fourier Transformation $QFT_{16} \frac{1}{2} ( \mid 1 \rangle + \mid 5 \rangle + \mid 9 \rangle + \mid 13 \rangle )$. We started with the following computation:
\begin{...
- 163
2
votes
2
answers
164
views
In the qiskit QFT demonstration, how to implement CPHASE between Q0 and Q1?
In the qiskit example for QFT demonstration the ibm_q_bogota is used, it has the following layout:
in the same time the measurement circuit for QFT demonstration is:
For such a linear layout how is ...
- 239
0
votes
0
answers
52
views
Inverse quantum Fourier transformation (QFT) on a 4 qubit state
I'm looking to calculate explicitly the inverse QFT acting on a four qubit state. Would the inverse just be calculated as the following:
\begin{equation}\label{QFTProduct}
\frac{1}{\sqrt{N}} \left( |0&...
1
vote
1
answer
185
views
Is QFT really faster FFT?
The standard DFT:
$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2 \pi kn/N} \tag{1}$$
takes approximately $N^2$ complex summations and multiplications (or $\mathcal{O}(N^2)$). The faster version of FT known as FFT ...
- 239
1
vote
0
answers
18
views
Convolution using QFT with 2 vectors
I am doing an experiment in Qiskit - trying to mimic convolution of 2 vectors and getting the result of convolution using element-wise approach.
However, I as doing necessary steps the result I get is ...
- 11
1
vote
1
answer
37
views
Translation by $s \in G$ is diagonal in the Fourier basis
Let $G$ be any finite abelian group and let $P_s$ be the map that sends $|x\rangle \to |x+s\rangle$. In the standard basis $\{|x\rangle : x \in G\}$, the matrix representation is a permutation matrix. ...
- 11
5
votes
2
answers
128
views
Is it true that if $U$ sends computational basis states to product states, then it sends product states to product states?
Let $U$ be a unitary such that for all $n$-qubit computational basis states $|x\rangle$, the state $U |x\rangle$ is a product state. I am trying to prove that for all $n$-qubit product states $|w\...
- 397
0
votes
1
answer
120
views
In Aaronson's Shor's algorithm sealed room analogy, what happens if I wake up only every 48 hours?
I've been reading Aronson's https://scottaaronson.blog/?p=208 blog post about Shor's algorithm. In his sealed room analogy, what happens if I wake up only every 48 hours? Won't this procedure wrongly ...
- 53
3
votes
1
answer
598
views
How to apply QFT to the last two qubits of a Qiskit quantum circuit?
I'm pretty new in Qiskit and quantum circuits. I'm using Qiskit to implement a quantum circuit and I followed this tutorial to implement a QFT. The way this QFT was built, it applies QFT in the first $...
- 189
1
vote
1
answer
69
views
Why is the application of a Quantum Fourier Transform constant time?
I am just curious (complexity theory wise) why the unitary matrix for the QFT (Quantum Fourier Transform) is constant time. From what I know, there is no general way to represent it as a sequence of ...
- 369
1
vote
0
answers
41
views
modify Shor’s quantum order finding algorithm in such a way that it uses as few qubits as possible
I am supposed to modify Shor’s quantum order finding algorithm in such a way that it uses as few qubits as possible.
Beforehand, I already did an exercise where I showed that the inverse Quantum ...
- 23
3
votes
1
answer
89
views
Is the phase-estimation a specific case of the Hidden Subgroup Problem?
I read Nielsen & Chuang and I have difficulties understanding the links between the Hidden Subgroup Problem and the Phase Estimation.
In Exercise 5.14 (Section 5.3.1 "Application: order-...
- 81
0
votes
0
answers
54
views
Period finding for amplitude encoding of function
In quantum Fourier transform, amplitude encoding is used to represent function $f(x)$ such that $|\psi\rangle = \sum_x f(x)|x\rangle$, with $f(x)$ being amplitude. In Shor's algorithm, it is not this ...
- 41
2
votes
1
answer
194
views
Solution to Nielsen & Chuang Exercise 5.3 (FFT)
Can somebody help me with the solution of Nielsen Chuang, where we are supposed to derive the FFT from the equation (5.4):
$$|j_1,\ldots,j_n\rangle\rightarrow\frac{\big(|0\rangle+e^{2\pi i 0.j_n}|1\...
- 21
2
votes
1
answer
215
views
How is the fractional binary notation used in the QFT?
I am studying the Quantum Fourier Transform and my question regards section 4 from this link. Specifically, I do not understand the step where they rewrite in fractional binary notation- could someone ...
4
votes
1
answer
238
views
How does the Hadamard gate work?
I'm learning about the Quantum Fourier Transform (QFT) and from what I can see the Hadamard gate equation doesn't make sense from what I have learnt so far. Here's a link to the resource (Example 2). ...
- 43
3
votes
1
answer
97
views
Is there a way to access the value of a classical bit after measurement and store it as a variable (qiskit)?
I am trying to implement the one-qubit Approximate QFT for Shor's Algorithm in qiskit as described in this paper, which requires the gate
$$
R_j^{\prime}=\left(\begin{array}{c}
1 \hspace{0.5em} 0 \\
0 ...
- 31
1
vote
1
answer
42
views
Alternative Versions of Quantum Fourier Transform (Decimation in Time/Frequency)
Is there a good comparison of alternative versions of the Quantum Fourier Transform (QFT) that mirror the alternative decimation-in-time or decimation in frequency versions for the conventional Fast ...
- 11
4
votes
2
answers
90
views
$QFT^{-1}$ at the end of Shor's algorithm and $QFT$ at the end of Hidden Subgroup algorithm
In the usual presentations (e.g. Nielsen and Chuang) Shor's algorithm (in its quantum part) is presented as a special case of phase estimation, meaning it uses a circuit of the form "generate ...
- 427
1
vote
0
answers
58
views
Convert an integer to its basis state in Cirq
I am trying to implement Quantum Adder using QFT in Cirq. I previously did the same problem using Pennylane, in which I converted an integer into its Basis state using the BasisStatePreparation method ...
2
votes
0
answers
41
views
Simulation of algorithms with QFT on a classical computer
In paper The Quantum Fourier Transform Has Small Entanglement the authors showed that strong entanglement of qubits caused by QFT comes mainly from ordering the qubits. QFT itself prepares only weak ...
- 13.5k
0
votes
1
answer
155
views
Why a Fourier Adder Gives Multiple Faulty Results?
I followed this tutorial and wrote a code that implements the following circuit:
By writing the following code:
...
3
votes
0
answers
36
views
Specific relation between the classical Fourier transform for finite abelian groups and the QFT for finite abelian groups
$\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ket}[1]{|#1\rangle}
\newcommand{\bra}[1]{\langle#1|}$
I am a math undergrad (with admittedly minimal background in quantum ...
0
votes
1
answer
49
views
Clarification about QTF proof regarding equality of QFT application and circuit application
I'm self learning quantum computing through IBM's Qiskit's learning section (which I really like), and I've stumbled across an inequality that I don't quite understand fully.
This must be really easy, ...
1
vote
1
answer
122
views
DFT like operation in the third step of Period finding and Discrete Logarithm algorithm
In the third step of the algorithm for discrete logarithm, the state
$$
|\hat{f}(l_1,l_2)\rangle=\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi il_2j/r}|{f}(0,j)\rangle
$$
is introduced which is stated to ...
- 771
3
votes
1
answer
153
views
How to intuitively interpret the QFT of a state?
According to wikipedia,
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform.
Given the ...
- 245
1
vote
0
answers
78
views
Is Quantum Fourier Transform defined for the standard basis only?
I'm reading the definition on Wikipedia for QFT which is identical to the definition of my professor and they define:
$$|x\rangle = \sum_{i=0}^{N-1} x_i |i\rangle $$
And then the QFT of $|x\rangle$ is:...
- 111
4
votes
1
answer
389
views
Why do we need to reverse the order of qubits in Quantum Fourier Transform? [duplicate]
Looking at Qiskit's QFT tutorial, their implementation of QFT requires you to swap the qubits at the end (Nielsen and Chuang do this too). I'm wondering why this is the case. Can we flip the gates ...
1
vote
0
answers
64
views
Slight issue with QFTing two qubits
Let's consider two qubits and the corresponding computational basis $\{|0\rangle\, |1\rangle, |2\rangle, |3\rangle\}$. In binary form, any of these vectors can also be written as a product $|x_1\...
1
vote
1
answer
110
views
Why can you check for entanglement using the quantum Fourier transform?
I'm reading this paper on quantum random oracles, and I have some fundamental questions about certain statements that seem to be intuitive (but I can't seem to figure it out). My goal is to have a ...
4
votes
1
answer
86
views
Quantum Fourier Transform on $\mathbb{Z}_R^n$
I am reading Regev's proof of existence of quantum algorithm to sample from a discrete Gaussian distribution given a CVP oracle and I am confused about his calculation of the Quantum Fourier transform ...
- 195
2
votes
1
answer
455
views
Prove that applying the QFT twice is equivalent to classical multiplication by $-1$ modulo $2^n$
While going through the answer given on this post, I came across the sentence:
If you apply the $QFT$ twice, it is equivalent to a classical multiplication by -1 modulo $2^n$
where $n$ is the size of ...
- 43
2
votes
1
answer
66
views
Why can we drop bits in front of the decimal in QFT?
In Preskill's notes on quantum information, he includes a section on the quantum Fourier transform (QFT) for period finding. Starting from the classical Fast FT over bitstrings, we can express any ket ...
- 591
4
votes
2
answers
917
views
If two unitary operators commute, do their roots also commute?
This is probably a pretty basic linear algebra question, but suppose we have two unitary operators $A$ and $B$, acting on the same $n$ qubits of $|\psi\rangle$, with $[A,B]=0$ - that is, $A$ and $B$ ...
- 10.2k
0
votes
1
answer
160
views
Different QFT and classical FFT result
I tried to create a PoC that QFT and classical (np.fft) are the same; however, the result confuses me. I use the same input for both QFT and np.fft. I used simulator circuit and directly measured the ...
- 3
1
vote
1
answer
139
views
How do you retrieve the Quantum Fourier Transform matrix from superposition expansion?
So I am trying to wrap my head around QFT working out the details. I have managed to retrieve the 2 qubit QFT matrix by expanding out the superposition of 2 qubits through QFT gate. I am now trying ...
- 33
1
vote
3
answers
141
views
How to show that the QFT satisfies $\frac1{\sqrt N}\sum_j\prod_le^{2\pi i j_l k/2^l}|j_1...j_n⟩=\bigotimes_l \frac1{\sqrt2}(|0⟩+e^{2\pi i k/2^l}|1⟩)$?
I'm reading Ronald de Wolf's lecture notes, and in chapter 4.5 he writes that
$$
\frac{1}{\sqrt N}\sum\limits_{j=0}^{N-1}\prod\limits_{l=1}^{n}e^{2\pi i j_l k / 2^l}|j_1...j_n\rangle =
\bigotimes\...
- 131
4
votes
1
answer
246
views
Difference between semiclassical QFT and QFT
In papers, one of them being An Experimental Study of Shor's Factoring Algorithm on IBM Q is stated that replacing QFT with the semiclassical QFT (Kitaev's approach) reduces the needed number of ...
- 137
6
votes
1
answer
193
views
Does QFT exploit entanglement?
I was studying the quantum circuit for the Quantum Fourier Transform (QFT) on the Mike & Ike, and they write the result of the transformation as a product state.
More precisely they wrote the ...
- 63
3
votes
1
answer
137
views
Hamiltonian of Qiskit QFT is not hermitian
I am trying to generate the Hamiltonian of a quantum Fourier transform by taking the log of the corresponding unitary using qiskit and scipy.
I don't find a hermitian matrix. Why?
...
- 360
0
votes
1
answer
181
views
Equating the state of the Phase Estimation algorithm to $\frac{1}{2^{t/2}}\sum_{k=0}^{2^t-1} e^{2\pi i\phi k}|k\rangle$
It is stated in the Phase Estimation algorithm in Page 222, Quantum Computation and Quantum Information by Nielsen and Chuang that
It seems to say that taking the inverse Quantum Fourier transform of ...
- 771
1
vote
1
answer
141
views
Making sense of the terms Polynomial and Exponential Precision in a Quantum Circuit
The quantum circuit construction of the quantum Fourier transform apparently requires gates of exponential precision in the number of qubits used. However, such precision is never required in any ...
- 771