最近Project涉及到variational hybrid quantum-classical algorithms中的技術，所以就簡單講講最近看的關於hybrid的演算法里gradient計算的東西。主要圍繞Maria Schuld and Nathan Killoran組提的方法。因為該演算法已經在PennyLane中有實現，也方便大家自己上手試試。本文基於去年末Nathan Killoran組在Evaluating analytic gradients on quantum hardware中提的方法（主要是用於hybrid的結構）。

Evaluating analytic gradients on quantum hardware?

arxiv.org

1. Variational Hybrid Quantum-Classical algorithm

variational hybrid quantum-classical algorithm，VHQC。顧名思義，就是量子與經典相結合的演算法。演算法線路部分是量子的，優化部分是經典的。如QAOA，如圖所示：

【2】QAOA框架

這種VHQC最早由Farhi在14年提出【1】，也就是QAOA（Quantum Approximate Optimization Algorithm）。該框架由帶參數的quantum circuit，及classical的optimizer組成。circuit中採用兩種帶參數的quantum gate：

  1. 帶參數 color{blue}{eta} 的單比特gate，即 X_color{blue}eta

2. 帶參數 color{red}{gamma} 的多比特gate，即 e^{-icolor{red}{gamma}H_c}

定義Objective function，然後正向evaluate的結果送入classical的optimizer，例如SGD（stochastic gradient descent）。再根據輸出，反向改變quantum circuit的參數。同classical演算法一樣，迭代多輪後，即可求得Objective function的最優值及對應的circuit參數color{blue}{eta}及color{red}{gamma}。

整個演算法的思想很簡單，量子和經典兩邊都出力，各取所需。該演算法中的核心部分為：如何計算每個circuit參數的gradient，後文將介紹一種計算該gradient的方法。

【1】Farhi E, Goldstone J, Gutmann S. A quantum approximate optimization algorithm[J]. arXiv preprint arXiv:1411.4028, 2014.

【2】Zhou L, Wang S T, Choi S, et al. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices[J]. arXiv preprint arXiv:1812.01041, 2018.

2. Differentiation

首先回顧下求偏導的幾種方法：

  1. 數值近似求解

[ abla gleft( x ight) approx gleft( {x + Delta x/2} ight) - gleft( {x - Delta x/2} ight)/Delta x\]

這種方法你只需將 g(x) 當做黑盒，兩次query即可得到近似結果。但是該種方法存在精度問題，實際的數值實驗上誤差較大，特別是epoch動則上千的時候，誤差累計很大。

2. 自動求導

由於DL的蓬勃發展，autograd實現了複雜函數的求導。其基本原理即將整個複雜函數分解成一環套一環的subfunction，通過鏈式法則將各subfunction的偏導累乘起來，實現整個複雜函數的偏導。自動求導適用於已知每個subfunction偏導的情況。PennyLane中將autograd拓展到了quantum circuit上，其將quantum circuit設計成如同tensorflow的計算節點（他們能這麼做的前提是以quantum circuit以expectation value作為輸出）。這樣整個計算圖就由classical node和quantum node作為最基本的構件，來進行計算。

3. 符號求導/解析式求偏導

通過符號運算，直接求得所需偏導的解析解。這種方法也就是Killoran他們基於以expectation value作為輸出的結構，提出的解析方法。因為為解析解的緣故，所以相較於數值近似，該種方法具有更高的精度。

3. Parameter Shift Rule

Parameter Shift Rule即Schuld,Killoran文章所提的解析方法。該方法實際將gradient的計算轉化為兩個shift了參數的quantum circuit來完成。如圖所示：

整個quantum circuit的結構是：以 [left| 0 ight angle ] 作為輸入，經過多個單比特及多比特的帶參量子門，最後對每個量子比特進行測量，以關於Observable（例如,Pauli運算元）的expectation value作為輸出，即

