量子振幅推定、量子振幅増幅

はじめに

量子コンピュータで目的の精度であるシミュレーションをしたい場合など、その結果としての振幅を精度よく取得するための方法として量子振幅推定があります。

用途

用途は金融や実問題などの社会問題を効率的に解くことができそうです。この量子振幅推定や量子振幅増幅の発展形としてグローバーのアルゴリズムがあります。量子振幅推定、量子振幅増幅はグローバーのアルゴリズムの一般化と言えるでしょう。

参考

MUFG、みずほ銀行（順不同）の方々が論文を出しています。
https://arxiv.org/abs/1904.10246

日本語解説もありました。
「量子コンピュータを用いた高速数値積分」

Quantum Amplitude Amplification and Estimation
https://arxiv.org/abs/quant-ph/0005055

量子振幅増幅

初期状態の振幅を増幅させることができます。ある関数を設定して、所望の状態を導き出します。

参考：

初期状態

初期状態は任意の量子状態と設定しますが、0状態と1状態の重ね合わせで複素数として、

\mid \psi \rangle = cos \theta \mid \psi_0 \rangle + e^{i\phi} sin \theta \mid \psi_1 \rangle

マーキング

マーキングは $\mid \psi_1 \rangle$ のみにマイナスをつけます。

U_{marking}\mid \psi_0 \rangle = \mid \psi_0 \rangle\\ U_{marking}\mid \psi_1 \rangle = -\mid \psi_1 \rangle

次のようにした時、

\mid \psi \rangle = \begin{bmatrix}cos \theta \\ e^{i\phi} sin \theta \end{bmatrix}

マーキングの回路は、

U_{marking} = \begin{bmatrix} 1&0 \\ 0&-1 \end{bmatrix}

となれば、

U_{marking} \mid \psi \rangle = \begin{bmatrix} 1&0 \\ 0&-1 \end{bmatrix} \begin{bmatrix}cos \theta \\ e^{i\phi} sin \theta \end{bmatrix} = \begin{bmatrix}cos \theta \\ - e^{i\phi} sin \theta \end{bmatrix}

となるようです。

振幅増幅

マーキングした指定の量子状態の振幅を増幅します。

U_{aa} = 2\mid \psi \rangle \langle \psi \mid - I

とすれば、指定の量子状態の周りでの反転になるので、

U_{aa} = \begin{bmatrix} 2 \alpha^2 -1 & -2 \alpha \beta e^{-i\phi}\\ -2 \alpha \beta e^{i \phi} & 2 \beta^2 - 1 \end{bmatrix}

となるようです。

複数回の繰り返し

これを複数回繰り返すので、

(U_{aa}U_{marking})^n = (\begin{bmatrix} 2 \alpha^2 -1 & -2 \alpha \beta e^{-i\phi}\\ -2 \alpha \beta e^{i \phi} & 2 \beta^2 - 1 \end{bmatrix} \begin{bmatrix} 1&0 \\ 0&-1 \end{bmatrix})^n \\= \begin{bmatrix} 2 \alpha^2 -1 & -2 \alpha \beta e^{-i\phi}\\ 2 \alpha \beta e^{i \phi} & 1- 2 \beta^2 \end{bmatrix}^n

固有値固有ベクトルをおいて、

量子状態に対して、n回操作した結果は、

cos(2n+1)\theta \mid \psi_0 \rangle + e^{i\phi}sin(2n+1)\theta \mid \psi_1 \rangle

こうなりました。所望の回数操作をした後に、振幅がこのようになりました。シミュレーションで使ってもよし、検索で使ってもよし、組合せ最適化で使っても良さそうです。

具体的な利用例としてグローバーのアルゴリズムを見てみます。

グローバーのアルゴリズム

グローバーのアルゴリズムは上記の振幅増幅回路を使って、所望の量子状態の振幅を最大にするように操作をします。

初期状態を $\mid + \rangle^{\otimes N}$ とすると、振幅は量子ビット数Nに応じて、 $\frac{1}{\sqrt{2^N}}$ となり、等分されます。初期の $sin\theta$ がわかるので、それから試行回数のnがわかります。

最終的な振幅はsinの値を1に持っていきたいので、角度 $(2n+1)\theta = \pi/2$ を目指します。

これがグローバーのアルゴリズムで、量子振幅増幅回路の具体例になります。