範例導向學習量子相位估計 (Quantum Phase Estimation)。

有錯再麻煩指正。

用途

Quantum phase estimation (QPE) 的主要功能: finding the eigenvalue of a unitary operator (找出么正算子¹的特徵值)

Review linear algebra

$A$ is a matrix, $\lambda$ is the eigenvalue of $A$ where two $u$ vectors are the eigenvectors.

$$Au = \lambda u$$

特性:

• $(A-\lambda I )u =0$
• $\det(A-\lambda I ) =0\iff u \ne \vec{0}$

Quantum form for eigenvalue and eigenvector

$U$ is a unitary matrix, $\lambda$ is the eigenvalue of $U$ where two $\mu$ vectors are the eigenvectors (or eigenstates).

$$U\lvert\mu\rangle = \lambda \lvert\mu\rangle$$

特性:

• $\because U$ is a unitary matrix $\therefore \lvert\det(U)\rvert =\lvert\lambda\rvert= 1 \Rightarrow\lambda = e^{i\theta} = e^{2\pi i\varphi}, 0 \le\varphi < 1$
• $\Rightarrow U\lvert\mu\rangle = e^{2\pi i\varphi}\lvert\mu\rangle$

Example: X

$X$ gate has two eigenvalues ($\lambda_1, \lambda_2$) and corresponding eigenvectors ($\lvert \mu_1\rangle, \lvert \mu_2\rangle$)

$U = X =\begin{pmatrix}0&1\\1&0\end{pmatrix}$

$\det(X-\lambda I) = 0\Rightarrow$

$\begin{vmatrix}-\lambda&1\\1&-\lambda\end{vmatrix} = 0 = \lambda^2-1 \Rightarrow \lambda=\pm 1\Rightarrow$