[fleft( heta ight) = leftlangle {widehat B} ight angle = leftlangle 0 ight|{U^dag }left( heta ight)widehat BUleft( heta ight)left| 0 ight angle ag{1}\]

其中 heta 為variational circuit的參數， [widehat B] 為Observable。

那麼對 fleft( heta ight) ,求其中任意的某個帶參量子門的參數 muin heta 的偏導即為：

[{partial _mu }f = leftlangle 0 ight|{U^dag }widehat B{partial _mu }Uleft| 0 ight angle + leftlangle 0 ight|{partial _mu }{U^dag }widehat BUleft| 0 ight angle \]

因為 [Uleft( heta ight) = VGleft( mu ight)W] ，則有

[{partial _mu }f = color{blue}{leftlangle 0 ight|{W^dag }}{G^dag }color{green}{{V^dag }widehat BV}left( {{partial _mu }G} ight)color{blue}{Wleft| 0 ight angle} + h.c.\]

令 [left| varphi ight angle = Wleft| 0 ight angle ] ， [widehat Q = {V^dag }hat BV] ，則

[{partial _mu }f = leftlangle varphi ight|{G^dag }widehat Qleft( {{partial _mu }G} ight)left| varphi ight angle + h.c. ag{2}\]

CASE 1. 一般的單比特門 e^{-imu H}

對於有任意Hermitian H 生成的gate G(mu)=e^{-imu H}。其對 mu 的偏導為：

[{partial _mu }G = - iH{e^{ - imu H}} ag{3}\]

則

[{partial _mu }f = leftlangle varphi ight|{G^dag }widehat Qleft( { - iH} ight)Gleft| varphi ight angle + h.c. ag{4}\]

令 [left| varphi ight angle = Gleft| varphi ight angle ] ,將 G 收縮進 left| varphi ight angle ，則有

[{partial _mu }f = leftlangle {varphi } ight|widehat Qleft( { - iH} ight)left| {varphi } ight angle + h.c. ag{5}\]

對於任意operator A,B ,有

[egin{array}{l} leftlangle varphi ight|{A^dag }widehat QBleft| varphi ight angle + h.c.\ = frac{1}{2}left( {leftlangle varphi ight|{{left( {A + B} ight)}^dag }widehat Qleft( {A + B} ight)left| varphi ight angle - leftlangle varphi ight|{{left( {A - B} ight)}^dag }widehat Qleft( {A - B} ight)left| varphi ight angle } ight) end{array}]

那麼由此，式5則可改寫成

[{partial _mu }f = frac{r}{2}left( egin{array}{l} leftlangle {varphi } ight|left( {mathbb{I} - i{r^{ - 1}}H} ight)widehat Qleft( {mathbb{I} - i{r^{ - 1}}H} ight)left| {varphi } ight angle \ - leftlangle {varphi } ight|left( {mathbb{I} + i{r^{ - 1}}H} ight)widehat Qleft( {mathbb{I} + i{r^{ - 1}}H} ight)left| {varphi } ight angle end{array} ight) ag{6}\]

其中 pm r 為 H 的兩個eigenvalue。

這裡為什麼會扯到eigenvalue，感覺比較突然。其實是為了讓 [ {mathbb{I} + i{r^{ - 1}}H} \]和 G 掛上鉤。這樣，我們計算偏導的時候直接可通過shift參數的兩個variational quantum circuit來實現。

如果生成 G 的Hermitian H 有兩個不同的eigenvalue pm r，那麼我們有：

G(frac{pi}{4r})=frac{1}{sqrt{2}}(mathbb{I}-ir^{-1}H) ag{7}

由於 G(a+b)=G(a)G(b) ,令 s=frac{pi}{4r} ,則

[egin{array}{l} {partial _mu }f = rleft( egin{array}{l} leftlangle varphi ight|{G^dag }left( {mu + s} ight)widehat QGleft( {mu + s} ight)left| varphi ight angle \ - leftlangle varphi ight|{G^dag }left( {mu - s} ight)widehat QGleft( {mu - s} ight)left| varphi ight angle end{array} ight)\ color{red}{ {partial _mu }f= rleft[ {fleft( {mu + s} ight) - fleft( {mu - s} ight)} ight]} end{array} ag{8}\]

