量子相位估計演算法

在量子計算中，量子相位估計算法是一種用於估計給定么正算符的某個特徵值所對應相位的量子演算法。由於么正算符的特徵值模數恆為1，它們的特性取決於其相位，因此該演算法可以等效地描述為提取相位或特徵值本身。此演算法最初由阿列克謝·基塔耶夫於1995年提出。

相位估計經常作為其他量子演算法中的子程序使用，例如秀爾演算法、解線性方程組的量子演算法以及量子計數演算法。

演算法概覽

此演算法在兩組量子位元上運作，在此文中稱為暫存器。這兩個暫存器分別包含 n 和 m 個量子位元。令 U 為一個作用於 m 量子位元暫存器上的么正算符。么正算符的特徵值模數為1，因此其特性由相位決定。因此，若 | \psi \rangle 是 U 的一個特徵向量，則對於某個 \theta\in\mathbb{R} ，有 U| \psi\rangle = e^{ 2\pi i \theta}\left|\psi \right\rangle 。由於複指數的週期性，我們總是可以假設 0 \leq \theta < 1 。

目標是使用少量閘和高成功機率來產生一個 \theta 的良好近似值。量子相位估計算法假設可以諭示機存取 U ，並且能取得量子態 |\psi\rangle ，從而實現這一目標。這意味著在討論演算法效率時，我們只關心需要使用 U 的次數，而不考慮實現 U 本身的成本。

更精確地說，該演算法使用第一個暫存器中的 n=O(\log(1/\varepsilon)) 個量子位元和 O(1/\varepsilon) 次受控U操作，以高機率回傳一個 \theta 的近似值，其加法誤差在 \varepsilon 以內。此外，我們可以透過總共使用 O(\log(1/\Delta)/\varepsilon) 次受控U操作，將成功機率提高到 1-\Delta （對於任何 \Delta>0 ），並且這是最優的。

演算法詳述

狀態準備

系統的初始狀態為：

|\Psi_0\rangle = |0\rangle^{\otimes n}|\psi\rangle ,

其中 |\psi\rangle 是通過 U 演化的 m 量子位元狀態。我們首先對第一個暫存器應用 n-量子位元阿達馬閘操作 H^{\otimes n} ，產生狀態： |\Psi_1\rangle = (H^{\otimes n}\otimes I_m)|\Psi_0\rangle = \frac{1}{2^{\frac{n}{2}}}(|0\rangle + |1\rangle)^{\otimes n}|\psi\rangle = \frac{1}{2^{n/2}} \sum_{j = 0}^{2^n - 1} |j\rangle |\psi\rangle. 請注意，這裡我們在 n 量子位元暫存器的二進位和 n 進位表示法之間進行切換：右邊的右矢 |j\rangle 是 n 量子位元狀態 |j\rangle\equiv \bigotimes_{\ell=0}^{n-1} |j_\ell\rangle 的簡寫，其中 j=\sum_{\ell=0}^{n-1} j_\ell 2^\ell 是 j 的二進位分解。

受控U操作

接著，狀態 |\Psi_1\rangle 經過受控么正演化 U_C ，其作用可寫為 U_C(|k\rangle\otimes|\psi\rangle) = |k\rangle\otimes( U^{k}|\psi\rangle), 對於所有 k=0,...,2^n-1 。此演化也可以簡潔地寫作U_C = \sum_{k=0}^{2^n-1} |k\rangle\!\langle k|\otimes U^k, 這突顯了其受控性質：它根據第一個暫存器是否為 |k\rangle 來對第二個暫存器應用 U^k 。回顧 |\psi\rangle 所滿足的特徵值條件，將 U_C 應用於 |\Psi_1\rangle 得到|\Psi_2\rangle \equiv U_C|\Psi_1\rangle = \left(\frac{1}{2^{n/2}}\sum_{k=0}^{2^n-1} e^{2\pi i \theta k}|k\rangle\right)\otimes |\psi\rangle, 其中我們使用了 U^{k}| \psi\rangle = e^{ 2\pi i k\theta}|\psi \rangle 。

