反復法による量子振幅推定

この記事の概要

Grinko et al. 2019, "Iterative Quantum Amplitude Estimation"を読んだので、その内容の理解を深めるためにアウトプットします。

この記事の概要
量子位相推定 (Quantum Phase Estimation, QPE)
量子振幅推定 (Quantum Amplitude Estimation, QAE)
反復法による量子振幅推定 (Iterative Quantum Amplitude Estimation, IQAE)
結言
参考文献
文責

量子位相推定 (Quantum Phase Estimation, QPE)

QunaSysさんのQuantum Native Dojo 2-4から、位相推定アルゴリズムは以下のような量子回路で記述されるのでした。

A quantum circuit of phase estimation — 位相推定の量子回路

ここで $H$ はアダマールゲート、 $U^{2^k}$ は測定用の各量子ビットを制御ビットとする制御ユニタリ演算、そして ${\rm QFT}^\dagger$ は量子フーリエ逆変換をそれぞれ表します。固有値の位相情報を測定用の補助量子ビットに移した後で、量子フーリエ逆変換で位相を取り出すことが位相推定アルゴリズムです。

量子振幅推定 (Quantum Amplitude Estimation, QAE)

量子振幅増幅

演算子 $\mathcal{A}$

まず求めたい $n$ 量子ビットの状態 $| \psi_1 \rangle_n$ と、それ以外の求めたくない量子状態 $| \psi_0 \rangle_n$ とに分ける演算子を $\mathcal{A}$ とします。状態を分けるために補助量子ビットを一つ用いて、演算子 $\mathcal{A}$ は $n+1$ 量子ビットに作用し

$\displaystyle{ \mathcal{A} | 0 \rangle_n \otimes | 0 \rangle = \sqrt{1-a} | \psi_0 \rangle_n \otimes | 0 \rangle + \sqrt{a} | \psi_1 \rangle_n \otimes | 1 \rangle }$

のように書かれます。ここで $a \in [0, 1$ ]は未知定数です。補助ビットの状態 $| 1 \rangle$ に求めたい状態 $| \psi_1 \rangle_n$ の情報を移すことができました。以降、便宜上のため $\sqrt{1-a} = \cos \theta, \sqrt{a} = \sin \theta$ と置きます。そして

$\displaystyle{ \Psi \rangle_{n+1} = \mathcal{A} | 0 \rangle_n \otimes | 0 \rangle }$

として、これを初期に用意します。

解に対する位相反転演算子 $U_w$

次に解である状態の位相を反転させる演算子

$\displaystyle{ U_w = (\bigotimes^n \mathbb{1}) \otimes Z }$

を作用させます。ここで $Z$ はパウリの $Z$ 演算子です。

$\displaystyle{ U_w | \Psi \rangle_{n+1} = \cos \theta　| \psi_0 \rangle_{n} \otimes (Z | 0 \rangle ) + \sin \theta | \psi_1 \rangle_{n} \otimes (Z | 1 \rangle) = \cos \theta　| \psi_0 \rangle_{n} \otimes | 0 \rangle - \sin \theta | \psi_1 \rangle_{n} \otimes | 1 \rangle }$

初期状態を対称軸にした反転操作演算子 $U_s$

$\displaystyle{ U_s = 2 | \Psi \rangle_{n+1} \langle \Psi |_{n+1} - \bigotimes^{n+1} \mathbb{1} }$

を作用させることで、初期状態 $| \Psi \rangle_{n+1}$ を対称軸とした反転操作を行います。

$\displaystyle{ \begin{align} U_s U_w | \Psi \rangle_{n+1} &= (2 | \Psi \rangle_{n+1} \langle \Psi |_{n+1} - \bigotimes^{n+1} \mathbb{1}) (\cos \theta　| \psi_0 \rangle_{n} \otimes | 0 \rangle - \sin \theta | \psi_1 \rangle_{n} \otimes | 1 \rangle ) \\ &= 2 \cos^2 \theta | \Psi \rangle_{n+1} - \cos \theta | \psi_0 \rangle_n \otimes | 0 \rangle -2 \sin^2 \theta | \Psi \rangle_{n+1} + \sin \theta | \psi_1 \rangle_n \otimes | 1 \rangle \\ &= (2 \cos^2 \theta \cos \theta - \cos \theta -2 \sin^2 \theta \cos \theta) | \psi_0 \rangle_n \otimes | 0 \rangle + (2\cos^2 \theta \sin \theta -2 \sin^2 \theta \sin \theta + \sin \theta) | \psi_1 \rangle_n \otimes | 0 \rangle \end{align} }$

ここで

$\displaystyle{ \cos (2\theta + \theta) = \cos 2\theta \cos \theta - \sin 2\theta \sin \theta = 2 \cos^2 \theta \cos \theta - \cos \theta - 2 \sin^2 \theta \cos \theta \\ \sin (2\theta + \theta) = \sin 2\theta \cos \theta - \cos 2\theta \sin \theta = 2 \cos^2 \theta \sin \theta + \sin \theta - 2 \sin^2 \theta \sin \theta }$

