24
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 ...
- 11.7k
17
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 ...
- 54.4k
14
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 $\{\...
- 17.1k
14
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 ...
- 54.4k
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 ...
- 11.7k
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 ...
- 3,603
9
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 ...
- 54.4k
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....
- 32.4k
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 ...
- 1,974
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 ...
- 32.4k
9
votes
Accepted
Is it true that if $U$ sends computational basis states to product states, then it sends product states to product states?
TL;DR: The claim is false, i.e. it is not true that if $U|x\rangle$ is a product state for all computational basis states $|x\rangle$, then $U$ sends product states to product states. Counterexamples ...
- 20k
9
votes
Accepted
Are there any quantum algorithms conjectured to give an exponential speedup for a non-oracle problem that don't use the Quantum Fourier Transform?
Aharonov–Jones–Landau algorithm is a polynomial time quantum algorithm that approximates the #P-hard problem of evaluating the Jones polynomial at certain roots of unity. The best classical algorithm ...
- 8,454
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 ...
- 54.4k
7
votes
Accepted
Simplified explanation of Shor/QFT transformation as thumbtack
Let me attempt to give a rather unconventional answer to this question:
...
- 591
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 '...
- 3,647
7
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 ...
- 17.1k
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 ...
- 54.4k
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 ...
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 ...
- 311
7
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,...
- 5,201
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 ...
- 1,974
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 ...
- 4,644
6
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 ...
- 54.4k
6
votes
Accepted
Intuitively, what does the quantum Fourier transform do?
Let's see what QFT does on two qubit (and then on three qubit) computational basis states and try to gain some insights. The QFT action on $|j\rangle$ basis state:
$$QFT |j\rangle = \frac{1}{2^{\frac{...
- 4,221
6
votes
Accepted
How is the fractional binary notation used in the QFT?
A positive integer $y$ has a binary representation $y_{n-1}\ldots y_{0}$ where $y_k \in \{0,1\}$. For example, for $n=3$, the number $5$ in binary is $\color{red}{101}$. If we do a binary expansion of ...
- 2,339
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 ...
- 5,598
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 ...
- 54.4k
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 ...
- 4,221
5
votes
Accepted
Qiskit Inverse of a quantum fourier transformation
From linear algebra we know that $(AB)^{-1} = B^{-1} A^{-1}$. This is because $(AB)*(AB)^{-1} = ABB^{-1}A^{-1} = AIA^{-1} = I$.
Hence, if you have the circuit to generate the Bell state from the state ...
- 13.6k
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 ...
- 20k
Only top scored, non community-wiki answers of a minimum length are eligible