CASE 2. 一般多比特門

對於任意多比特量子門，對其參數的偏導結果為complex square matrix。那麼自然，我們可以將其分解為多個unitary matrix的線性組合，如：

[{partial _mu }G = sumlimits_{k = 1}^K {{alpha _k}{A_k}} ag{9}\]

那麼

[{partial _mu }f = sumlimits_{k = 1}^K {{alpha _k}} left( {leftlangle varphi ight|{G^dag }widehat Q{A_k}left| varphi ight angle + h.c.} ight)\]

[ = sumlimits_{k = 1}^K {{alpha _k}} left( {leftlangle varphi ight|{{left( {G + {A_k}} ight)}^dag }widehat Qleft( {G + {A_k}} ight)left| varphi ight angle - leftlangle varphi ight|{{left( {G - {A_k}} ight)}^dag }widehat Qleft( {G - {A_k}} ight)left| varphi ight angle } ight)\]

接下來介紹如何實現 [{leftlangle varphi ight|{{left( {G + {A_k}} ight)}^dag }widehat Qleft( {G + {A_k}} ight)left| varphi ight angle }] 和 [{leftlangle varphi ight|{{left( {G - {A_k}} ight)}^dag }widehat Qleft( {G - {A_k}} ight)left| varphi ight angle }] 。

通過觀察，我們發現可以利用coherent linear combinations of unitaries的技術來實現【1】。通過以下電路即可是完成：

【2】coherent linear combinations of unitaries

以單個 A_k 為例，首先Hardmard作用於ancilla比特 [left| 0 ight angle ] ，之後經過 G,A_k ,可得

[frac{1}{{sqrt 2 }}left( {left| 0 ight angle Gleft| varphi ight angle + left| 1 ight angle {A_k}left| varphi ight angle } ight)\]

在經過Hardmard門之後，可得

[frac{1}{{sqrt 2 }}left( {left| 0 ight angle left( {G + {A_k}} ight)left| varphi ight angle + left| 1 ight angle left( {G - {A_k}} ight)left| varphi ight angle } ight)\]

不難看出，如果我們對ancilla比特進行測量，則會以以下概率得到態 [frac{1}{sqrt{2p_0}}{left( {G + {A_k}} ight)left| varphi ight angle }] , [frac{1}{sqrt{2p_1}}{left( {G - {A_k}} ight)left| varphi ight angle }]

