Skip to main content

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
2 votes
1 answer
27 views

qiskit DraperQFTAdder

my code: ...
Lexiang Xue's user avatar
2 votes
1 answer
58 views

Unitary Transformation for QFT with 2 base states is giving the columns in the wrong order

I'm trying to reproduce in Qiskit the multiplicative form of the QFT for two qubits. It is similar to what is asked in Nielsen's QCQI book in Exercise 5.2 and Box 5.1. To check the results I'm ...
Gustavo Mirapalheta's user avatar
4 votes
1 answer
156 views

Defining the QFT over finite fields

The DFT is well-developed over $\mathbb{C}$ with fast quantum algorithms. There is a DFT defined classically over $F_q$ which mirrors the complex case when we have an $N^{th}$ root of unity in $F_q$, ...
Jackson Walters's user avatar
1 vote
1 answer
75 views

quantum multiplier for large numbers

I am working on a project where I need to calculate 3x+1 for numbers 0 to infinity. I have an 8GB RAM laptop and I am using Cirq. For small numbers, I was able to perform the multiplication using the ...
karen's user avatar
  • 21
1 vote
2 answers
47 views

What exactly is the change in domain for the Quantum Fourier Transform?

The (classical) Fourier Transform is famous for the reversible switch between the time-domain and frequency-domain of time dependent functions. Likewise there would be a change in domain associated ...
Phillip Dukes's user avatar
1 vote
1 answer
70 views

Why does the QFT provide for so many controlled rotations?

I'm new to quantum and I wanted to understand why QFT uses controlled rotation gates. Thank you all
Azure's user avatar
  • 19
3 votes
0 answers
39 views

How to create a quantum algorithm to determine unknown coefficients in a linear function

I am trying to solve the following practice question shown below. I am stuck on part (c) where I must design a quantum algorithm to solve the stated problem. I can tell that the solution is probably ...
Featherball's user avatar
2 votes
1 answer
82 views

Fourier transform of the product of two wave functions

Good day, I have a wave function in the coordinate representation $\Psi(x)$. The Fourier transform I am interested in is: $$ \int e^{-i a x} \Psi(x) \Psi^{\star}(x-b) dx,$$ where $a$, $b$ are some ...
Kim's user avatar
  • 43
13 votes
1 answer
950 views

Does the Quantum Fourier Transform require universality?

Background: In most setups of fault-tolerant quantum computation, universality is achieved using Clifford gates such as $(S, H, \text{CNOT})$ and the $T$-gate. The Eastin-Knill theorem can be ...
Frederik Ravn Klausen's user avatar
3 votes
0 answers
142 views

Failed - Internal Error when running on ibmq

I tried to apply a series of an inverse QFT on a single qubit depending on a previous measurement, but when a depth of a circuit became longer I encountered an internal error, ...
taketoshi kinoshita's user avatar
2 votes
2 answers
77 views

In the QFT, do the basis states $\{|k\pmod N\rangle\}_{k=0}^N$ only make sense when $N=2^n$?

When I started learning quantum computing, I learned that for an $n$ qubit system, the basis states look like $$ \bigg\{ |\text{n-bit strings}\rangle\bigg\}\,.$$ So an $n$ qubit system has $2^n$ basis ...
woah's user avatar
  • 23
3 votes
0 answers
68 views

Why FACTORING is in second level of Fourier hierarchy?

As per comlexityzoo web, the definition of the k-th level of Fourier Hierarchy (FH) is: $FH_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels ...
Manish Kumar's user avatar
3 votes
1 answer
53 views

Unexpected Rotations in QFT Implementation with Qiskit vs. Expected Behavior in Quirk

I'm working on implementing the Quantum Fourier Transform (QFT) using Qiskit. I've encountered an issue where unexpected rotations occur in the presence of a Hadamard circuit, which contrasts with the ...
Alessio Puppi's user avatar
3 votes
1 answer
75 views

Understanding how to solve group isomorphism given the state $\sum_{\pi \in S_n} |\pi(G) \rangle$

