Quantum Algorithm(2)：量子相位估計

該篇文章將詳細展開講述上篇Quantum Principle Component Analysis所提到的重要框架Quantum Phase Estimation,QPE。該框架被廣泛應用於量子演算法中，例如QPCA，HHL，QSVD等。以下是主要參考文獻：

John Watrous的課件

https://cs.uwaterloo.ca/~watrous/LectureNotes/CPSC519.Winter2006/08.pdf?

cs.uwaterloo.ca

https://cs.uwaterloo.ca/~watrous/LectureNotes/CPSC519.Winter2006/09.pdf?

cs.uwaterloo.ca

Dieter van Melkebeek的課件

http://pages.cs.wisc.edu/~dieter/Courses/2010f-CS880/Scribes/09/lecture09.pdf?

pages.cs.wisc.edu

http://pages.cs.wisc.edu/~dieter/Courses/2010f-CS880/Scribes/10/lecture10.pdf?

pages.cs.wisc.edu

Quantum Phase Estimation量子相位估計，顧名思義，通過量子演算法得到給定輸入的相位信息，估計即是這個相位結果的精度和我們演算法的設置相關。Quantum Phase Estimation求解的本質問題是矩陣的特徵值估計，即給定矩陣求解出其特徵值（在Dieter van Melkebeek的課件中，稱該問題為eigenvalue estimation【1】）。

問題描述：

輸入：已知某作用於個量子比特的量子電路（其對應於酉操作 $[U in {C^{N imes N}},N = {2^n}]$ ）及量子態（對應於的特徵向量）：

$[Uleft| u ight angle = {e^{2pi i heta }}left| u ight angle \ ag{1}]$

輸出：相位的估計值

由於為酉矩陣，故有
1. 其特徵向量具有完備性及正交性即 $[left{ {left| {{u _i}} ight angle } ight}_{i = 1}^N ；leftlangle {{u _i}} ight.left| {{u _j}} ight angle = 0, i e j, i,j=1,...,N\]$ 2. 其所有特徵值的模均為1，故特徵值均可表示為 $[left{ {{e^{2pi i{ heta _j}}}} ight}_{j = 1}^N，{ heta _j} in left[ {0,1} ight)\]$

在John Watrous的課件中，他的推導方法簡單明了，推薦先看。本文是將其展開來講。

下圖為整個QPE的演算法框架圖

第一部分

該部分的輸入有兩個，一個為 $[{left| 0 ight angle ^{ otimes n}}]$ 的量子寄存器1和的量子寄存器2。該部分目的為準備疊加態，為之後存儲相位做準備。其思想即把分解成類似二進位的表示，每qubit負責其中一位。最後讀取寄存器1得到的二進位串還原出來的即為 。

$[left| {{varphi _1}} ight angle = left( {{H^{ otimes n}} otimes I} ight){left| 0 ight angle ^{ otimes n}}left| u ight angle = frac{1}{{sqrt {{2^n}} }}sumlimits_{{x_0}{x_1}...{x_{n-1}} in {{left{ {0,1} ight}}^n}} {left| {{x_0}{x_1}...{x_{n-1}}} ight angle } left| u ight angle \ ag{2}]$

其中 $x_{i}in{{0,1}}$ 。

第二部分

通過對量子寄存器2進行個控制 $U^{j}，j=2^{0},...,2^{n-1}$ 的操作，實現將相位 $[{{e^{2pi i{ heta _j}}}}]$ 分別添加到概率幅上。如圖所示。其中 $x_{i}in{0,1}$

因為有分別添加到概率幅上。如圖所示

$[{U^{{2^j}}}left| u ight angle = {e^{2pi i heta cdot {2^j}}}left| u ight angle \ ag{3}]$

由於使用受控門，所以將 $e^{2pi i heta cdot {2^j}}$ 添加到了每個量子比特為時的概率幅上。

同時，且可以通過二進位進行展開，得：

