# 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
Filter by
Sorted by
Tagged with
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
1 vote
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{...
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 ...
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
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 ...
1 vote
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 ...
1 vote
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. ...
128 views

1 vote
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 ...
1 vote
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 ...
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-...
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 ...
194 views

1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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: ...
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\rangle} \newcommand{\bra}{\langle#1|}$ I am a math undergrad (with admittedly minimal background in quantum ...
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
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 ...
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 ...
1 vote
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:...
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
64 views

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 ... 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 ... 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 ... 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$... 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 ... 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 ... 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\... 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 ... 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 ... 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? ... 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 ...
1 vote