$\begin{cases}
\lambda_1 = 1, u_1 =\frac{1}{\sqrt{2}} \begin{pmatrix}1\\1\end{pmatrix}\Rightarrow \lvert \mu_1\rangle =\frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1 \rangle)\\
\lambda_2 = -1, u_2 =\frac{1}{\sqrt{2}}
\begin{pmatrix}1\\-1\end{pmatrix}\Rightarrow \lvert \mu_2\rangle =\frac{1}{\sqrt{2}}(\lvert 0\rangle-\lvert 1 \rangle
\end{cases}$

Phase kickback

Phase kickback 是在量子糾纏 (entanglement) 下的一種現象，原本在量子糾纏下 $C\mbox{-}U$ (controlled-U) 運算會由控制位元 (control bit) 影響目標位元 (target qubit)，然而在有些情況中目標位元會維持輸入的狀態反而是控制位元的相位 (phase) 會受到影響 (不影響 0, 1 的機率)。

可以看成 $\lambda\lvert xy\rangle$ 有兩種表達方式，但是展開後會發現確實是 control bit 受到影響，也就是 $(\lambda\lvert x\rangle)\lvert y\rangle$:

$\lambda\lvert xy\rangle = \lvert x\rangle(\lambda \lvert y\rangle) = (\lambda\lvert x\rangle)\lvert y\rangle$

Example 1: CX

$U = X\Rightarrow C\mbox{-}U = CX = CNOT$

可以看到以 $\lvert +-\rangle, \lvert - -\rangle$ 為輸入的話其對應的結果反而是 control bit 的相位有變化。

Example 2: CZ

$U = Z\Rightarrow C\mbox{-}U = CZ$

$CZ\big(\frac{1}{\sqrt{2}}(
\lvert 01\rangle+\lvert 11\rangle)\big) =\frac{1}{\sqrt{2}}
(\lvert 01\rangle - \lvert 11\rangle)$

Quantum phase estimation

利用 Phase kickback 的現象及 IQFT (請參考前幾篇文章) 來產生 $U$ 對應的 eigenvalue。

運算式定義

$U$ 次方計算定義如下

$U^n\lvert\mu\rangle = \underbrace{U…U}_{n}\lvert\mu\rangle=\lambda^n \lvert\mu\rangle$

邏輯閘

上方使用 $t$ 個 qubit 作為估計位 (counting qubits)，通常越多位會越精準，除非已被二進位小數完整表達。例如，$t = 3$，可以精確到 $\frac{1}{2^3} = \frac{1}{8}$。下方 $\lvert\mu\rangle$ 為 eigenvector 輸入，輸出 $\lvert 2^t\varphi\rangle$ 為 eigenvalue。

Example 1: U = X with t = 1

以其中一組 eigenvector、eigenvalue 示範。

從結果可以有以下推導: $\frac{1}{\sqrt{2}}(\lvert 0\rangle+e^{2\pi i (2^{0}\varphi)}\lvert 1\rangle)\Rightarrow e^{2\pi i (2^0\varphi)} =\lambda = -1$，不過相位的資訊在觀測時就會消失，所以這邊要借助 IQFT 來將相位的資訊 (Fourier basis) 轉換到 qubit (Computational basis) 上，如下圖。

有 IQFT 的幫助下，測量的輸出是 $p = \lvert 1\rangle$，此時可以根據 $t = 1$ 代入求 eigenvalue 的公式: $\lambda = e^{2\pi i(\frac{p}{2^t})} = e^{2\pi i(\frac{1}{2^1})} = -1$。這邊因為剛好 $U = X$ 所需要的精確度是 0.5 所以 $t$ (counting qubits) 只需要 1 個位元即可。

實際執行

Example 2: U = X with t = 2

雖然 $t$ (counting qubits) 只需要 1 個位元即可，這邊還是使用這個邏輯閘當作使用更多 $t$ 的情況。$t = 2$ 輸出為 $\lvert 10\rangle$ 代入公式 $\lambda = e^{2\pi i(\frac{p}{2^t})} = e^{2\pi i(\frac{2}{2^2})} = -1$。

實際執行

Example 3: U = X with t = 3

Example 4: U = X with t = 4

Eigenvectors superposition

上面示範的都是事先已知 eigenvector，例如都使用 $X$ 的其中一個 eigenvector ($\lvert \mu_2\rangle$) 來求得 eigenvalue ($\lambda_2$)。

但是一般情況沒這麼容易，因為若是知道 eigenvector 的話直接化簡就可以得到 eigenvalue。這裡可以利用疊加態同時存在不同狀態的能力，將 eigenvector 的疊加態當作輸入，則觀測輸出就會是其中一個 eigenvalue，利用統計的方式找出機率最大的幾個來代入公式。

Example: U = X with t = 4

回顧 $X$ 有兩組 eigenvector、eigenvalue: $(\lambda_1, \mu_1), (\lambda_2, \mu_2)$

其中 $\mu_1\rangle =\frac{1}{\sqrt{2}}(\lvert 0\rangle+\lvert 1 \rangle)$、$\mu_2\rangle =\frac{1}{\sqrt{2}}(\lvert 0\rangle-\lvert 1 \rangle)$，這邊可以發現 $\lvert\mu_1\rangle+ \lvert \mu_2\rangle =\lvert 0\rangle$，因此以疊加態當作輸入的會變得容易許多。

q[4] 為 eigenvectors 疊加態:

根據輸出結果，理論上可以得到兩個 eigenvalue:

• ${\color{red}\lvert 1000\rangle} =\lvert 8\rangle\Rightarrow\lambda = e^{2\pi i {\color{blue}(}\frac{\color{red}{8}}{2^4}{\color{blue})}} = -1$
• ${\color{red}\lvert 0000\rangle} =\lvert 0\rangle\Rightarrow\lambda = e^{2\pi i {\color{blue}(}\frac{\color{red}{0}}{2^4}{\color{blue})}} = 1$

References

• 量子计算 [5] – QFT & 相位估计 - nyasyamorina
• 为什么量子相位估计可以求矩阵特征值 - 你是想难为我胖虎
• Quantum Phase Estimation - IBM
• QC — Phase estimation in Shor’s Algorithm - Jonathan Hui
• Controlled NOT gate - wiki
• Quantum Phase Kickback - Frank Zickert | Quantum Machine Learning