In QPE, we first accumulate the phase in control bits and then apply inverse QFT to them to get the actual phase. So it means that QPE must be converting the phase into its Fourier basis states in the first half. That's why applying inverse QFT in the second half yields the corresponding phase value. Is this correct? If yes, why does QPE 'naturally' convert the phase into its Fourier basis states in the first half? Why is that process analogous to QFT?
Why does Quantum Phase Estimation first 'naturally' convert the phase into its Fourier basis states?
- $\begingroup$ If I'm interpreting the question correctly, I'd say the quick answer is that QPE generates a state of the form $\sum_k \lambda^k |k\rangle$ with $\lambda$ the eigenvalue corresponding to the "oracle" unitary used in the QPE (eigenvalue corresponding to whatever eigenstate it's been used in the second register). And writing $\lambda=e^{2\pi i\phi}$, you can see that such a superposition has precisely the form of some $\operatorname{QFT}_N|j\rangle$, provided that $\phi=j/N$ for some $j\in\mathbb{Z}$ $\endgroup$glS– glS ♦2025-01-14 08:24:14 +00:00Commented Jan 14 at 8:24
1 Answer
When you apply QFT on an state $|x \rangle$ the output can be shown as a tensor product form :
$$\text{QFT}(|x\rangle) = \frac{1}{\sqrt{N}}\bigotimes_{k=1}^n\bigg(|0\rangle+e^{\frac{2\pi ix}{2^k}}|1\rangle\bigg)\,, \tag{1}$$ where $$N=2^n\,.$$
Let $x$ be a binary string $x_1x_2..x_{n-1}x_n$, then (1) can be written as : $ \begin{align} \text{QFT}(|x_1x_2..x_{n-1}x_n\rangle) = \frac{1}{\sqrt{N}}&\bigg(|0\rangle + e^{\frac{2 \pi i x_1x_2..x_{n-1}x_n}{2^1}}|1\rangle\bigg)\\ &\otimes\bigg(|0\rangle + e^{\frac{2 \pi i x_1x_2..x_{n-1}x_n}{2^2}}|1\rangle\bigg)\\&\otimes\cdots\otimes\bigg(|0\rangle + e^{\frac{2 \pi i x_1x_2..x_{n-1}x_n}{2^n}}|1\rangle\bigg)\,. \tag{2} \end{align}$ Integer part of $\frac{2\pi i x}{2^k}$ in $e^{\frac{2\pi i x}{2^k}}$ can be ignored as it's 1. Thus, we just consider its fractional part, (2) can be written as :
$\begin{align} = \frac{1}{\sqrt{N}}&\bigg(|0\rangle + e^{2 \pi i 0.x_n}|1\rangle\bigg)\\&\otimes\bigg(|0\rangle + e^{2 \pi i 0.x_{n-1}x_n}|1\rangle\bigg)\\&\otimes\cdots\otimes\bigg(|0\rangle + e^{2 \pi i 0.x_1x_2...x_{n-1}x_n}|1\rangle\bigg)\,. \tag{3} \end{align}$
Next, let's see Fig.1 showing a diagram of phase estimation: 
$|\psi_1 \rangle$ and $|\psi_2 \rangle$ can be written as follows :
$|\psi_1\rangle = H^{\otimes m}|0\rangle^{\otimes m}\otimes|\psi\rangle=\frac{1}{\sqrt{2^m}}(|0\rangle+|1\rangle)\otimes \cdots \otimes(|0\rangle+|1\rangle)\otimes|\psi\rangle\tag{4}$
When you apply controlled-U gate on $|j\rangle\otimes|\psi\rangle$ where $|j\rangle$ is control qubits it evolves to $|j\rangle U^j|\psi\rangle$. Hence $|\psi_2\rangle$ is represented as follows:
$|\psi_2\rangle =\frac{1}{\sqrt{2^m}}(|0\rangle+|1\rangle U^{2^{m-1}})\otimes(|0\rangle+|1\rangle U^{2^{m-2}})\otimes \cdots \otimes(|0\rangle+|1\rangle U^{2^{0}})\otimes|\psi\rangle\tag{5}$
Since $U^{2^{m-1}}=e^{2\pi i \theta 2^{m-1}}$ (5) can be written as (6):
$|\psi_2\rangle =\frac{1}{\sqrt{2^m}}(|0\rangle+e^{2\pi i \theta 2^{m-1}}|1\rangle )\otimes(|0\rangle+e^{2\pi i \theta 2^{m-2}}|1\rangle )\otimes \cdots \otimes(|0\rangle+e^{2\pi i \theta 2^{0}}|1\rangle )\otimes|\psi\rangle\tag{6}$
Therefore, first register can be represented as follows :
$\frac{1}{\sqrt{2^m}}(|0\rangle + e^{2\pi i \theta 2^{m-1}}|1\rangle ) \otimes (|0\rangle + e^{2\pi i \theta 2^{m-2}}|1\rangle ) \otimes \cdots \otimes (|0\rangle + e^{2\pi i \theta 2^{0}}|1\rangle ) \tag{7}$
A phase $\theta$ is an m-qubit real number. Let $\theta$ be :
$\theta = 0.\theta_1\theta_2...\theta_m \tag{8}$
Putting (8) into (7) gives :
$\frac{1}{\sqrt{2^m}}(|0\rangle + e^{2\pi i 0.\theta_m} |1\rangle ) \otimes (|0\rangle + e^{2\pi i 0.\theta_{m-1}\theta_{m}}|1\rangle ) \otimes \cdots \otimes (|0\rangle + e^{2\pi i 0.\theta_1\theta_2..\theta_{m-1}\theta_{m} }|1\rangle ) \tag{9}$
Comparing (3) and (9), you see they have the same form. Hence, by applying an Inverse QFT on (9) we can get (8).
-EDIT-
QFT can be expressed in a tensor product form. I've added its derivation below.
Let input $x$ be a binary string $x=[x_1x_2..x_n] \, x_k \in \{0, 1\} \, k=\{1,2,..,n\}$
QFT can be expressed in a form (10): $$\text{QFT}(|x\rangle) = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\omega_N^{jx}|j\rangle_n \tag{10}$$
Let $j$ also be a binary string $j = [j_1j_2..j_n] \, j_k \in \{0,1\}, k = \{1,2,..,n\}$
Since $\sum_{j=0}^{N-1}$ is $\sum_{j_1=0}^{1}\sum_{j_2=0}^{1}\cdots \sum_{j_n=0}^{1}$, (10) can be written as (11):
$$\frac{1}{\sqrt{N}}\sum_{j_1=0}^{1}\sum_{j_2=0}^{1}\cdots \sum_{j_n=0}^{1}\omega_N^{jx}|j\rangle_n \tag{11}$$
Rewriting j as $j_1j_2...j_n$ in (11) gives (12): $$\frac{1}{\sqrt{N}}\sum_{j_1=0}^{1}\sum_{j_2=0}^{1}\cdots \sum_{j_n=0}^{1}\omega_N^{jx}|j_1j_2..j_n\rangle \tag{12}$$
Next, the exponent of $\omega$ in (12) can be expressed using $\sum$ form. As j can also be expressed using the sum of power of 2 times $j_k$, namely
$j = \sum_{k=1}^{n}2^{n-k} \cdot j_k \tag{13}$
Putting (13) to (12) gives (14):
$$\frac{1}{\sqrt{N}}\sum_{j_1=0}^{1}\sum_{j_2=0}^{1}\cdots \sum_{j_n=0}^{1}\omega_N^{x \cdot \sum_{k=1}^{n}2^{n-k} \cdot j_k}|j_1j_2..j_n\rangle \tag{14}$$
Now let's rewrite $\omega_N^{x \cdot \sum_{k=1}^{n}2^{n-k} \cdot j_k}|j_1j_2..j_n\rangle$ in (14) with tensor product notation:
$$\frac{1}{\sqrt{N}}\sum_{j_1=0}^{1}\sum_{j_2=0}^{1}\cdots \sum_{j_n=0}^{1}\bigotimes_{k=1}^n\omega_N^{x \cdot \sum_{k=1}^{n}2^{n-k} \cdot j_k}|j_k\rangle \tag{15}$$
Putting $\sum_{j_1=0}^{1}\sum_{j_2=0}^{1}\cdots \sum_{j_n=0}^{1}$ inside $\bigotimes_{k=1}^n$ in (15) gives (16):
$$\frac{1}{\sqrt{N}}\bigotimes_{k=1}^n \sum_{j_k=0}^{1}\omega_N^{x \cdot \sum_{k=1}^{n}2^{n-k} \cdot j_k}|j_k\rangle \tag{16}$$
Expanding $\sum_{j_k=0}^{1}$ in (16) gives : $$\frac{1}{\sqrt{N}}\bigotimes_{k=1}^n (\omega_N^{x \cdot 2^{n-k}\cdot 0}|0\rangle + \omega_N^{x \cdot 2^{n-k} \cdot 1}|1\rangle) \tag{17}$$
In (17), $\omega_N^{x \cdot 2^{n-k}\cdot 0} = \omega_N^{0} = 1$. Therefore, (17) can be written as (18):
$$\frac{1}{\sqrt{N}}\bigotimes_{k=1}^n (|0\rangle + \omega_N^{x \cdot 2^{n-k}}|1\rangle) \tag{18}$$
In (18), $\omega_N^{x \cdot 2^{n-k}}$ can be written as $e^{\frac{2\pi i x}{2^k}}$ because :
$$\omega_N^{x \cdot 2^{n-k}} = e^{\frac{2\pi i x \cdot 2^{n-k}}{N}} = e^{\frac{2\pi i x \cdot 2^{n-k}}{2^n}} = e^{\frac{2\pi i x}{2^k}} \tag{19}$$
Putting (19) to (18) gives (20):
$$\frac{1}{\sqrt{N}}\bigotimes_{k=1}^n (|0\rangle + e^{\frac{2\pi i x}{2^k}}|1\rangle) \tag{20}$$
As (20) is (1), (1) has been derived.
- $\begingroup$ Thank you for the detailed explanation. $\endgroup$shrini1000– shrini10002025-01-12 15:29:42 +00:00Commented Jan 12 at 15:29
- $\begingroup$ Can you please also show how equation #1 in your answer is derived? $\endgroup$shrini1000– shrini10002025-01-12 15:47:08 +00:00Commented Jan 12 at 15:47
- 1$\begingroup$ I've added the derivation after EDIT, please take a look. $\endgroup$taketoshi kinoshita– taketoshi kinoshita2025-01-13 06:35:30 +00:00Commented Jan 13 at 6:35
- $\begingroup$ Thank you once again. $\endgroup$shrini1000– shrini10002025-01-13 15:03:59 +00:00Commented Jan 13 at 15:03