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
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: ...
Jackson Walters's user avatar
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 ...
pilsungk's user avatar
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 ...
Ziv's user avatar
  • 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's user avatar
  • 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 ...
Saz's user avatar
  • 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 ...
tparker's user avatar
  • 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-...
kevin's user avatar
  • 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 ...
James's user avatar
  • 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{...
3nondatur's user avatar
  • 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 ...
Curious's user avatar
  • 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&...
Aaron Lowry 's user avatar
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 ...
Curious's user avatar
  • 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 ...
MeatBallKing's user avatar
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. ...
user25129's user avatar
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\...
trillianhaze's user avatar
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 ...
bburd's user avatar
  • 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 $...
Herr Schrödinger's user avatar
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 ...
wavosa's user avatar
  • 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 ...
moert4's user avatar
  • 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-...
user8622655's user avatar
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 ...
Felipe's user avatar
  • 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\...
Gregor123's user avatar
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 ...
random person's user avatar
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). ...
WhiteWolfDev's user avatar
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 ...
inception's user avatar
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 ...
user22838's user avatar
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 ...
Gadi A's user avatar
  • 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 ...
Jessica John Britto's user avatar
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 ...
Martin Vesely's user avatar
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: ...
Himanshu Bansal's user avatar
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 ...
Kenanski Bowspleefi's user avatar
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, ...
user3804691's user avatar
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 ...
Sooraj S's user avatar
  • 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 ...
gen's user avatar
  • 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:...
Doron Behar's user avatar
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 ...
Freeman Cheng's user avatar
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\...
Creeptographer's user avatar
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 ...
FlamtapShuckle's user avatar
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 ...
schayes's user avatar
  • 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 ...
Srijan's user avatar
  • 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 ...
Cuhrazatee's user avatar
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$ ...
Mark Spinelli's user avatar
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 ...
Bankde's user avatar
  • 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 ...
Michael Hong's user avatar
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\...
dnnagy's user avatar
  • 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 ...
Vladnerovski's user avatar
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 ...
wasalbi's user avatar
  • 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? ...
Nichola's user avatar
  • 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 ...
Sooraj S's user avatar
  • 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 ...
Sooraj S's user avatar
  • 771