$[egin{array}{l} heta = frac{j}{{{2^n}}} = 0.{ heta _0}{ heta _1}...{ heta _{n - 1}} = frac{1}{2}{ heta _0} + frac{1}{{{2^2}}}{ heta _1} + ... + frac{1}{{{2^n}}}{ heta _{n - 1}},j = 1,...,{2^{n - 1}}\ end{array}\ ag{4}]$

其中 $[{ heta _i} in left{ {0,1} ight}]$ 。這樣重複使用受控門的好處是，我們的量子態可以表示成

$[{U^{{2^j}}}left| u ight angle = {e^{2pi ileft( {0.{ heta _0}{ heta _1}...{ heta _{n-1}}} ight) cdot {2^j}}}left| u ight angle = {e^{2pi i0.{ heta _j}{ heta _{j + 1}}...{ heta _{n-1}}}}left| u ight angle \ ag{5}]$

這時我們的整個電路的輸出的量子態 $[left| {{varphi _2}} ight angle ]$ 為

$[left| {{varphi _2}} ight angle = frac{1}{{sqrt {{2^n}} }}underbrace {left( {left| 0 ight angle + {e^{2pi i0.{ heta _{n - 1}}}}left| 1 ight angle } ight)}_{left| {{x_0}} ight angle }underbrace {left( {left| 0 ight angle + {e^{2pi i0.{ heta _{n - 2}}{ heta _{n - 1}}}}left| 1 ight angle } ight)}_{left| {{x_1}} ight angle }...underbrace {left( {left| 0 ight angle + {e^{2pi i0.{ heta _0}...{ heta _{n - 1}}}}left| 1 ight angle } ight)}_{left| {{x_{n - 1}}} ight angle} left| u ight angle\ ag{6}]$

令 $[{phi _i} = 0.{ heta _{n - i + 1}}..{ heta _{n - 1}}]$ ，則有

$[left| {{varphi _2}} ight angle = frac{1}{{sqrt {{2^n}} }}sumlimits_{j = 1,{x_0},...,{x_{n - 1}} in {{left{ {0,1} ight}}^n}}^n {{e^{2pi ileftlangle {x,{phi _j}} ight angle }}left| {{x_0},...,{x_{n - 1}}} ight angle } left| u ight angle\]$

第三部分

考慮最簡單的情況。

當時，如以下circuit

因為 $[{e^{2pi i0.{ heta _{n - 1}}}} = {left( {{e^{pi i}}} ight)^{{ heta _{n - 1}}}} = {left( { - 1} ight)^{{ heta _{n - 1}}}}]$ ，則有

$[Uleft( {H otimes I} ight)left| {0,u} ight angle = frac{1}{{sqrt 2 }}left( {left| 0 ight angle + {{left( { - 1} ight)}^{{ heta _{n - 1}}}}left| 1 ight angle } ight)left| u ight angle = Hleft| {{ heta _{n - 1}}} ight angle left| u ight angle \ ag{7}]$

這裡用到了phase kickback這個trick，也就是將在單量子比特概率幅上的信息，存儲到量子態上。這樣我們只需要最後對第一個量子比特作用Hardmard門即可將 $heta_{n-1}$ 存儲到量子態上。

當時，有

同理，因為

$[{e^{2pi i0.{ heta _{n - 2}}{ heta _{n - 1}}}} = {e^{2pi ileft( {frac{1}{2}{ heta _{n - 2}} + frac{1}{{{2^2}}}{ heta _{n - 1}}} ight)}} = {e^{pi i{ heta _{n - 2}}}}{e^{1/2pi i{ heta _{n - 1}}}} = {left( { - 1} ight)^{{ heta _{n - 2}}}}{e^{1/2pi i{ heta _{n - 1}}}}\]$

$[egin{array}{l} {U^2}Uleft( {H otimes H otimes I} ight)left| {0,0,u} ight angle = frac{1}{{sqrt 2 }}left( {left| 0 ight angle + {{left( { - 1} ight)}^{{ heta _{n - 1}}}}left| 1 ight angle } ight)left( {left| 0 ight angle + {{left( { - 1} ight)}^{{ heta _{n - 2}}}}{e^{1/2pi i{ heta _{n - 1}}}}left| 1 ight angle } ight)left| u ight angle \ = Hleft| {{ heta _{n - 1}}} ight angle left( {left| 0 ight angle + {{left( { - 1} ight)}^{{ heta _{n - 2}}}}{e^{1/2pi i{ heta _{n - 1}}}}left| 1 ight angle } ight)left| u ight angle end{array}\ ag{8}]$