Let $G=([n],E)$ be an undirected graph, which is represented by a $n \choose 2$ bit string, by indicating for each $i < j$ if $(i,j) \in E$. And let $| G \rangle$ be the $n \choose 2$ qubit state ...
Gabi G's user avatar
  • 239
2 votes
1 answer
131 views

Is it possible to modify the QFT circuit to use only 1-qubit gates?

[Measured Quantum Fourier Transform] I've recently learned the Quantum Fourier Transform, and was shown its circuit. The circuit I've seen is composed of Hadamard gates and controlled Rotation gates. ...
Gabi G's user avatar
  • 239
2 votes
0 answers
32 views

Quantum Fourier Transform : amplitude encoding of the time series?

I try to understand how to concretely use the Quantum Fourier Transform so as to retrieve the frequency amplitudes $g_{0},\dots, g_{N-1}$ out of the discrete time series $f_{0},\dots, f_{N-1}$ ($f_k\...
deb2014's user avatar
  • 321
6 votes
1 answer
293 views

Is QFT qubit recycling compatible with Zeckendorf's Fibonacci representation of integers?

Background Phase estimation circuits prepare $n$ qubits $Q_0, \dots, Q_{n-1}$ in the $|+\rangle$ state, then apply $U^{2^q}$ controlled by $Q_q$ for each $q$, then apply a quantum Fourier transform, ...
Craig Gidney's user avatar
  • 39.8k
5 votes
2 answers
277 views

Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?

The (classical) lower bound on Fast Fourier transform is still open question. The complexity of $\mathcal{O}(N\log(N))$ (due to Cooley-Tukey) is not known to be optimal. (Here, $N$ is the vector size.)...
Manish Kumar's user avatar
2 votes
1 answer
516 views

How to construct a quantum circuit for quantum Fourier transform in a prime dimensional Hilbert space?

This problem is given as a problem in Nielsen and Chuang. Consider a Hilbert space of dimension $p$ where $p$ is a prime number. Quantum Fourier transform (QFT) in this space is defined as $$ |j\...
Abu Saleh Musa's user avatar
1 vote
1 answer
97 views

Problem with the mathematical definition of the eigenvalue algorithm on a specific exercise

I think I understand well how the eigenvalue algorithm works but when I try to define it mathematically I have problems. Specifically I have the matrix U: $$ U = \begin{pmatrix} 0 & i \\ i & 0 ...
Francescov20's user avatar
3 votes
1 answer
206 views

Estimating $\pi$ using Quantum Computing - why does it work only in simulator?

I followed the steps from the Qiskit tutorial on YouTube titled "How can I estimate Pi using a quantum computer? - 1 Minute Qiskit" The code uses Qiskit and apparently works successfully ...
Rodrigo Hjort's user avatar
4 votes
0 answers
34 views

Fourier sampling in positive characteristic

Fourier sampling is used in the hidden subgroup problem in Shor's algorithm for $\mathbb{Z}/N\mathbb{Z}$ in the abelian case and the symmetric group $S_n$ for attempts at graph isomorphism in the ...
Jackson Walters's user avatar
2 votes
1 answer
236 views

Inverse Quantum Fourier Transformation

I have the exercise to implement the Inverse QFT with Qiskit for any number of qubits without the swapping part. I tried to implement something like this for any $n$. Now I got this code but it doesn'...
Ruebli's user avatar
  • 85
0 votes
3 answers
197 views

Help debugging implementation of Draper QFT adder

I am attempting to implement the adder found in this paper. Here is the code: ...
Jackson Walters's user avatar
3 votes
1 answer
385 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
500 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
80 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
  • 25.9k
13 votes
3 answers
2k 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,861
0 votes
0 answers
38 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
146 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
  • 501
1 vote
1 answer
59 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
  • 173
3 votes
2 answers
222 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
  • 267
1 vote
1 answer
479 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
  • 267
2 votes
0 answers
55 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
45 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
147 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
5 votes
1 answer
2k 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
156 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
  • 409
1 vote
1 answer
78 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
4 votes
1 answer
152 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
69 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
336 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
315 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
287 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
321 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
54 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
5 votes
2 answers
142 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
  • 437
1 vote
0 answers
107 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 ...
CuriousMind's user avatar
3 votes
0 answers
69 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
215 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