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
1 answer
24 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, ...
user avatar
1 vote
1 answer
62 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 ...
user avatar
  • 313
3 votes
1 answer
51 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 ...
user avatar
  • 245
1 vote
0 answers
31 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:...
user avatar
2 votes
1 answer
48 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 ...
user avatar
1 vote
0 answers
50 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\...
user avatar
1 vote
1 answer
70 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 ...
user avatar
4 votes
1 answer
56 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 ...
user avatar
  • 195
2 votes
1 answer
155 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 ...
user avatar
  • 33
1 vote
1 answer
50 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 ...
user avatar
4 votes
2 answers
776 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$ ...
user avatar
  • 7,042
0 votes
1 answer
75 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 ...
user avatar
  • 3
0 votes
0 answers
25 views

Quantum algorithm for viterbi decoding of classical convolutional code

I was looking into A QUANTUM ALGORITHM FOR VITERBI DECODING OF CLASSICAL CONVOLUTIONAL CODES ref:https://arxiv.org/abs/1405.7479. In this work how the gate complexity is taken as $O(N|Q|F(\log F)^2)$ ...
user avatar
1 vote
0 answers
47 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 ...
user avatar
1 vote
3 answers
112 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\...
user avatar
  • 111
4 votes
1 answer
101 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 ...
user avatar
6 votes
1 answer
178 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 ...
user avatar
  • 63
2 votes
1 answer
87 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? ...
user avatar
  • 326
0 votes
1 answer
105 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 ...
user avatar
  • 313
1 vote
1 answer
56 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 ...
user avatar
  • 313
1 vote
1 answer
78 views

Formulation of quantum phase estimation in Nielsen and Chuang is different then from other sources?

In a chapter of Quantum Computation and Quantum Information by Nielsen and Chuang (10th edition) about quantum phase estimation I get a little confused. Namely: Before applying inverse QFT our quantum ...
user avatar
  • 35
1 vote
1 answer
180 views

Question regarding the notation of QFT

