19 votes

Why does the "Phase Kickback" mechanism work in the Quantum phase estimation algorithm?

A first remark This same phenomenon of 'control' qubits changing states in some circumstances also occurs with controlled-NOT gates; in fact, this is the entire basis of eigenvalue estimation. So not ...
user avatar
15 votes
Accepted

Why does the "Phase Kickback" mechanism work in the Quantum phase estimation algorithm?

Imagine you have an eigenvector $|u\rangle$ of $U$. If you have a state such as $|1\rangle|u\rangle$ and you apply controlled-$U$ to it, you get out $e^{i\phi}|1\rangle|u\rangle$. The phase isn't ...
user avatar
  • 47.5k
13 votes

Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?

Introduction to the Classical Discrete Fourier transform: The DFT transforms a sequence of $N$ complex numbers $\{\mathbf{x}_n\}:=x_0,x_1,x_2,...,x_{N-1}$ into another sequence of complex numbers $\{\...
user avatar
12 votes
Accepted

Why can the QFT be replaced by Hadamard gates?

While the QFT and Hadamard transforms are different, their action on the input state $|00\ldots 0\rangle$ is identical; both produce the uniform superposition of all states. So, if you've got a choice ...
user avatar
  • 47.5k
10 votes

Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?

One possible answer as to why we can realise the QFT efficiently is down to the structure of its coefficients. To be precise, we can represent it easily as a quadratic form expansion, which is a sum ...
user avatar
9 votes
Accepted

Implementation of inverse QFT?

Yes. You have been given a factorization $QFT=U_1 \cdots U_n$ where each $U_i$ is an individual gate. $$ QFT^{-1} = U_n^{-1} \cdots U_1^{-1}\\ = U_n^{\dagger} \cdots U_1^{\dagger}\\ $$ A lot of the ...
user avatar
  • 3,553
9 votes

Why should we use inverse QFT instead of QFT in Shor's algorithm?

For Shor's algorithm, it actually doesn't matter which one you use. If you apply the QFT twice, it is equivalent to a classical multiplication by -1 modulo $2^n$ where $n$ is the size of the register....
user avatar
  • 23.3k
9 votes
Accepted

If two unitary operators commute, do their roots also commute?

If $A$ and $B$ are any two diagonalizable matrices that commute, then for any matrix function $f$ (anything in the continuous functional calculus, such as square root), $f(A)$ and $f(B)$ will also ...
user avatar
  • 1,691
9 votes

If two unitary operators commute, do their roots also commute?

It's always possible to find some square roots that commute. But it's not guaranteed that all square roots commute. If two operations commute, then you can find square roots that commute by ...
user avatar
  • 23.3k
8 votes

Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?

This is deviating a little from the original question, but I hope gives a little more insight that could be relevant to other problems. One might ask "What is it about order finding that lends itself ...
user avatar
  • 47.5k
8 votes

Do the probability amplitudes of the superposition state produced by the QFT transform convey useful information?

You probably shouldn't be thinking of the Quantum Fourier Transform as being something where you want to extract the outcoming probability amplitudes. As you say, when you start measuring, you destroy ...
user avatar
  • 47.5k
7 votes
Accepted

Simplified explanation of Shor/QFT transformation as thumbtack

Let me attempt to give a rather unconventional answer to this question: ...
user avatar
7 votes
Accepted

How does Fourier sampling actually work (and solve the parity problem)?

Starting from the beginning (a very good place to start, after all), the state $\left| 0\right\rangle^{\otimes n}\left| -\right\rangle$ is input into $H^{\otimes n}\otimes I$ (here, called the '...
user avatar
  • 3,477
7 votes
Accepted

Why is quantum Fourier transform required in Shor's algorithm?

The essential feature of this problem is that while both the quantum and classical algorithms can make use of the efficient classical function of calculating $a^k\text{ mod }N$, the issue is how many ...
user avatar
  • 47.5k
7 votes
Accepted

Does the quantum Fourier transform have many applications beyond period finding?

Given that the QFT is exponentially faster than the FFT, The problem with quantum computing is that they are not actually parallel computers: One is tweaking the qubits in such a way that when ...
user avatar
7 votes

Does the Quantum Fourier Transform (QFT) preserve entanglement?

I expect you're referring to this image: Where it says that $R_m$ is given by a particular 2x2 matrix. In this notation, $R_m$ is a 1-qubit unitary, but the circuit is applying a different gate, what ...
user avatar
6 votes
Accepted

Why do we use the quantum superposition for a period instead of factors in Shor's algorithm?

A QFT can't arbitrarily raise the probability of any state you want to any value you want. Once you create a superposition, you need to find some way to make destructive interference occur between the ...
user avatar
  • 1,691
6 votes
Accepted

What happens with first phase factor in QFT?

If you have a quantum state like $$|\Psi\rangle_n = a_0|0\rangle_n+a_1|1\rangle_n+...+a_n|2^n-1\rangle_n$$ and you measure it in the $\{|0\rangle_n,...,|2^{n-1}\rangle_n\}$ basis, then the probability ...
user avatar
6 votes
Accepted

How to describe, or encode, the input vector x of Quantum Fourier Transform?

Formula 5.2 refers to an encoding we call amplitude encoding. Imagine you have a vector $x$ with components $x_i$, the components are then encoded as amplitudes of a quantum state. This encoding is ...
user avatar
  • 4,574
6 votes
Accepted

What is the matrix for a SWAP operation on two qubits?

In the general case I think it's easier to consider the matrix in the form $$ M = \sum_{i_1,\dots,i_n, j_1, \dots j_n} c_{i_1,\dots,j_n} |i_1 \dots i_n\rangle \langle j_1 \dots j_n|, $$ where the $i_1,...
user avatar
  • 4,202
5 votes

How to describe, or encode, the input vector x of Quantum Fourier Transform?

You don't convert a classical input to the r.h.s. of Eq. (5.2). The r.h.s. of Eq. (5.2) is something you get as the output of a preceding quantum computation as a quantum state, such as in Shor's ...
user avatar
5 votes
Accepted

What is the intuition of using Hadamard gate in quantum fourier transform?

The intuition, roughly speaking, is that the only way that you're going to get some difference between classical and quantum computing is if you are able to prepare qubits in a superposition. If you ...
user avatar
  • 47.5k
5 votes
Accepted

Does the Quantum Fourier Transform (QFT) preserve entanglement?

TLDR: the Fourier transform is entangling. We can immediately agree on two things: if you input a computational basis state (separable) to the Fourier transform, it outputs a separable state the ...
user avatar
  • 47.5k
5 votes

What is the probability to get all qubits equal zero after QFT

By looking to the circuit for the QFT presented in the M. Nielsen and I. Chuang textbook (Figure 5.1.) we can notice that all controlled rotations can be neglected because for each control rotation ...
user avatar
5 votes

Application of QFT to Order-finding

Answer to question 1 There are many ways the first quantum algorithm for order finding could have been conceived and I don't know how it really happened. However, here is a plausible though entirely ...
user avatar
  • 14.4k
5 votes
Accepted

How to generalize the relationship HXH = Z for higher dimensions

The appropriate $d$-dimensional analogue of $H$ turns out to be the Quantum Fourier Transform. This is obscured by the fact that even though $(1)$ is conjugation the inverse is written implicitly ...
user avatar
  • 14.4k
5 votes
Accepted

Does QFT exploit entanglement?

Yes, the formula you have shows that applying QFT to a given computational basis state $|j\rangle = |j_1 j_2 \dots j_n\rangle$ results in an unentangled output state. However when applied to ...
user avatar
  • 4,942
4 votes

Implementing QFT for Shor's Algorithm

The comment made by arriopolis is correct. The output registers of these compiled circuits are important for synthesizing the circuit, but not particularly interesting to measure. As you saw already,...
user avatar
4 votes

Quantum computers don't try all the possible solutions, so how does the QFT really work?

In many quantum algorithms, the first step is to compute some problem on all instances at the same time -- if you wish, you compute all solutions at once. But then you are left with a state such as $$...
user avatar
4 votes

Why after transpiling a Qiskit circuit we obtain a different result?

I have found the solution! The problem is that each time you use the transpile function, it generates a different transpiled circuit and the order of the outcome is not necessary the same as the order ...
user avatar
  • 369

Only top scored, non community-wiki answers of a minimum length are eligible