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)
97
questions
0
votes
1answer
25 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)|\...
1
vote
0answers
44 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 ...
3
votes
1answer
106 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 ...
4
votes
1answer
44 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 ...
1
vote
1answer
47 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 ...
4
votes
1answer
70 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 ...
3
votes
1answer
134 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}}(...
0
votes
1answer
45 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 (...
3
votes
1answer
75 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 ...
3
votes
1answer
78 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 ...
1
vote
1answer
61 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.
...
0
votes
1answer
54 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 ...
2
votes
1answer
42 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
210 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
84 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$ ...
6
votes
2answers
414 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 ...
2
votes
1answer
44 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
430 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
121 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
193 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 ...
1
vote
1answer
161 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
141 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
70 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
75 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
172 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
63 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 ...
4
votes
1answer
143 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
61 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
2answers
308 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
258 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 ...
5
votes
1answer
98 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
61 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
117 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
48 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
116 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
44 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
166 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
51 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 ...
4
votes
1answer
64 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
115 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 ...
3
votes
1answer
397 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
66 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
171 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
46 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
52 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
154 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
86 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
149 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
143 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 ...
