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)
84
questions
2
votes
1answer
38 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, ...
2
votes
3answers
184 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 ...
3
votes
1answer
66 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$ ...
2
votes
1answer
39 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 ...
5
votes
3answers
391 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 ...
3
votes
1answer
96 views
Show that Quantum Fourier Transform maps Bell states to Bell states
Given Bell states $\mathcal{B} = \{\left\vert \phi^{\pm} \right\rangle, \left\vert \psi^{\pm} \right\rangle\}$, show that Quantum Fourier Transform(QFT) maps $\mathcal{B}\rightarrow \mathcal{B}$ by ...
3
votes
1answer
145 views
Application of QFT to Order-finding
In the Nielsen & Chuang book, section 5.3.1 page 226, there is a statement which goes like this:- (statement-1)
The quantum algorithm for order-finding is just the phase estimation
algorithm ...
0
votes
1answer
75 views
Qubit ordering in qiskit
I am confused about the qubit ordering in circuit diagrams and endianness used in qiskit. As far as I understand, qiskit uses little endian (least significant qubit is rightmost) and while drawing ...
3
votes
2answers
122 views
How does the QFT represent the frequency domain?
QFT is often explained through the classical analogue which converts a certain function from the time domain to the frequency domain. When looking at the discrete Fourier transform, it makes sense to ...
2
votes
1answer
65 views
A simple question about QFT and CNOT
Given two $d$-dimensional states $QFT|i\rangle(i\in\{0,1,2,...,d-1\})$ and $|\varphi\rangle=|0\rangle$. If I perform $CNOT(QFT|i\rangle,|\varphi\rangle)$, and then perform $QFT^{-1}|\varphi\rangle$, ...
1
vote
1answer
55 views
Trying to perform Quantum Phase Estimation on T-gate
I'm trying to perform QPE on the T-gate in Quirk but I'm not getting the correct result. For the T-gate, I should be measuring (001) with 100% probability, but instead, I'm getting the following:
I'...
4
votes
1answer
124 views
What is the matrix for a SWAP operation on two qubits?
Say we want to swap qubits $a$, $b$ in the same register, where $a,b \in \left \{ 0, 1,\cdots, n-1 \right \}$. What would be the corresponding matrix.
For those interested, I'm curious about this ...
3
votes
1answer
47 views
Measuring in the computational basis in the single qubit gate QFT implementation
I've come across this paper about a single-qubit-gate-only QFT implementation. In the paper it is claimed that measuring a qubit after applying the Hadamard gate (it isn't called Hadamard gate in the ...
3
votes
1answer
123 views
Shor's algorithm: what to do after reading the QFT's result twice?
I asked about how to identify the period looking at a Fourier transform plot. The answer seems to be to run the fourier transform multiple times getting multiple values associated to high ...
0
votes
1answer
46 views
What is this equation for coin operator is trying to do in this quantum walk for Non-regular graph? This coin operator is called Fourier coin
I am reading the following paper: Discrete-time quantum walk on complex networks
for community detection by Kanae Mukai
We define the Coin operator $C$ by: $C=C_1\otimes C_2....C_n$ , We define coin ...
7
votes
3answers
259 views
Shor's algorithm: initialization of second register
I am trying to understand Shor's algorithm. I am not quite sure why the initialization, indicated as $|1\rangle$ in the below image at the bottom left is chosen as it is? I understand the modular ...
3
votes
1answer
138 views
Qiskit Inverse of a quantum fourier transformation
In the photo provided the Quantum Fourier Transform is depicted in Qiskit before the barrier. I don't understand the result of inverse. Conceptually, should the inverse of the QFT be the same ...
4
votes
1answer
71 views
Quantum Fourier Transform for general cyclic groups
The QFT on the group $\mathbb{Z}_N$ is given by
\begin{equation}
QFT\,|k\rangle =\frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} e^{2\pi i\,jk/N}|j\rangle\,.
\end{equation}
The usual circuit implements the QFT ...
3
votes
0answers
56 views
Abelian Hidden Subgroup Problem for arbitrary cyclic p-Groups
I had asked a question similar to this one here regarding how to handle the HSP for groups whose cyclic decomposition contains factors whose order is not a power of two. I also had some prior ...
4
votes
1answer
104 views
How to write a classical version of Shor's algorithm
For learning purposes, I would like to write a classical version of Shor's algorithm. From what I have read, what makes this algorithm fast is the quantum FFT, which is used to find the period of the ...
0
votes
1answer
43 views
Quantum circuit, Fourier Transform/Decomposition?
Broadly speaking, can we say that quantum circuits are like Fourier Transform/Decomposition? We use qbit like waves, tune it with quantum gates, to find answer. https://ars.els-cdn.com/content/image/3-...
2
votes
1answer
112 views
Constructing arbitrary functions for the Abelian HSP
My question might be similar to Hidden subgroup problem. However, I'm not exactly sure though. In addition, that question doesn't have an answer.
I'm trying to create some simple instances of the ...
2
votes
1answer
36 views
How to apply QFT to a quantum state in superposition?
Given the following quantum state:
$\frac{1}{2}(|0000\rangle + |0100\rangle + |1000\rangle + |1100\rangle)$
How do I apply a QFT (given by the formula below) to that state in superposition?
$QFT_n|j\...
3
votes
1answer
133 views
Intuitively, what does the quantum Fourier transform do?
I somewhat understand its practical use in phase estimation and algorithms like Shor's algorithm but is there some more intuitive way of understanding what it does?
More concretely, I'd like to know ...
2
votes
1answer
42 views
Prove that QFT and Walsh-Hadamard gates give the same output when acting on $\lvert x\rangle\lvert 0\rangle$ [duplicate]
I know that $QFT_n|0\rangle$ is equivalent to $H_n|0\rangle$
(mathematical proof).
And it is also easy to prove that $QFT_1$ is equivalent to $H_1$ (applied to one QuBit).
From looking at the circuit ...
3
votes
1answer
59 views
Are there any common applications where one can replace FFT with Quantum Fourier Transform?
I want to apply QFT to some common applications like on wave equations. I haven't found any applications of QFT except Shor's algorithm and I am yet to build an intuition for its use cases. I am a ...
2
votes
1answer
90 views
N-Qubit Hadamard vs Quantum Fourier Transform
Both Simon's algorithm and the algorithm for period finding begin by placing qubits in the equal superposition state, but Simon's algorithm uses the n-qubit Hadamard $H^{\otimes n}$ while the period ...
2
votes
1answer
272 views
Why after transpiling a Qiskit circuit we obtain a different result?
I am trying to obtain the correct circuit transpiled for the ibmq_london device, as I want to know what the real gates applied in the quantum computer are. I am implementing the QFT circuit for 5 ...
2
votes
0answers
62 views
QFT on timeseries Data and compare results with classical FFT
Intention - To learn and apply QFT on time-series data and compare the result with classical FFT.
Data Used - Small timeseries data of 16 points -
...
1
vote
2answers
123 views
Is there a quantum operation to change a phase $e^{(0.q_0 q_1 q_2 q_3)}$ into $e^{(0.q_1 q_2 q_3)}$?
Given a set of four qubits, say $q_{0},q_{1},q_{2},q_{3}$ which represent a $4$-bit binary number with $q_{0}$ as the MSB. After applying QFT on these qubits the phase of $q_{0}$using the concept of ...
4
votes
2answers
152 views
How to find a circuit for the roots of QFT?
After reading about using quantum gates instead of ancillas, it asserts that every quantum circuit has a square root. Theoretically, they do, but is there a practical method to generate the quantum ...
2
votes
1answer
44 views
Indexing an “unknown” quantum state
Assuming I have a state
$$|x\rangle = \frac{1}{\sqrt{n}}\sum_n |x_n\rangle$$
where $|x_n\rangle$ are quantum state vectors
$$|x_n\rangle = \frac{1}{\|x_n\|}\sum_i x_{in}|i\rangle$$
and that I have a ...
2
votes
1answer
35 views
Proof of QFT for a Periodic Function
For Mosca Keynes, ex 7.1.5:
You are asked to prove:
$\text{QFT}^{-1}_{mr}|\phi_{r,b}\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-2\pi i \frac{b}{r}k}|mk\rangle$
where
$|\phi_{r,b}\rangle = \...
0
votes
1answer
122 views
How to obtain the density matrix using tomography in the real device?
I am trying to run the QFT algorithm for n=5 (n number of qubits). The number of experiments that it generates is bigger than the one allowed by the IBM devices (i.e. 75). Therefore, I have tried to ...
1
vote
1answer
65 views
QFT of 3-bit system
Recently I was learning about QFT(Quantum Fourier Transform). I was learning how QFT is applied with H and cROT gates. I was playing with QFT here. I was testing with 3-Qubit set as you can see in the ...
5
votes
1answer
138 views
Question Regarding Quantum Period-Finding Fourier Transform Approximation
I am following the 5.4.1 Period-Finding Algorithm in Nielsen and Chuang as shown below:
My confusion lies with the second expression of point 3 in the procedure. Why is the second expression an ...
3
votes
2answers
133 views
How to check if a quantum circuit is deterministic?
I'm trying to find a way to check if a given quantum circuit is essentially a classical one (up to changes in phase).
Given a description of a quantum circuit by a list (of size $l$) of ordered ...
1
vote
1answer
97 views
How does Inverse QFT work in Quantum Phase Estimation?
I'm trying to implement Quantum Phase Estimation from qiskit textbook.
Below is the implementation circuit taken from the above-mentioned site:
The output at position 2 will be as follows:
$$|\psi ...
2
votes
2answers
140 views
Quantum computers don't try all the possible solutions, so how does the QFT really work?
Scott Aaronson is fond of saying "Quantum computers do not solve hard search problems instantaneously by simply trying all the possible solutions at once." That is, they are not non-deterministic ...
3
votes
2answers
70 views
How to implement exponentiation of a gate without breaking complexity?
In the application of QFT for quantum phase estimation (QPE) of a unitary $\mathbf{U}$, one has to perform successive controlled operations using powers of $\mathbf{U}$. In order not to break the ...
3
votes
3answers
241 views
What is the probability to get all qubits equal zero after QFT
Question from exam:
Bob built a quantum computer wiht 10 qubits. All qubits are set to zeroes. Bob performed a quantum Fourier transform on the system and then measured the system.
what is the ...
1
vote
2answers
95 views
qiskit: IQFT acting on subsystem of reversed-ordered qubits state
I have a state psi as an ndarray of shape (2 ** 3,) s.t.
psi[0]= amplitude of 000
...
1
vote
1answer
201 views
Is it possible to demonstrate a quadratic speed-up of a quantum algorithm on a classical computer?
In article Quantum computational finance: Monte Carlo pricing of financial derivatives the authors said that:
Firstly:
While a practical quantum computer has yet to become
a reality, we can ...
3
votes
0answers
53 views
What does “decoherence attenuates the density matrix” mean?
I'm reading the paper Implementation of the Quantum Fourier Transform. On page 4, they write
To a first approximation, decoherence during the course of the QFT attenuates the entire density matrix. ...
5
votes
2answers
209 views
Does the Quantum Fourier Transform (QFT) preserve entanglement?
It is well known that entanglement in a quantum state is not affected when you perform a combination of 1-qubit unitary transformations.
I have seen that the QFT can be decomposed into product of 1-...
9
votes
3answers
556 views
Does the quantum Fourier transform have many applications beyond period finding?
(This is a somewhat soft question.)
The quantum Fourier transform is formally quite similar to the fast Fourier transform, but exponentially faster.
The QFT is famously at the core of Shor's ...
6
votes
2answers
615 views
Why can the QFT be replaced by Hadamard gates?
I'm studying Shor's Algorithm.
In the book, author explains QFT can be replaced by Hadamard gates?
Why this process is possible??
Thank you everybody. This is QPE. I attach part of book!!
3
votes
1answer
312 views
Cannot replicate results in article on pricing financial derivatives on IBM Q
I am trying to implement a circuit for searching for the largest eigenvalue and respective eigenvector of an operator, i.e. phase estimation, introduced in article Towards Pricing Financial ...
2
votes
1answer
319 views
Implementing QFT for Shor's Algorithm
Iām trying to get a Quantum Fourier Transform working with the rest of a compiled version of Shorās algorithm, attempting to factor $N=21$.
In the following image, thereās an initialization phase (...
1
vote
1answer
44 views
Can a QFT be implemented as a physical change of the measurement basis?
Suppose you had an "analog" quantum computer, where a register would store a wavefunction $\psi(x)$ where $x$ is a continuous variable (with $0\leq x\leq 1$, say). Instead of gates, you would somehow ...
