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
1
vote
1answer
49 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
1answer
74 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
1answer
35 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 ...
-1
votes
0answers
26 views

HHL algorithm explanation in layman terms [duplicate]

Can someone explain what is happening step by step in HHL algorithm in layman terms without maths starting from the first part (quantum phase estimation), than the second part (rotation gate) and ...
1
vote
1answer
57 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 ...
1
vote
1answer
123 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....
3
votes
1answer
166 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 ...
3
votes
1answer
160 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 ...
1
vote
0answers
120 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 ...
2
votes
1answer
29 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 ...
1
vote
1answer
28 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, ...
1
vote
1answer
108 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 $ \...
2
votes
1answer
63 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)\...
2
votes
0answers
80 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 ...
2
votes
2answers
145 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 ...
1
vote
2answers
100 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, ...
2
votes
1answer
61 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
73 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
136 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
53 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
74 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
112 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
139 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
56 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
80 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
96 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
83 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
82 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
44 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
223 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
91 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
557 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
52 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
483 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
130 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
215 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
303 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
182 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
72 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
99 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
226 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
112 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
163 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
68 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
359 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
431 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
211 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
67 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
146 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
56 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-...