# Tag Info

### 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 ...
• 12.2k
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 ...
• 59.9k
Accepted

### Does the Quantum Fourier Transform require universality?

Yes, the QFT requires universality. No, there isn't a non-universal gate set that implements the QFT. Just having the QFT as an operation is already computationally universal, because it can generate ...
• 39.7k

• 5,978
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,814
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,764
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 ...
• 59.9k
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 ...
• 59.9k
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,381

### $QFT^{-1}$ at the end of Shor's algorithm and $QFT$ at the end of Hidden Subgroup algorithm

$\text{QFT}\big(|0\rangle^{\otimes n}\big) = \text{QFT}^{-1}\big(|0\rangle^{\otimes n}\big) = |{+}\rangle^{\otimes n}$, so a QFT, inverse QFT, or a column of Hadamard gates are all equivalent at the ...
• 888
Accepted

### $QFT^{-1}$ at the end of Shor's algorithm and $QFT$ at the end of Hidden Subgroup algorithm

Note that $\text{QFT}^2$ is a permutation $|k\rangle \rightarrow |(-k) \bmod 2^n\rangle$. This is a classical operation. It can be applied in the post processing of the measurements, and in fact it ...
• 39.7k