Top 8

量子回路で色々な内積計算【量子コンピューター Advent Calendar 2021 15 日目】

Dec. 12, 2021, 12:19 p.m. edited Dec. 14, 2021, 10:50 a.m.

#量子情報 #量子力学

$$ \def\bra#1{\mathinner{\left\langle{#1}\right|}} \def\ket#1{\mathinner{\left|{#1}\right\rangle}} \def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}} $$

量子コンピューター Advent Calendar 2021 15 日目の記事です。そして私はこれが Advent Calender 初参加です。

量子アルゴリズムを構築するにあたって内積計算をする機会がある場合がありますが、その際に使えるであろう手法を 3 つ紹介します。その前に準備として内積計算の対象となる 2 つの $n$ ビットで表される状態を $\ket{\psi}=U_\psi \ket{0^n}$, $\ket{\phi}=U_\phi\ket{0^n}$ とします。

SWAP test
逆回路
SWITCH test
最後に全然関係ない話

SWAP test

最もポピュラーな手法です。 [H. Buhrman et al., 2001] にて提案されました。これは 3 者間の一方向通信である SMP プロトコルにおいて通信計算量を指数的に削減するのに利用されました（わかりやすい日本語解説記事）。

内容としては、まず

$$\ket{0}\ket{\psi}\ket{\phi}$$

という状態を用意します。この最初のビットにアダマール $H$ を作用させます。

$$\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\ket{\psi}\ket{\phi}$$

そして最初のビットを制御ビットとして $CSWAP$ を作用させます。

$$\frac{1}{\sqrt{2}}(\ket{0}\ket{\psi}\ket{\phi}+\ket{1}\ket{\phi}\ket{\psi})$$

それから再び最初のビットに $H$ を作用させます。

$$\frac{1}{2}\{\ket{0}(\ket{\psi}\ket{\phi}+\ket{\phi}\ket{\psi})+\ket{1}(\ket{\psi}\ket{\phi}-\ket{\phi}\ket{\psi})\}$$

ここで最初のビットを測定すると、その値が $0$ となる確率は

$$ \begin{align} \Pr(0)&=\frac{1}{4}\|\ket{\psi}\ket{\phi}+\ket{\phi}\ket{\psi}\|^2\\ &=\frac{1}{4}(\braket{\psi}{\psi}\braket{\phi}{\phi}+\braket{\psi}{\phi}\braket{\phi}{\psi}+\braket{\phi}{\psi}\braket{\psi}{\phi}+\braket{\phi}{\phi}\braket{\psi}{\psi})\\ &=\frac{1}{4}(2+2|\braket{\psi}{\phi}|^2)\\ &=\frac{1}{2}(1+|\braket{\psi}{\phi}|^2) \end{align} $$

であることから、内積は

$$|\braket{\psi}{\phi}|^2=2\Pr(0)-1$$

と求まります。

量子回路で表すと以下のようになります。

逆回路

おそらく SWAP test の次に有名な手法だと思います。手法の名称が不明なので本稿では「逆回路」と呼びます。初出かはわかりませんが [V. Havlicek et al., 2018] で用いられています。

内容としてはその名の通り逆回路を組むようになっており、まず

$$U_\phi\ket{0^n}=\ket{\phi}$$

を作ります。そこに $U_\psi$ の逆回路 $U_\psi^\dagger$ を作用させます。

$$U_\psi^\dagger U_\phi\ket{0^n}$$

そして、この $n$ ビットを測定して $0^n$ を得る確率は

$$ \begin{align} \Pr(0^n)&=\left|\left\langle0^n\middle|U_\psi^\dagger U_\phi\middle|0^n\right\rangle\right|^2\\ &=|\braket{\psi}{\phi}|^2 \end{align} $$

となり、ちょうど欲しい内積となっています。

量子回路としては以下のようになります。

SWITCH test

最後に紹介するのが、おそらく多くの方は初見であろう SWITCH test です。これは [P. Chamorro-Posada et al., 2017] で提案されたものです（ただし、おそらく [Z. Zhao et al., 2015] p.3 左下で既に原型があったはず。~~なお、 PhysRevA 版を見ると・・・~~）。この内積の大きな特徴として、得られる内積は実部（または虚部）のみ、かつ符号つきということが挙げられます。

内容としては、まず

$$\ket{0}\ket{0^n}$$

という状態を用意します。最初のビットに $H$ を作用させます。

$$\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\ket{0^n}$$

それから最初のビットに $X$ (つまり $NOT$) を作用させたうえで最初のビットを制御ビットとして $U_\psi$ を作用させ、そして再び最初のビットに $X$ を作用させます（つまり量子回路での表記における白丸のこと）。