[left{ {egin{array}{*{20}{c}} {{p_0} = frac{1}{4}leftlangle varphi ight|{{left( {G + {A_k}} ight)}^dag }left( {G + {A_k}} ight)left| varphi ight angle }\ {{p_1} = frac{1}{4}leftlangle varphi ight|{{left( {G - {A_k}} ight)}^dag }left( {G - {A_k}} ight)left| varphi ight angle } end{array}} ight.\]

若對ancilla比特計算 widehat Q 的expectation value，則可得

[{E_0} = frac{1}{{4{p_0}}}leftlangle varphi ight|{left( {G + {A_k}} ight)^dag }widehat Qleft( {G + {A_k}} ight)left| varphi ight angle \]

[{E_1} = frac{1}{{4{p_1}}}leftlangle varphi ight|{left( {G - {A_k}} ight)^dag }widehat Qleft( {G - {A_k}} ight)left| varphi ight angle \]

若K=1時，不難看出，

[{leftlangle varphi ight|{G^dag }widehat Q{A_k}left| varphi ight angle + h.c.=2(p_0E_0-p_1E_1)}\]

註：

可以看出該方法首先需要知道 A_k ,並且需要計算 2K 個expectation value。對於只作用於比特數較少的門（較小系統），該方法 A_k 是容易找到的，且 K 的取值可直接選為2（ [{partial _mu }G = frac{alpha }{2}left( {left( {{A_1} + A_1^dag } ight) + ileft( {{A_2} + A_2^dag } ight)} ight)] ），方便計算。

綜上，該種解析式的方法計算gradient，比以往通過numerical differentiation的方法擁有更高的精度，而且整個計算過程由variational quantum circuit實現。

【1】Andrew M Childs and Nathan Wiebe, Hamiltonian simulation using linear combinations of unitary operations," Quantum Information and Computation 12,0901{0924 (2012).

【2】Schuld M, Bergholm V, Gogolin C, et al. Evaluating analytic gradients on quantum hardware[J]. arXiv preprint arXiv:1811.11184, 2018.

附錄

相關公式推導

式（3）

[{partial _mu }G = - iH{e^{ - imu H}}\]

證明：

[{e^{ - imu H}} = sumlimits_{k = 0}^infty {{{left( mu ight)}^k}frac{{{{left( { - i} ight)}^k}{H^k}}}{{k!}}} \]

因為

[ (- iH){e^{ - imu H}} = sumlimits_{k = 0}^infty {{{left( mu ight)}^k}frac{{{{left( { - i} ight)}^{k + 1}}{H^{k + 1}}}}{{k!}}} \]

及

[egin{array}{l} {partial _mu }{e^{ - imu H}} = sumlimits_{k = 0}^infty {{partial _mu }left( {{mu ^k}} ight)frac{{{{left( { - i} ight)}^k}{H^k}}}{{k!}}} \ = sumlimits_{k = 0}^infty {k{mu ^{k - 1}}frac{{{{left( { - i} ight)}^k}{H^k}}}{{k!}}} = sumlimits_{k = 1}^infty {{mu ^{k-1}}frac{{{{left( { - i} ight)}^k}{H^k}}}{{k - 1!}}} end{array}\]

所以

[{partial _mu }G = - iH{e^{ - imu H}}\]

式7

如果 H 有兩個不同的eigenvalue pm r ,則

[{H^dag }Hleft( {left| {{varphi ^ - }} ight angle leftlangle {{varphi ^ - }} ight| + left| {{varphi ^ + }} ight angle leftlangle {{varphi ^ + }} ight|} ight) = {left( { - r} ight)^2}left| {{varphi ^ - }} ight angle leftlangle {{varphi ^ - }} ight| + {left( r ight)^2}left| {{varphi ^ + }} ight angle leftlangle {{varphi ^ + }} ight|\]

[Rightarrow{H^2} = {left( r ight)^2}I\]

因為

[{e^{ - imu H}} = sumlimits_{k = 0}^infty {{{left( mu ight)}^k}frac{{{{left( { - i} ight)}^k}{H^k}}}{{k!}}} \]

[ = sumlimits_{k = 0}^infty {frac{{{{left( { - imu } ight)}^{2k}}{H^{2k}}}}{{left( {2k} ight)!}}} + sumlimits_{k = 0}^infty {frac{{{{left( { - imu } ight)}^{2k + 1}}{H^{2k + 1}}}}{{left( {2k + 1} ight)!}}} \]

[ = mathbb{I}sumlimits_{k = 0}^infty {frac{{{{left( { - 1} ight)}^k}{{left( {rmu } ight)}^{2k}}}}{{left( {2k} ight)!}}} - frac{i}{r}Hsumlimits_{k = 0}^infty {frac{{{{left( { - 1} ight)}^k}{{left( {rmu } ight)}^{2k + 1}}}}{{left( {2k + 1} ight)!}}} \]

[ = cos left( {rmu } ight)mathbb{I} - frac{i}{r}Hsin left( {rmu } ight)\]

若 mu=frac{pi}{4r} ，則

G(frac{pi}{4r})=frac{1}{sqrt{2}}(mathbb{I}-ir^{-1}H)


推薦閱讀：
相关文章