為了證明 U_C 也可以被有效率地實現，觀察到我們可以將 U_C 寫成 U_C = \prod_{\ell=0}^{n-1} C_\ell(U^{2^\ell}) ，其中 C_\ell(U^{2^\ell}) 表示根據第一個暫存器的第 \ell 個量子位元是否為 |1\rangle ，對第二個暫存器應用 U^{2^\ell} 的操作。形式上，這些閘的作用可以表徵為C_\ell(U^k) (|j\rangle\otimes |\psi\rangle) = |j\rangle\otimes ( U^{j_\ell k}|\psi\rangle). 此方程式可解釋為，當 j_\ell=0 時，也就是第 \ell 個量子位元為 |0\rangle 時，狀態保持不變；而當第 \ell 個量子位元為 |1\rangle 時，閘 U^k 應用於第二個暫存器。因此，這些受控閘的組合得到\prod_{\ell=0}^{n-1} C_\ell(U^{2^\ell})(|j\rangle\otimes|\psi\rangle) = |j\rangle\otimes\left(U^{\sum_{\ell=0}^{n-1} j_\ell 2^\ell} |\psi\rangle\right)= U_C , 最後一步直接由二進位分解 j=\sum_{\ell=0}^{n-1} j_\ell 2^\ell 得出。

應用逆量子傅立葉轉換

電路的最後一部分是在 |\Psi_2\rangle 的第一個暫存器上應用逆量子傅立葉轉換 (QFT) \mathcal{QFT} ：|\tilde\Psi_3\rangle = \mathcal{QFT}^{-1}_{2^n} |\tilde\Psi_2\rangle. QFT及其逆轉換對基底狀態的作用表徵為 \begin{align} \mathcal{QFT}_N|k\rangle &= N^{-1/2}\sum_{j=0}^{N-1} e^{\frac{2\pi i}{N}jk}|j\rangle, \\ \mathcal{QFT}_N^{-1}|k\rangle &= N^{-1/2}\sum_{j=0}^{N-1} e^{-\frac{2\pi i}{N}jk}|j\rangle. \end{align} 因此可得

|\tilde\Psi_3\rangle = \frac{1}{2^{\frac{n}{2}}}\sum_{k=0}^{2^n - 1} e^{2\pi i \theta k} \left( \frac{1}{2^{\frac{n}{2}}}\sum_{x=0}^{2^n - 1} e^{\frac{-2\pi i k x}{2^n}}|x\rangle \right) = \frac{1}{2^{n}}\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1}e^{-\frac{2\pi i k}{2^n} \left ( x - 2^n \theta \right )} |x\rangle.

將狀態在計算基底中分解為 |\tilde\Psi_3\rangle = \sum_{x=0}^{2^n-1} c_x |x\rangle, 則係數等於 c_x \equiv \frac{1}{2^n} \sum_{k=0}^{2^n-1} e^{-\frac{2\pi ik}{2^n}(x-2^n \theta) } =

\frac{1}{2^{n}}  \sum_{k=0}^{2^n - 1} e^{-\frac{2\pi i k}{2^n} \left ( x-a \right )} e^{2 \pi i \delta k}, 其中我們寫成  2^n \theta = a + 2^n \delta, ，而  a  是最接近  2^n \theta  的整數。差值  2^n\delta  根據定義必須滿足  0 \leqslant |2^n\delta| \leqslant \tfrac{1}{2} 。這相當於將  2^n \theta  四捨五入到最近的整數來近似  \theta \in [0, 1]  的值。

測量