很容易看出，為了要提取出 $heta_{n-2}$ 只需要先作用控制旋轉門在作用Hardmard門即可。

其中旋轉門為

$[R = left[ {egin{array}{*{20}{c}} 1&0\ 0&{{e^{2pi i/4}}} end{array}} ight]\ ag{9}]$

可見，我們通過旋轉門抵消掉 $[{e^{1/2pi i}}]$ ，使其最終成為 $[{{{left( { - 1} ight)}^{{ heta _{n - 1}}}}}]$

同理，我們一步一步的對整個寄存器1進行這種操作，即可將相位存儲到量子態上。

通過觀察，我們可以發現，這個操作其實就是對寄存器1進行了 $[QF{T^dag }]$ ，即

$[QF{T^dag }left| {{varphi _2}} ight angle = frac{1}{{{2^n}}}sumlimits_{x,y = 0}^{{2^n} - 1} {{e^{ - 2pi xy/{2^n}}}{e^{2pi ix heta }}left| y ight angle } \ ag{10}]$

【1】Dieter van Melkebeek， eigenvalue estimation http://pages.cs.wisc.edu/~dieter/Courses/2010f-CS880/Scribes/10/lecture10.pdf

證明：

公式（5）:

因為，則可將其用二進位展開為 $[ heta = 0.{ heta _0}{ heta _1}...{ heta _{n-1}} = frac{1}{2}{ heta _0} + frac{1}{{{2^2}}}{ heta _1} + ... + frac{1}{{{2^{n-2}}}}{ heta _{n-1}}]$

$[egin{array}{*{20}{l}} {0.{ heta _0}{ heta _1}...{ heta _{n - 1}} cdot {2^j}}\ { = left( {frac{1}{{{2^1}}}{ heta _0} + frac{1}{{{2^2}}}{ heta _1} + ... + frac{1}{{{2^{n - 2}}}}{ heta _{n - 1}}} ight) cdot {2^j}}\ { = left( {frac{1}{{{2^{1 - j}}}}{ heta _0} + frac{1}{{{2^{2 - j}}}}{ heta _1} + ... + frac{1}{{{2^{j - j}}}}{ heta _{j - 1}} + frac{1}{{{2^{j + 1 - j}}}}{ heta _j} + ... + frac{1}{{{2^{n - j}}}}{ heta _{n - 1}}} ight)}\ { = { heta _0}...{ heta _{j - 2}}{ heta _{j - 1}} + 0.{ heta _j}{ heta _{j + 1}}...{ heta _{n - 1}}} end{array}\]$

那麼，我們有

$[egin{array}{{l}} {{e^{2pi ileft( {{ heta _0}...{ heta _{j - 2}}{ heta _{j - 1}} + 0.{ heta _j}{ heta _{j + 1}}...{ heta _{n - 1}}} ight)po}} = {e^{2pi ileft( {0.{ heta _j}{ heta _{j + 1}}...{ heta _{n - 1}}} ight)}}}\ { = {e^{2pi ileft( {{ heta _0}...{ heta _{j - 2}}{ heta _{j - 1}}} ight)}} cdot {e^{2pi ileft( {0.{ heta _j}{ heta _{j + 1}}...{ heta _{n - 1}}} ight)}}} end{array}\]$

又因為 $[{e^{2pi ileft( {{ heta _{0}}{ heta _{1}}...{ heta _{n-1}}} ight)}} = 1]$ ，所以 $[{e^{2pi ileft( {{ heta _0}{ heta _1}...{ heta _{j - 1}} + 0.{ heta _j}{ heta _{j + 1}}...{ heta _{n-1}}} ight)}} = {e^{2pi ileft( {0.{ heta _j}{ heta _{j + 1}}...{ heta _{n-1}}} ight)}}]$ ，則