$$\frac{1}{\sqrt{2}}(\ket{0}\ket{\psi}+\ket{1}\ket{0^n})$$

次に普通に最初のビットを制御ビットとして $U_\phi$ を作用させます。

$$\frac{1}{\sqrt{2}}(\ket{0}\ket{\psi}+\ket{1}\ket{\phi})\tag{1}$$

そして最初のビットに $H$ を再び作用させます。

$$\frac{1}{2}\{\ket{0}(\ket{\psi}+\ket{\phi})+\ket{1}(\ket{\psi}-\ket{\phi})\}$$

ここで最初のビットを測定して $0$ を得る確率は

$$ \begin{align} \Pr(0)&=\frac{1}{4}\|\ket{\psi}+\ket{\phi}\|^2\\ &=\frac{1}{4}(\braket{\psi}{\psi}+\braket{\psi}{\phi}+\braket{\phi}{\psi}+\braket{\phi}{\phi})\\ &=\frac{1}{4}(2+2\mathrm{Re}\braket{\psi}{\phi})\\ &=\frac{1}{2}(1+\mathrm{Re}\braket{\psi}{\phi}) \end{align} $$

となります。ここで、 3 番目の等号では

$$ \begin{align} \braket{\psi}{\phi}+\braket{\phi}{\psi}=2\mathrm{Re}\braket{\psi}{\phi} \end{align} $$

証明

$\ket{\psi}\equiv[a_1+ib_1,\dots,a_N+ib_N]$, $\ket{\phi}\equiv[c_1+id_1,\dots,c_N+id_N]$ ($N\in\mathbb{N}$, $a_1,\dots,a_N, b_1,\dots,b_N, c_1,\dots,c_N, d_1,\dots,d_N\in\mathbb{R}$) とおく。このとき、 $$ \begin{align} \braket{\psi}{\phi}&=\sum_{k=1}^N(a_k-ib_k)(c_k+id_k)=\sum_{k=1}^N\{(a_kc_k+b_kd_k)+i(a_kd_k-b_kc_k)\}\\\ \braket{\phi}{\psi}&=\sum_{k=1}^N(c_k-id_k)(a_k+ib_k)=\sum_{k=1}^N\{(a_kc_k+b_kd_k)-i(a_kd_k-b_kc_k)\} \end{align} $$ したがって、 $$ \begin{align} \braket{\psi}{\phi}+\braket{\phi}{\psi}&=2\mathrm{Re}\braket{\psi}{\phi}\\\ \braket{\psi}{\phi}-\braket{\phi}{\psi}&=2i\mathrm{Im}\braket{\psi}{\phi} \end{align} $$

■

を用いました。ゆえに、内積の実部は

$$\mathrm{Re}\braket{\psi}{\phi}=2\Pr(0)-1$$

となります。なお、虚部が欲しい場合は [L. Zhao et al., 2019] p.6 Appendix B で紹介されているように式(1)の最初のビットに位相回転ゲートを作用させてから $H$ と測定をすれば良いです。

内積の虚部を得る

式(1)の最初のビットに位相回転ゲート $$P\left(\frac{3}{2}\pi\right)=\begin{bmatrix} 1 & 0\\\ 0 & e^{i\frac{3}{2}\pi} \end{bmatrix}$$ を作用させます。 $$\frac{1}{\sqrt{2}}(\ket{0}\ket{\psi}-i\ket{1}\ket{\phi})$$ $H$ を最初のビットに作用させます。 $$\frac{1}{2}\{\ket{0}(\ket{\psi}-i\ket{\phi})+\ket{1}(\ket{\psi}+i\ket{\phi})\}$$ そして最初のビットを測定して $0$ が得られる確率は $$ \begin{align} \Pr(0)&=\frac{1}{4}\|\ket{\psi}-i\ket{\phi}\|^2\\\ &=\frac{1}{4}(\braket{\psi}{\psi}-i\braket{\psi}{\phi}+i\braket{\phi}{\psi}+\braket{\phi}{\phi})\\\ &=\frac{1}{4}\{2-i(\braket{\psi}{\phi}-\braket{\phi}{\psi})\}\\\ &=\frac{1}{4}(2+2\mathrm{Im}\braket{\psi}{\phi})\\\ &=\frac{1}{2}(1+\mathrm{Im}\braket{\psi}{\phi}) \end{align} $$ となりますので、求める内積の虚部は $$\mathrm{Im}\braket{\psi}{\phi}=2\Pr(0)-1$$ となります。

内積の実部を求める量子回路は以下のようになります。