より

$\displaystyle{ U_s U_w | \Psi \rangle_{n+1} = \cos (2\theta + \theta) | \psi_0 \rangle_n \otimes | 0 \rangle + \sin (2\theta + \theta) | \psi_1 \rangle_n \otimes | 1\rangle }$

k回繰り返し

これを $U_w U_s$ を作用させることを $k$ 回繰り返すと

$\displaystyle{ (U_s U_w)^k | \Psi \rangle_{n+1} = \mathcal{Q}^k | \Psi \rangle_{n+1} = \cos ((2k+1)\theta )| \psi_0 \rangle_n \otimes | 0 \rangle + \sin ((2k+1)\theta) | \psi_1 \rangle_n \otimes | 1 \rangle }$

のようになります。

量子振幅推定とその量子回路

振幅増幅と同時に位相を補助量子ビットに移すことによって、振幅の推定を行います。これまでの議論を量子回路で表現すると以下のようになります。

A quantum circuit of amplitude estimation — 量子振幅推定の量子回路

上図のように最後に量子フーリエ逆変換により位相推定を行えば、振幅の情報を取り出すことができます。

量子振幅推定の問題点

ここで議論してきた量子振幅推定では増幅演算 $\mathcal{Q}$ の繰り返し回数を増やすごとに補助量子ビットを追加する必要があります。これではNISQデバイス上でこのアルゴリズムを実行するには限界があります。よって以下では、補助ビットの数が限られている場合に精度よく量子振幅推定を行うためのアルゴリズムIQAEをご紹介します。

反復法による量子振幅推定 (Iterative Quantum Amplitude Estimation, IQAE)

位相推定なしのQAE

これまでの議論から $n+1$ 番目の量子ビットを測定すると、状態 $|\psi_1 \rangle_n$ が得られる確率は

$\displaystyle{ \mathbb{P} [ | 1\rangle ] = \sin^2 ((2k+1) \theta) \tag{#} }$

となります。この $\sin^2$ の値と $k$ が分かれば、求めたい $\theta = \theta_a$ を得ることができます。

IQAEの考え方

最大となる $k$

三角関数の公式 $\sin^2 x = (1-\cos 2x)/2$ から、 $\sin^2 ((2k+1) \theta_a)$ を推定することは $\cos ((4k+2) \theta_a)$ を推定することと同義です。 $\theta_a$ の値を推定するために、以下のように考えましょう。
$[ \theta_l, \theta_u ] \subseteq [0, \pi/2]$ の間に求めたい $\theta = \theta_a \ (\sin \theta_a = \sqrt{a})$ があるとしましょう( $l$ : lower, $u$ : upperの意味)。今はcosの値を決定したいので、 $(4k+2) \theta_l, (4k+2) \theta_a, (4k+2) \theta_u$ は $[0, \pi$ ]または $[\pi, 2\pi$ ]の間にあると考えます。よって最大となる $k$ を $[ (4k+2) \theta_l, (4k+2) \theta_u ]_{\rm mod \ 2\pi}$ が $[0, \pi ]$ または $[ \pi, 2\pi ]$ の制限の元で探します。

IQAEアルゴリズム

以上の議論から、IQAEアルゴリズムは以下のようになります。

$k_i, {\rm up}_i$ をFindNextK( $k_{i-1}, \theta_l, \theta_u, {\rm up}_{i-1}$ )という関数で更新します。
$\theta_l = (4k_i+2) \theta_l, \theta_u = (4k_i+2) \theta_u$ として $\theta_l, \theta_u$ を更新します。
$\theta_u - \theta_l > 2\epsilon$ の間、1~2を繰り返します。
$[ a_l, a_u ] = [ \sin^2 \theta_l, \sin^2 \theta_u ]$ を計算し、値を返します。

最後に求まった $a_l, a_u$ から $\tilde{a} = (a_l + a_u)/2$ とすれば、精度 $|a-\tilde{a}| \leq \epsilon$ が達成されます。

サブルーチン FindNextK

FindNextKはこのIQAEアルゴリズムの根幹をなす部分です。以下にその考え方を示します。

初期のインターバルを $[\theta_l, \theta_u$ ]として、それを $K_i = 4k_i +2$ でスケールした $[\theta^{\rm min}_i, \theta_i^{\rm max}$ ]を考えます。求めたいのは $K = (4k+2) \geq 2K_i$ を満たす $k$ です。
上段左の図は初期の状態 $[\theta^{\min}_i, \theta^{\rm max}_i$ ]です。ここに $q = K/K_i$ をかけると、上段真ん中の図のようになります。
さらに $K$ の値を更新すると、上段右の図のようになります。しかしこれは $[0, \pi$ ]または $[\pi, 2\pi$ ]の間に両者が存在するという考えから外れてcosの値を一意に決定することができません。さらに値を更新し、下段真ん中図のようにします。ここからさらに $K$ を更新すると下段右図のようになります。この状態もcosの値を一意に定めることができないので、FindNextKは下段真ん中図の $q$ の値から $k$ を出力します。