I have a question about the notation of QFT. I would like to present briefly what my problem is. So given is the QFT as a mapping with: $$|j_1,...,j_n\rangle \rightarrow \frac{(|0\rangle + e^{2\pi i 0....
user avatar
  • 628
3 votes
1 answer
181 views

What are quantum algorithms with only one possible outcome with probability equal to one?

I would like to study circuits with only one possible outcome. Quantum phase estimation, Bernstein-Vazirani, and in part Deutsch-Jozsa (for constant functions) come to mind - do you know any other ...
user avatar
  • 151
3 votes
1 answer
343 views

Qiskit's QFT not returning the expected state

I'm currently going through the lab problems for the Qiskit course here. I'm trying to finish lab set number 3 on QPE but I can't seem to get the desired output, even from the solution notebook. I'm ...
user avatar
1 vote
0 answers
141 views

Represent the $n$-qubit $2^n\times2^n$ size Hadamard/quantum Fourier transform unitary square matrix as product of $k$ two-level unitary matrices

I wish to know if it is possible to express the n-qubit Hadamard unitary square matrix of size $2^n * 2^n$ as a product of 'k' two-level unitary square matrices where 'k' is of the order of polynomial ...
user avatar
3 votes
1 answer
47 views

Where is the extra qubit after QFT$^{-1}$ coming from in Shor’s algorithm?

Hello sorry if this is a stupid question arising from my ignorance but I have been looking at the modular adder for Shor's algorithm according to this website. Here is what the gate looks like: The ...
user avatar
  • 65
1 vote
1 answer
36 views

Quantum fourier transform with classical vibrations

Is there any difference in effect between a quantum circuit and a carefully constructed analogue one relying on interference? For example, why couldn't I take a series of $N$ carefully shaped pipes, ...
user avatar
1 vote
1 answer
114 views

Find the conditions under which the state $|\phi\rangle = \sum_{y=0}^{2^n -1} e^{\frac{2 \pi i a y}{2^n}} |y\rangle$ is unentangled

Show that the state $ |\phi\rangle = \sum_{y=0}^{2^n -1} e^{\frac{2 \pi i a y}{2^n}} |y\rangle $ is unentangled if $a \in \{ 0,1,...,2^n - 1\} $ and $|\phi\rangle$ can be expressed in the form $ \...
user avatar
2 votes
1 answer
91 views

Why don't we use exact QFT in Shor's algorithm?

In DLP ($g \equiv x^r$ (mod $p$) with known order of $x$ as $p$), Shor algorithm applies QFT to the state $$\frac{1}{p}\sum_{a, b}^{p-1}|a, b, g^ax^b⟩$$ Here QFT is of size $q$ that satisfies $(p-1)\...
user avatar
2 votes
0 answers
94 views

Two possible ways how to implement Shor's Algorithm

Among many paper describing circuit solving period finding problem and discrete logarithm problem (DLP) (for simplity, let's say $g \equiv x^r$ (mod n) and try to find $r$), there are two variants ...
user avatar
3 votes
2 answers
176 views

Why are these two QFT circuits equivalent?

I am new to quantum computing and have been trying to understand the Quantum Fourier Transform (QFT). Through my research using both the Qiskit textbook and other sources, I see differences in how the ...
user avatar
  • 97
1 vote
2 answers
174 views

How do I find the state of each qubit at the end of the circuit?

I have this Quantum Fourier Transform (QFT) and I want to know how to find the final state of each qubit if q0, q1, ...
user avatar
  • 97
2 votes
1 answer
67 views

Rephase gate in implementaion of QFT of arbitray size

Talking about how exact size of QFT is achieved, both paper 1 and paper 2 skipped the implementation of gate $U$ that can do: $$U|\alpha, \beta⟩ \mapsto exp\left(\frac{i2\pi}{N} \alpha\beta\right)|\...
user avatar
1 vote
0 answers
104 views

Implementation of the Phase Estimation algorithm

I've been working on implementing quantum phase estimation in Qiskit for a $2^n \times 2^n$ Hamiltonian as part of my bachelor project, I'm using Trotterization as my Hamiltonian simulation of choice ...
user avatar
3 votes
1 answer
215 views

What is the relation between Hadamard transformation and QFT?

I am new to the field and I can't help having a feeling that Hadamard and Fourier Transform are somehow related, but it is not clear to me how. Any explanation on how these two are related would be ...
user avatar
4 votes
1 answer
63 views

In Shor's algorithm, how is ${\rm QFT}_n|x\rangle$ split into its even and odd components?

I am auditing a course on quantum computing. Since this is not paid, I dont have any staff support to ask questions. Therefore I am asking the stackoverflow community to help me with it. This is ...
user avatar
1 vote
1 answer
152 views

What are the input and output of QFT and IQFT, respectively?

I have read two opposite explanations about QFT and IQFT from 2 books for beginners of Quantum Computing. Which one is correct? The first book said, if we input an n-qubit non-superposition state into ...
user avatar
4 votes
1 answer
178 views

What is the quantum query complexity of the period finding routine of Shor's algorithm?

It seems like it should be a function of N - O(log N), to minimise probability of getting a multiple of the period. However, Prof Preskill's lec notes mention: Thus we solve Period Finding if the ...
user avatar
  • 73
3 votes
1 answer
152 views

What is the quantum Fourier transform of $\alpha|0\rangle+\beta|1\rangle$?

Given $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$ and $|\alpha|^2 + |\beta|^2 = 1$, what would the quantum Fourier transform of $|\psi\rangle$ be? I know it is of the form $\frac{1}{\sqrt{2}}(...
user avatar
0 votes
1 answer
76 views

Qiskit QFT matrix does not match with DFT matrix

The unitary matrix associated with the QFT circuit in Qiskit does not match the actual DFT matrix. In fact, all the imaginary components have their sign flipped (...
user avatar
  • 715
4 votes
1 answer
85 views

Canonical construction of Logical Fourier Gate

For physical $d$-dimensional qudits we can define $$X= \sum_{i=0}^{d-1} |i+1\rangle \langle i |$$ and $$Z = \sum_{i=0}^{d-1} \omega^i |i\rangle \langle i |,$$ with $\omega=e^{2\pi i/d}$. The Fourier ...
user avatar
  • 2,363
3 votes
1 answer
132 views

In the hidden subgroup problem for finite Abelian groups, where does the state $\frac{1}{\sqrt{|G|}}\sum_{g\in G} |g,0\rangle$ come from?

I am new to the concept of HSP. Previously, I saw how to solve hidden subgroup problem over $\mathbb{Z}_2^n$, which was Simon's algorithm. Over there the first step was to apply $H^{\otimes n}$, which ...
user avatar
1 vote
1 answer
103 views

How to use QFT operation in Q#?

I see the QFT operation in the document given by Microsoft, but I don't know how to call it. ...
user avatar
  • 13
0 votes
1 answer
113 views

Quantum Fourier Transform in the Period Finding Problem

I am trying to prove that when applying the inverse QFT to the following state: we get the following result: However, I get a wrong prefactor. Can anyone tell me where I went wrong? Here my ...
user avatar
  • 11
2 votes
1 answer
50 views

Calculating the QFFT according to Coppersmith

I have come through an interesting paper by Don Coppersmith (https://arxiv.org/pdf/quant-ph/0201067.pdf), and I was wondering what was your view on the $Q_{JK}$ ("twiddle") transformation, ...
user avatar
2 votes
3 answers
265 views

Intuition behind the use of inverse FFT in Quantum Circuit for Hamming weight

I have found this question from MIT problemset. I could only design the circuit for 3 qubits. But they have a general solution that shows this circuit. I am trying to understand this circuit (from ...
user avatar
  • 905
3 votes
1 answer
104 views

Efficient QFT-based QPEA complexity

The HHL algorithm lies on an implementation of the Quantum Phase Estimation algorithm. One popular implementation is based on the Quantum Fourier Transform which can be divided in three steps. Let $U$ ...
user avatar
  • 185
6 votes
2 answers
936 views

How to generalize the relationship HXH = Z for higher dimensions

Concerning the Hadamard gate and the Pauli $X$ and $Z$ gates for qubits, it is straightforward to show the following relationship via direct substitution: $$ HXH = Z.\tag{1}$$ And I would like to ...
user avatar
  • 95
2 votes
1 answer
62 views

Lieb-Robinson Bound in 2nd quantized description?

Background Let us restrict our discussion to bosons and adopt the convention First Quantised $\leftrightarrow $ Second Quantised Theory (we are following these Ashok Sen's Quantum Field Theory I of ...
user avatar
6 votes
3 answers
595 views

Why can I not apply a control gate/function to a gate like T, S, S dagger, ... (using IBM Quantum Experience)? Is there another option?

I am trying to use the circuit composer of the IBM QE. I am doing the inverse QFT on 3 qubits and therefore need a control on T and S dagger gates, but it won't let me. Does anyone know why or know a ...
user avatar
  • 121