$\require{cancel} \newcommand{\Ket}[1]{\left|{#1}\right\rangle} \newcommand{\Bra}[1]{\left\langle{#1}\right|} \newcommand{\Braket}[1]{\left\langle{#1}\right\rangle} \newcommand{\Rsr}[1]{\frac{1}{\sqrt{#1}}} \newcommand{\RSR}[1]{1/\sqrt{#1}} \newcommand{\Verti}{\rvert} \newcommand{\HAT}[1]{\hat{\,#1~}} \DeclareMathOperator{\Tr}{Tr}$
Quantum Phase Estimation - Why¶
First created in September 2018
Ref:
Quantum Phase Estimation but we are not following its illustration, as it is confusing.
Motivation¶
Quantum phase is useful in many algorithms due to its relative and modular nature. It is not distinguishable among $\phi_\kappa=\phi_0+2\kappa\pi~~(\kappa\in\mathbb Z)$ so one can do modular arithmetic in calculation, e.g. Quantum Fourier Transform (QFT) and Shor's Algorithm.
However, phase is relative and cannot be directly measured with measurement gates. For example, $\Ket+$ and $\Ket-$ both measure 50-50 chance of a 0 and 1, but their phases differ by $\pi$.
Quantum Phase Estimation (QPE) is a process to measure how much phase change an operator $U$ effects on its eigenstate $\Ket\psi$. In other words, QPE is to measure the eigenvalue of $U$ given an eigenstate.
Phase Saving¶
Modular Arithmetic¶
In this context, $\Theta$ is the count of $2\pi$ cycles, a "digitised cycle phase". $\Theta=1$ is a phase of $2\pi$. Fractional phase is represented in decimal or binary. e.g. $\pi/4=2\pi/8$ is presented as $0.125$ in decimal or $[0.001]$ in binary.
For an angular phase $\phi$, the cycle phase $\Theta=\phi/2\pi$. We further define $\phi_m\equiv 2\pi/m$, which is a unit of $1/m$ cycle.
$j\phi_m$ and $k\phi_m$ is in phase if and only if $j\equiv k\pmod m.~~~~$
Proof: $j\equiv k\pmod m ~\Leftrightarrow~j=k+\kappa m ~\Leftrightarrow~j\phi_m =k\phi_m+\kappa m\phi_m =k\phi_m+\kappa m\cdot 2\pi/m =k\phi_m+2\kappa\pi .$
Eigenvalue as Phase¶
Given a unitary $U$ and one of its eigenstates $\Ket\psi$, the eigenvalue would be a unit-length complex number, or a phase. We have $U\Ket\psi=e^{2\pi i\Theta}\Ket\psi$, where $\Theta\in[0,1).$
The QPE algorithm estimates the value of $\Theta$. In other words, it is to find the eigenvalue of a unitary operator, given an eigenstate.
The strategy is to have a "measuring" register $\Ket x$ and an eigenstate register $\Ket\psi$. By applying an $x$-controlled $U$ to $\Ket\psi$ one would "modulate" the phase $2\pi i\Theta$ into $\Ket x$. Measuring $\Ket x$ would give a bit pattern approximating $\Theta$. The more qubits in $\Ket x$, the more accurate the approximation is.
To illustrate, let $cU^j$ be the $q$-controlled $U^j$ operation. $U^j\Ket\psi=e^{2\pi i\cdot j\Theta}\Ket\psi.$
When $\Ket{q}$ is initialised to $\Ket+$, $cU^j\left(\Ket{q}\otimes\Ket\psi\right) =\Rsr2\left(\Ket0\Ket\psi+\Ket1 e^{2\pi i\cdot j\Theta}\Ket\psi\right) =\Rsr2\left(\Ket0+e^{2\pi i\cdot j\Theta}\Ket1\right)\Ket\psi .$
You can see the "kick back" of the phase change $e^{2\pi i\cdot j\Theta}$ from $\Ket\psi$ to $\Ket x$. This is not surprising given that phase is only relative. The trick is that we use $\Ket\psi$ as a common reference that all qubits in $\Ket x$ is relative to, such that there are phases differences built up among the qubits $q_r$.
When we apply the $q_r$-controlled $U^{2^r}$ to $\Ket\psi$, as $\Ket\psi$ is an eigenstate of $U$, it will shift a phase of $2^r\Theta$, which will reflect on $q_r$ given the common reference.
The measuring register $\Ket x$ will build up a pattern of $\sum_{r=0}^n2^r\Theta$. Such "phase modulation" can be read out by the inverse Quantum Fourier Transform $QFT^{-1}$.
Formulation¶
To measure $\Ket\psi$ with $n$ qubits, we apply a successive $\Ket+$ controlled $U^{2r}$ to $\Ket\psi,~$ where $r\in[0,n-1]$.
Let the measuring register be $\Ket x=\Ket{q_{n-1}q_{n-2}\ldots q_1q_0}$, and $\Ket k$ is standard basis vector with $k$ being the numerical value of $q_{n-1}\ldots q_0$.
i.e. $\Ket x=[x_0,x_1,\ldots,x_{N-1}]^T=\sum_{k=0}^{N-1}x_k\Ket k,~~$ where $N=2^n.~~$
Note: While there are only $n$ qubits of $q_r$, there are $N=2^n$ states $x_k\Ket k$, each $x_k$ is represented as a unique pattern of $q_{n-1}\ldots q_0$.
Now let $c_rU^{2^r}\Ket\psi$ be a controlled $U^{2^r}$ operation on $\Ket\psi$ with $q_r$ being the control qubit. $\Ket x$ was initialised to ${1\over\sqrt{N}}\left(\Ket0+\Ket1\right)^{\otimes n}.~~$ ($\Ket\psi$ is omitted in the following to emphasise the phase change on $\Ket x$.)
After the operation, $x$ will become $\displaystyle \left(\prod_{r=1}^n\!^\otimes~c_{n-r}U^{2^{(n-r)}}\right) {1\over\sqrt{N}}\left(\Ket0+\Ket1\right)^{\otimes n}$
$\displaystyle={1\over\sqrt{N}} \left(\Ket0+e^{2\pi i\cdot 2^{n-1}\Theta}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i\cdot 2^{n-2}\Theta}\Ket1\right)\otimes \ldots\otimes \left(\Ket0+e^{2\pi i\cdot 2\Theta}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i\cdot\Theta}\Ket1\right) ={1\over\sqrt N}\sum_{k=0}^{N-1}e^{2\pi i\cdot k\Theta}\Ket k .$
This is very similar to QFT (Quantum Fourier Transform). If we apply $F_N$ to a basis state $\Ket q$,
$\displaystyle F_N\Ket q ={1\over\sqrt N}\prod_{r=1}^n\!^\otimes\left(\Ket0+e^{2\pi i~q\cdot2^{-r}}\Ket1\right)$
$\displaystyle={1\over\sqrt N} \left(\Ket0+e^{2\pi i~q\cdot2^{-1}}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i~q\cdot2^{-2}}\Ket1\right)\otimes \ldots\otimes \left(\Ket0+e^{2\pi i~q\cdot2^{-n+1}}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i~q\cdot2^{-n}}\Ket1\right)$
$\displaystyle={1\over\sqrt N} \left(\Ket0+e^{2\pi i\cdot2^{n-1}(q/N)}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i\cdot2^{n-2}(q/N)}\Ket1\right)\otimes \ldots\otimes \left(\Ket0+e^{2\pi i\cdot2(q/N)}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i\cdot(q/N)}\Ket1\right)$
$={1\over\sqrt N}\sum_{k=0}^{N-1}e^{2\pi i\cdot k(q/N)}\Ket k .$
By observation of $\Ket x$ vs $F_N\Ket q$, we can see that $\Theta\sim(q/N)$. In other words, $\Ket x$ is "modulated" with the phase from $\Ket\psi$.
So we can use $QFT^{-1}$ to reverse the process to find the $\Theta$ pattern. The larger $N$ is, the higher the precision of approximating $\Theta$ with $q/N$.
Visualisation¶
If we initialise the measuring register $\Ket x$ to $\Ket+^\otimes n$, it will be an unbiased superposition of $\Rsr N\sum_{k=0}^{N-1}\Ket k.$
All standard basis states $\Ket k$ are of the same "baseline" phase of zero. $\Ket x=\Rsr N\sum_{k=0}^{N-1}e^{2\pi i\cdot 0}\Ket k.$
After the $q_r$-controlled $U^{2^r}$ operation, a phase is built up: $\Ket x=\Rsr N\sum_{k=0}^{N-1}e^{2\pi i\cdot k\Theta}\Ket k.$
So the originally zero rotation from $\Ket 0$ to $\Ket{N-1}$, now it is spiraling through the states, adding a $\Theta$ phase per state in the numerical rank.
When $F_N^{-1}$ is operating on $\Ket x$, all rows would add up to zero, except for the row with $q/N$ equal (or close) to $\Theta$. Such row will add up to unity (or close). It is like the resonance in the continuous Fourier Transform, in which the phase in $\Ket x$ "resonances" with $\Ket\xi_q$, the $q^\mathrm{th}$ column of $F_N$, resulting in state $\Ket q$.
Recall $\Ket x=\left({1\over\sqrt N}\sum_{k=0}^{N-1}e^{2\pi i\cdot k\Theta}\Ket k\right).~~$ Because $F_N\Ket q\approx\Ket x,~~$ We have $F_N^{-1}\Ket x\approx\Ket q.$
Examples¶
Useful things:
$R_x(\pi\Theta)=\begin{bmatrix}\cos\pi\Theta/2&-i\sin\pi\Theta/2\\-i\sin\pi\Theta/2&\cos\pi\Theta/2\end{bmatrix} .$
$R_x(\pi/2)=\Rsr2\begin{bmatrix}1&-i\\-i&1\end{bmatrix}=-i\sqrt X,~~~ R_x(\pi)=\begin{bmatrix}0&-i\\-i&0\end{bmatrix}=-iX,~~~ R_x(2\pi)=\begin{bmatrix}-1&0\\0&-1\end{bmatrix}=-I,~~~ R_x(4\pi)=\begin{bmatrix}1&0\\0&1\end{bmatrix}=I .$
$F_2 =\Rsr2\begin{bmatrix}1&1\\1&\omega_1\end{bmatrix} =\Rsr2\begin{bmatrix}1&1\\1&-1\end{bmatrix} =H.~~~~ F_2^{-1} =\Rsr2\begin{bmatrix}1&1\\1&\overline{\omega_1}\end{bmatrix} =\Rsr2\begin{bmatrix}1&1\\1&-1\end{bmatrix} =H .$
$F_4 =\Rsr4\begin{bmatrix} 1&1&1&1\\ 1&\omega_2&\omega_2^2&\omega_2^3\\ 1&\omega_2^2&\omega_2^4&\omega_2^6\\ 1&\omega_2^3&\omega_2^6&\omega_2^9\\ \end{bmatrix} ={1\over2}\begin{bmatrix} 1&1&1&1\\ 1&i&-1&-i\\ 1&-1&1&-1\\ 1&-i&-1&i\\ \end{bmatrix} .$
$F_4^{-1} =\Rsr4\begin{bmatrix} 1&1&1&1\\ 1&\overline{\omega_2}&\overline{\omega_2^2}&\overline{\omega_2^3}\\ 1&\overline{\omega_2^2}&\overline{\omega_2^4}&\overline{\omega_2^6}\\ 1&\overline{\omega_2^3}&\overline{\omega_2^6}&\overline{\omega_2^9}\\ \end{bmatrix} ={1\over2}\begin{bmatrix} 1&1&1&1\\ 1&-i&-1&i\\ 1&-1&1&-1\\ 1&i&-1&-i\\ \end{bmatrix} .$
1-Qubit Register¶
Case $n=1,~~U=R_x(\pi),~~N=2^n=2.$
When $\Ket\psi=\Ket+,~~R_x(\pi)\Ket\psi=-i\Ket+,~~\Theta_+=0.75=[0.11].$
When $\Ket\psi=\Ket-,~~R_x(\pi)\Ket\psi=i\Ket-,~~\Theta_-=0.25=[0.01].$
$\Ket x$ was initialised to ${1\over\sqrt2}\left(\Ket0+\Ket1\right),$ which is irrespective of $\Ket\psi$. After the operation, $\Ket x$ is changed.
When $\displaystyle\Ket\psi=\Ket+~$:
$\left(c_0R_x(\pi)\right)\Ket x\Ket\psi =\left(c_0R_x(\pi)\right){1\over\sqrt2}\left(\Ket0+\Ket1\right)\Ket+ ={1\over\sqrt2}\left(\Ket0\Ket+ +\Ket1 R_x(\pi)\Ket+\right) ={1\over\sqrt2}\left(\Ket0\Ket+ -i\Ket1\Ket+\right) ={1\over\sqrt2}\left(\Ket0-i\Ket1\right)\Ket+\\ ={1\over\sqrt2} \left(\Ket0+e^{2\pi i\cdot1\times 0.75}\Ket1\right)\Ket+ ={1\over\sqrt2}\sum_{k=0}^1e^{2\pi i\cdot k\times 0.75}\Ket k\Ket+ =\begin{bmatrix}\Rsr2\\-i\Rsr2\end{bmatrix}\otimes\Ket+ .$
$F_2^{-1}\Ket x =H\begin{bmatrix}\Rsr2\\-i\Rsr2\end{bmatrix} ={1\over2}\begin{bmatrix}1-i\\1+i\end{bmatrix} .$ Measuring this will give you half a chance of $0$ and $1$.
When $\displaystyle\Ket\psi=\Ket-~$:
$\Ket x\Ket\psi =\left(c_0R_x(\pi)\right){1\over\sqrt2}\left(\Ket0+\Ket1\right)\Ket- ={1\over\sqrt2}\left(\Ket0\Ket- +\Ket1 R_x(\pi)\Ket-\right) ={1\over\sqrt2}\left(\Ket0\Ket- +i\Ket1\Ket-\right) ={1\over\sqrt2}\left(\Ket0+i\Ket1\right)\Ket-\\ ={1\over\sqrt2} \left(\Ket0+e^{2\pi i\cdot1\times 0.25}\Ket1\right)\Ket- ={1\over\sqrt2}\sum_{k=0}^1e^{2\pi i\cdot k\times 0.25}\Ket k\Ket- =\begin{bmatrix}\Rsr2\\i\Rsr2\end{bmatrix}\otimes\Ket- .$
$F_2^{-1}\Ket x =H\begin{bmatrix}\Rsr2\\i\Rsr2\end{bmatrix} ={1\over2}\begin{bmatrix}1+i\\1-i\end{bmatrix} .$ Measuring this will give you half a chance of $0$ and $1$.
2-Qubit Register¶
Let us increase the number of qubits to 2 and see if it gives a better approximation.
Case $n=2,~~U=R_x(\pi),~~N=2^n=4.$
$U$ and $\Ket\psi$ have not changed, so we can recall: $~~\Theta_+=0.75=[0.11]$ and $\Theta_-=0.25=[0.01].$
$\Ket x$ was initialised to $\Rsr2\left(\Ket0+\Ket1\right)\otimes\Rsr2\left(\Ket0+\Ket1\right).~~$ We omit $\Ket\psi$ here but please be reminded that $R_x$ is on $\Ket\psi$, not on $\Ket1$.
When $\displaystyle\Ket\psi=\Ket+~$:
$\displaystyle\Ket x =\left(c_1R_x(2\pi)\right){1\over\sqrt2}\left(\Ket0+\Ket1\right)\otimes \left(c_0R_x(\pi)\right){1\over\sqrt2}\left(\Ket0+\Ket1\right) ={1\over\sqrt2}\left(\Ket0-\Ket1\right)\otimes {1\over\sqrt2}\left(\Ket0-i\Ket1\right)\\ ={1\over\sqrt4} \left(\Ket0+e^{2\pi i\cdot2\times 0.75}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i\cdot1\times 0.75}\Ket1\right) ={1\over\sqrt4}\sum_{k=0}^3e^{2\pi i\cdot k\times 0.75}\Ket k ={1\over\sqrt4}\begin{bmatrix}1\\-i\\-1\\i\end{bmatrix} .$
$F_4^{-1}\Ket x =\Rsr4 \begin{bmatrix} 1&1&1&1\\ 1&-i&-1&i\\ 1&-1&1&-1\\ 1&i&-1&-i\\ \end{bmatrix} \Rsr4 \begin{bmatrix} 1\\ -i\\ -1\\ i\\ \end{bmatrix} =\begin{bmatrix} 0\\ 0\\ 0\\ 1\\ \end{bmatrix} .$ Measuring this will give you $\Ket{11}$ with certainty, which means $\Theta=0.75=[0.11].$
When $\displaystyle\Ket\psi=\Ket-~$:
$\displaystyle\Ket x =\left(c_1R_x(2\pi)\right){1\over\sqrt2}\left(\Ket0+\Ket1\right)\otimes \left(c_0R_x(\pi)\right){1\over\sqrt2}\left(\Ket0+\Ket1\right) ={1\over\sqrt2}\left(\Ket0-\Ket1\right)\otimes {1\over\sqrt2}\left(\Ket0+i\Ket1\right)\\ ={1\over\sqrt4} \left(\Ket0+e^{2\pi i\cdot2\times 0.25}\Ket1\right)\otimes \left(\Ket0+e^{2\pi i\cdot1\times 0.25}\Ket1\right) ={1\over\sqrt4}\sum_{k=0}^3e^{2\pi i\cdot k\times 0.25}\Ket k ={1\over\sqrt4}\begin{bmatrix}1\\i\\-1\\-i\end{bmatrix} .$
$F_4^{-1}\Ket x =\Rsr4 \begin{bmatrix} 1&1&1&1\\ 1&-i&-1&i\\ 1&-1&1&-1\\ 1&i&-1&-i\\ \end{bmatrix} \Rsr4 \begin{bmatrix} 1\\ i\\ -1\\ -i\\ \end{bmatrix} =\begin{bmatrix} 0\\ 1\\ 0\\ 0\\ \end{bmatrix} .$ Measuring this will give you $\Ket{01}$ with certainty, which means $\Theta=0.25=[0.01].$
"Recovery" of $\Theta$ from $\Ket x$¶
Now, let us see if $F_N^{-1}\Ket q={1\over\sqrt N}\sum_{k=0}^{N-1}e^{-2\pi i\cdot k(q/N)}\Ket k$ would recover $\Theta$.
A recap on QFT:
Given $\omega_n=e^{2\pi i/N}$, $\boxed{\displaystyle y_k={1\over\sqrt N}\sum_{j=0}^{N-1}x_j\omega_n^{jk}~}$ and $\omega^{jk}=\omega^{kj},~~$ we have $\Ket y=F_N\Ket x,~~F_N^{-1}\Ket y=\Ket x,~$ and $\boxed{\displaystyle x_j={1\over\sqrt N}\sum_{k=0}^{N-1}y_k\omega_n^{-jk}~}$.
This makes sense as $\displaystyle y_k ={1\over\sqrt N}\sum_{j=0}^{N-1}\left({1\over\sqrt N}\sum_{k'=0}^{N-1}y_{k'}\omega_n^{-jk'}\right)\omega_n^{jk} ={1\over N}\sum_{k'=0}^{N-1}y_{k'}\left(\sum_{j=0}^{N-1}\omega_n^{-jk'}\omega_n^{jk}\right) ={1\over N}\sum_{k'=0}^{N-1}y_{k'}\left(\sum_{j=0}^{N-1}\omega_n^{j(k-k')}\right) .$
The $\omega_n$ terms will add up to zero when $k\ne k'$, and add up to $N$ when $k=k'$. So $\displaystyle y_k={1\over N}y_kN=y_k.$
$\ldots$
Given $\displaystyle\Ket x={1\over\sqrt N}\sum_{j=0}^{N-1}e^{2\pi i\cdot j\Theta}\Ket j$, we can express $\displaystyle \Ket x ={1\over\sqrt N}\sum_{j=0}^{N-1}x_j\Ket j,~~$ where $x_j=e^{2\pi i\cdot j\Theta}.$
$\Ket y ={1\over\sqrt N}\sum_{k=0}^{N-1}y_k\Ket k,~~$ where $y_k={1\over\sqrt N}\sum_{j=0}^{N-1}x_j\omega_n^{jk} .$
Here is the circuit from Wikipedia. The top line is the MSB.
The $QFT_n^{-1}$ (Inverse Quantum Fourier Transform) on the right is as following.
Note: $R_n$ gates in $QFT_n$ are phase shift by $2\pi/2^n$. In $QFT_n^{-1}$, the phase shift is negative, i.e. $\displaystyle \exp\left(-2\pi i~[0.\overbrace{0..1}^n]\right).$ So $R_2$ is $S^\dagger$, $R_3$ is $T^\dagger$ and so on.
