Photo by Tengy Art on Unsplash
Part 1 ではポートフォリオ最適化の理論について紹介しました．ポートフォリオの分散の最小化問題が，
( 0 0 R ⊤ 0 0 S ⊤ R S Σ ) ( η θ ω ) = ( μ p ∗ ξ 0 ) \begin{aligned}
\begin{pmatrix}
0 & 0 & \bm{R}^\top \\
0 & 0 & \bm{S}^\top \\
\bm{R} & \bm{S} & \Sigma
\end{pmatrix}
\begin{pmatrix}
\eta \\
\theta \\
\bm{\omega}
\end{pmatrix}=
\begin{pmatrix}
\mu_p^\ast \\
\xi \\
\bm{0}
\end{pmatrix}
\end{aligned} ⎝ ⎜ ⎛ 0 0 R 0 0 S R ⊤ S ⊤ Σ ⎠ ⎟ ⎞ ⎝ ⎜ ⎛ η θ ω ⎠ ⎟ ⎞ = ⎝ ⎜ ⎛ μ p ∗ ξ 0 ⎠ ⎟ ⎞ で表される連立方程式を解くことに帰着することを見ました．
Part 2では量子アルゴリズムを用いてこの連立方程式を解く方法について見ていきます．O ( N 3 ) O(N^3) O ( N 3 ) O ( log ( N ) ) O(\log(N)) O ( log ( N ) ) 指数加速が得られます．
ちなみに位相推定を行うためにはA A A A A A
B = ( 0 A † A 0 ) B = \begin{pmatrix}
0 & A^\dagger \\
A & 0
\end{pmatrix} B = ( 0 A A † 0 ) で定義されるエルミート行列B B B A A A
実はPart 3も予定していて，そちらでは更に現実的な制約を入れたポートフォリオ最適化問題について考えます．制約を入れた場合には，二次錘計画問題(SOCP: Second Order Cone Programming)に帰着させることで，量子内点法と呼ばれるアルゴリズムを用いることができることを見ます．
今，解きたい問題は行列あるA A A x , b \bm{x},\bm{b} x , b
A x = b A\bm{x}=\bm{b} A x = b となっているとき
x = A − 1 b \bm{x} = A^{-1}\bm{b} x = A − 1 b を求める問題です．
ブラケットによる表記を用いると上の逆行列計算は
∣ x > = ∣ A − 1 b > \left| \bm{x} \right> = \left| A^{-1}\bm{b} \right> ∣ x ⟩ = ∣ ∣ ∣ A − 1 b ⟩ と書くことができます．
このような逆行列計算はHHLアルゴリズムと呼ばれる量子アルゴリズムを用いて計算可能です．
具体的なアルゴリズムの説明の前に，x , b \bm{x},\bm{b} x , b ∣ x > , ∣ b > \left| \bm{x} \right>, \left| \bm{b} \right> ∣ x ⟩ , ∣ b ⟩
量子状態へ情報を埋め込む方法としては離散化してビット列に埋め込む方法と，振幅として埋め込む方法がありますデジタルエンコーディング ，後者をアナログエンコーディング と呼ぶことにします．
ある情報j j j b i n ( j ) \mathrm{bin}(j) b i n ( j )
∣ b i n ( j ) > \left| \mathrm{bin}(j) \right> ∣ b i n ( j ) ⟩ として量子状態に埋め込むことをデジタルエンコードと呼ぶことにします．ただし，以降では表記を簡単にするために，b i n \mathrm{bin} b i n
∣ j > \left| j \right> ∣ j ⟩ と表記します．
例えば，3量子ビットの系を考えると，j j j 8 8 8 b i n ( 8 ) = 100 \mathrm{bin}(8)=100 b i n ( 8 ) = 1 0 0
∣ 8 > = ∣ 1 > ⊗ ∣ 0 > ⊗ ∣ 0 > \left| 8 \right>=\left| 1 \right>\otimes\left| 0 \right>\otimes\left| 0 \right> ∣ 8 ⟩ = ∣ 1 ⟩ ⊗ ∣ 0 ⟩ ⊗ ∣ 0 ⟩ というエンコーディングを行うことを指します．
もちろん，埋め込みたいデータが厳密に2進表示できる場合は誤差なく埋め込みできますが，2進表示できない場合には丸め誤差が発生します．
ベクトルx = ( x 1 , x 2 , … , x N ) ⊤ \bm{x}=(x_1,x_2,\dots,x_N)^\top x = ( x 1 , x 2 , … , x N ) ⊤
∣ x > = 1 ∑ j ∣ x j ∣ 2 ∑ j = 1 N x j ∣ j > \left| \bm{x} \right> = \frac{1}{\sqrt{\sum_j|x_j|^2}}\sum_{j=1}^Nx_j\left| j \right> ∣ x ⟩ = ∑ j ∣ x j ∣ 2 1 j = 1 ∑ N x j ∣ j ⟩ として埋め込むことをアナログエンコードと呼ぶことにします．
準備ができたのでHHLアルゴリズムによる逆行列計算を見ていきます．
目標は
∣ x > = ∣ A − 1 b > \left| \bm{x} \right> = \left| A^{-1}\bm{b} \right> ∣ x ⟩ = ∣ ∣ ∣ A − 1 b ⟩ を求めることです．
仮定としては
∣ b > = ∑ j b j ∣ j > \left| \bm{b} \right> = \sum_jb_j\left|j\right> ∣ b ⟩ = j ∑ b j ∣ j ⟩ がすでに得られていること，A A A
このアルゴリズムのポイントとしては
b \bm{b} b A A A 量子計算では固有値(の近似値)をデジタルエンコードできる．(量子位相推定)
デジタルエンコードされた状態∣ λ j > ∣ a j > \left| \lambda_j \right>\left| \bm{a}_j \right> ∣ λ j ⟩ ∣ a j ⟩ λ j − 1 ∣ a j > \lambda_j^{-1}\left| \bm{a}_j \right> λ j − 1 ∣ a j ⟩
という点が挙げれられます．
A A A { a i } , { λ i } \{ \bm{a}_i\}, \{\lambda_i\} { a i } , { λ i }
A a i = λ i a i A\bm{a}_i =\lambda_i\bm{a}_i A a i = λ i a i から
A − 1 a i = λ i − 1 a i A^{-1} \bm{a}_i =\lambda_i^{-1} \bm{a}_i A − 1 a i = λ i − 1 a i がすぐに分かります．
さてb \bm{b} b A A A { a i } \{\bm{a}_i\} { a i }
b = ∑ i β i a i \bm{b} =\sum_i \beta_i\bm{a}_i b = i ∑ β i a i ここで上の関係を用いると
A − 1 b = ∑ i β i λ i − 1 a i A^{-1} \bm{b}=\sum_i \beta_i\lambda_i^{-1}\bm{a}_i A − 1 b = i ∑ β i λ i − 1 a i となることがわかります．
量子状態を使えば，逆行列計算を求める，という目標は
∣ A − 1 b > ∝ ∑ i β i λ i − 1 ∣ a i > \left| A^{-1}\bm{b} \right>\propto\sum_i \beta_i\lambda_i^{-1}\left|\bm{a}_i \right> ∣ ∣ ∣ A − 1 b ⟩ ∝ i ∑ β i λ i − 1 ∣ a i ⟩ を作ってやる，という目標に置き換えることができます．
さて，仮定から
∣ b > = ∑ j b j ∣ j > \left| \bm{b} \right> = \sum_jb_j\left|j \right> ∣ b ⟩ = j ∑ b j ∣ j ⟩ を持っていますが，基底を取り替えることで
∣ b > = 1 ∑ i ∣ β i ∣ 2 ∑ i β i ∣ a i > \left| \bm{b} \right> = \frac{1}{\sqrt{\sum_i|\beta_i|^2}}\sum_i\beta_i\left|\bm{a}_i \right> ∣ b ⟩ = ∑ i ∣ β i ∣ 2 1 i ∑ β i ∣ a i ⟩ を持っている，と解釈することもできます．
そうするとやりたいことは
∣ a i > \left| \bm{a}_i \right> ∣ a i ⟩ から
λ i − 1 ∣ a i > \lambda_i^{-1}\left|\bm{a}_i \right> λ i − 1 ∣ a i ⟩ を作る演算ができれば，∣ b > \left| \bm{b}\right> ∣ b ⟩
ということで，∣ a i > → λ i − 1 ∣ a i > \left| \bm{a}_i \right>\rightarrow\lambda_i^{-1}\left|\bm{a}_i \right> ∣ a i ⟩ → λ i − 1 ∣ a i ⟩ ∣ λ i > ∣ a i > \left| \lambda_i \right>\left| \bm{a}_i \right> ∣ λ i ⟩ ∣ a i ⟩
ユニタリ演算子U U U { ∣ u j > } \{\left| \bm{u}_j \right>\} { ∣ u j ⟩ } { e i 2 π η j , η i ∈ R } \{e^{i2\pi\eta_j},\eta_i \in \mathcal{R}\} { e i 2 π η j , η i ∈ R } U U U
量子位相推定(Quantum Phase Estimation)では
∣ u j > → ∣ η j > ∣ u j > \left| \bm{u}_j \right> \rightarrow \left| \eta_j \right>\left| \bm{u}_j \right> ∣ u j ⟩ → ∣ η j ⟩ ∣ u j ⟩ として，固有値の位相をデジタルエンコードすることが可能です．
まず，η i \eta_i η i
η i = ∑ k = 1 M 2 − k η i , k \eta_i=\sum_{k=1}^M2^{-k}\eta_{i,k} η i = k = 1 ∑ M 2 − k η i , k となります．
M個の補助量子ビットを用いて，Hadamardゲートと制御量子ビットを∣ k > \left|k \right> ∣ k ⟩ U k U^k U k
∣ u j > → H ⊗ M 1 2 n / 2 ∑ k = 0 2 M − 1 ∣ k > ∣ u j > → c o n t r o l − U k 1 2 n / 2 ∑ k = 0 2 M − 1 exp ( i 2 π k ( ∑ k ′ = 1 M 2 − k ′ η j , k ′ ) ) ∣ k > ∣ u j > = 1 2 n / 2 ∑ k = 0 2 M − 1 exp ( i 2 π k η j ) ∣ k > ∣ u j > \begin{aligned}
\left| \bm{u}_j \right> &\stackrel{H^{\otimes M}}{\rightarrow}
\frac{1}{2^{n/2}}\sum_{k=0}^{2^M-1}\left| k \right>\left| \bm{u}_j \right> \\
& \stackrel{\mathrm{control-}U^k}{\rightarrow}
\frac{1}{2^{n/2}}\sum_{k=0}^{2^M-1}\exp\left(i2\pi k\left(\sum_{k'=1}^M2^{-k'}\eta_{j,k'}\right)\right)\left| k \right>\left| \bm{u}_j \right>\\
& =
\frac{1}{2^{n/2}}\sum_{k=0}^{2^M-1}\exp\left(i2\pi k\eta_j\right)\left| k \right>\left| \bm{u}_j \right>
\end{aligned} ∣ u j ⟩ → H ⊗ M 2 n / 2 1 k = 0 ∑ 2 M − 1 ∣ k ⟩ ∣ u j ⟩ → c o n t r o l − U k 2 n / 2 1 k = 0 ∑ 2 M − 1 exp ( i 2 π k ( k ′ = 1 ∑ M 2 − k ′ η j , k ′ ) ) ∣ k ⟩ ∣ u j ⟩ = 2 n / 2 1 k = 0 ∑ 2 M − 1 exp ( i 2 π k η j ) ∣ k ⟩ ∣ u j ⟩ が得られます．
これに量子逆フーリエ変換を行ってやると
1 2 n / 2 ∑ k = 0 2 M − 1 exp ( i 2 π k η j ) ∣ k > ∣ u j > → I − Q F T ∣ η j > ∣ u j > \begin{aligned}
\frac{1}{2^{n/2}}\sum_{k=0}^{2^M-1}\exp\left(i 2\pi k\eta_j\right)\left| k \right>\left| \bm{u}_j \right> \stackrel{I-QFT}{\rightarrow}\left| \eta_j \right>\left| \bm{u}_j \right>
\end{aligned} 2 n / 2 1 k = 0 ∑ 2 M − 1 exp ( i 2 π k η j ) ∣ k ⟩ ∣ u j ⟩ → I − Q F T ∣ η j ⟩ ∣ u j ⟩ となります．
さて，HHLのサブルーチンとしてはU = e i 2 π A U=e^{i2\pi A} U = e i 2 π A
∣ a i > → ∣ λ i > ∣ a i > \left| \bm{a}_i \right> \rightarrow \left| \lambda_i \right>\left| \bm{a}_i \right> ∣ a i ⟩ → ∣ λ i ⟩ ∣ a i ⟩ として，固有値をデジタルエンコードすることが可能です．e i A e^{iA} e i A A A A
制御回転ゲートにより，
∣ λ i > ∣ a i > → ∣ λ i > ( ∣ a i > λ i − 1 ∣ 0 > + 1 − λ i − 2 ∣ 1 > ) \left| \lambda_i \right>\left| \bm{a}_i \right>\rightarrow\left| \lambda_i \right>\left(\left| \bm{a}_i \right>\lambda_i^{-1}\left| 0 \right>+\sqrt{1-\lambda_i^{-2}}\left|1 \right>\right) ∣ λ i ⟩ ∣ a i ⟩ → ∣ λ i ⟩ ( ∣ a i ⟩ λ i − 1 ∣ 0 ⟩ + 1 − λ i − 2 ∣ 1 ⟩ ) とすることが可能です．その後余計なレジスタ∣ λ i > \left| \lambda_i \right> ∣ λ i ⟩ ∣ 0 > \left| 0 \right> ∣ 0 ⟩
λ i − 1 ∣ a i > \lambda_i^{-1}\left| \bm{a}_i \right> λ i − 1 ∣ a i ⟩ が得られます．
ここまでをまとめると
∣ b > = 1 ∑ i ∣ β i ∣ 2 ∑ i β i ∣ a i > → Q P E 1 ∑ i ∣ β i ∣ 2 ∑ i β i ∣ λ i > ∣ a i > → D A c o n v . 1 ∑ i ∣ β i λ i − 1 ∣ 2 ∑ i β i λ i − 1 ∣ a i > \begin{aligned}
\left| \bm{b} \right> = \frac{1}{\sqrt{\sum_i|\beta_i|^2}} \sum_{i}\beta_i\left| \bm{a}_i \right> &\stackrel{\mathrm{QPE}}{\rightarrow} \frac{1}{\sqrt{\sum_i|\beta_i|^2}}\sum_{i}\beta_i\left| \lambda_i \right> \left| \bm{a}_i \right> \\
&\stackrel{\mathrm{DA conv.}}{\rightarrow}\frac{1}{\sqrt{\sum_i|\beta_i\lambda_i^{-1}|^2}}\sum_{i}\beta_i \lambda_i^{-1} \left| \bm{a}_i \right>
\end{aligned} ∣ b ⟩ = ∑ i ∣ β i ∣ 2 1 i ∑ β i ∣ a i ⟩ → Q P E ∑ i ∣ β i ∣ 2 1 i ∑ β i ∣ λ i ⟩ ∣ a i ⟩ → D A c o n v . ∑ i ∣ β i λ i − 1 ∣ 2 1 i ∑ β i λ i − 1 ∣ a i ⟩ となり，目標であった
∣ A − 1 b > = 1 ∑ i ∣ β i λ i − 1 ∣ 2 ∑ i β i λ i − 1 ∣ a i > \left| A^{-1}\bm{b}\right> = \frac{1}{\sqrt{\sum_i|\beta_i\lambda_i^{-1}|^2}}\sum_{i}\beta_i \lambda_i^{-1} \left| \bm{a}_i \right> ∣ ∣ ∣ A − 1 b ⟩ = ∑ i ∣ β i λ i − 1 ∣ 2 1 i ∑ β i λ i − 1 ∣ a i ⟩ を得ることができました．
このHHLアルゴリズムについてはA A A κ \kappa κ A A A N N N O ( p o l y log ( N ) ) O(\mathrm{poly}\log(N)) O ( p o l y log ( N ) ) O ( p o l y ( κ ) ) O(\mathrm{poly}(\kappa)) O ( p o l y ( κ ) )
このHHLアルゴリズムにはいくつか注意点があって，
行列A A A
古典の情報x \bm{x} x ∣ x > \left| \bm{x} \right> ∣ x ⟩ O ( N ) O(N) O ( N )
同様に，得られた状態∣ A − 1 b > \left| A^{-1}\bm{b} \right> ∣ ∣ ∣ A − 1 b ⟩ O ( N ) O(N) O ( N )