最後一步是在第一個暫存器上進行計算基底的測量。這會以機率 \Pr(y) = |c_y|^2 = \left| \frac{1}{2^{n}} \sum_{k=0}^{2^n-1} e^{\frac{-2\pi i k}{2^n}(y-a)} e^{2 \pi i \delta k} \right |^2.

 得到結果   |y\rangle  。因此，如果  \delta=0 ，即當  \theta  可以寫成  \theta=a/2^n  時， \operatorname{Pr}(a)=1 ，總是可以得到結果  y=a 。另一方面，如果  \delta\neq0 ，機率為 \operatorname{Pr}(a)=\frac{1}{2^{2n}} \left | \sum_{k=0}^{2^n-1} e^{2 \pi i \delta k} \right |^2 = \frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^n \delta}}}{1-{e^{2 \pi i \delta}}} \right|^2.
 從此表達式可以看出，當  \delta\neq0  時， \Pr(a) \geqslant \frac{4}{\pi^2} \approx 0.405 。要證明這一點，我們觀察到根據  \delta  的定義，有不等式  |\delta| \leqslant \tfrac{1}{2^{n+1}} ，因此： \begin{align}

\Pr(a) &= \frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^n \delta}}}{1-{e^{2 \pi i \delta}}} \right |^2 && \text{對於 } \delta \neq 0 \\ &= \frac{1}{2^{2n}} \left | \frac{2 \sin \left ( \pi 2^n \delta\right)}{ 2\sin( \pi \delta)} \right |^2 && \left| 1-e^{2ix}\right|^2 = 4\left| \sin (x)\right|^2 \\ &= \frac{1}{2^{2n}} \frac {\left | \sin\left(\pi 2^n \delta\right) \right |^2}{| \sin( \pi \delta) |^2} \\ &\geqslant \frac{1}{2^{2n}} \frac {\left | \sin\left(\pi 2^n \delta\right) \right |^2}{| \pi \delta |^2} && | \sin(\pi \delta) | \leqslant | \pi \delta | \\ &\geqslant \frac{1}{2^{2n}} \frac {|2 \cdot 2^n \delta|^2}{| \pi \delta |^2} && | 2\cdot2^n \delta | \leqslant | \sin(\pi 2^n\delta) | \text{ 對於 } |\delta| \leqslant \frac{1}{2^{n+1}} \\ &\geqslant \frac {4}{\pi^2} .\end{align}

我們得出結論，該演算法以至少 4/\pi^2 的機率提供 \theta 的最佳 n 位元估計（即與正確答案相差在 1/2^n 以內）。透過增加約 O(\log(1/\epsilon)) 個額外的量子位元並捨棄這些額外的量子位元，機率可以提高到 1 - \epsilon 。

簡單範例

考慮此演算法最簡單的實例，除了編碼 |\psi\rangle 所需的量子位元外，只涉及 n=1 個量子位元。假設 |\psi\rangle 的特徵值為 \lambda=e^{2\pi i \theta} ， \theta\in[0,1) 。演算法的第一部分生成單一量子位元狀態 |\phi\rangle\equiv \frac{1}{\sqrt2}(|0\rangle+\lambda |1\rangle) 。在此情況下，應用逆QFT相當於應用一個阿達馬閘。因此，最終的結果機率為 p_\pm = |\langle\pm|\phi\rangle|^2 ，其中 |\pm\rangle\equiv\frac{1}{\sqrt2}(|0\rangle\pm|1\rangle) ，更明確地說， p_\pm = \frac{|1\pm\lambda|^2}{4} =\frac{1 \pm \cos(2\pi \theta)}{2}. 假設 \lambda=1 ，意即 |\phi\rangle=|+\rangle 。則 p_+=1 ， p_-=0 ，我們從測量結果中確定性地回復了 \lambda 的精確值。如果 \lambda=-1 ，情況亦然。

另一方面，如果 \lambda=e^{2\pi i/3} ，則 p_\pm = [1 \pm \cos(2\pi/3)]/2 ，即 p_+=1/4 和 p_-=3/4 。在這種情況下，結果不是決定性的，但我們仍然發現得到結果 |-\rangle 的可能性較高，這與 2/3 較接近1而非0的事實相符。

更一般地說，如果 \lambda=e^{2\pi i\theta} ，則 p_+\ge 1/2 的充分必要條件是 |\theta|\le 1/4 。這與上述結果一致，因為在 \lambda=\pm1 （對應於 \theta=0,1/2 ）的情況下，相位是確定性地被取回的，而其他相位越接近這兩個值，其取回的準確度就越高。

參見

秀爾演算法
量子計數演算法
宇稱測量

參考資料