めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

Phase Estimator の量子回路を解説してみる(その1)

まずは、Phase Estimator の基礎となる、量子フーリエ変換の実装を解説します。

(離散)フーリエ変換とは?

形式的に言うと、N 成分の複素ベクトル \mathbf x = (x_0,\cdots,x_{N-1})N 成分の複素ベクトル \mathbf y = (y_0,\cdots,y_{N-1}) に変換する、次の計算式です。

 \displaystyle y_k := \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\exp\left(2\pi i\times\frac{jk}{N} \right) --- (1)

このような変換を考えて何が嬉しいのかと言うと・・・、実はこの変換には、元の成分 (x_0,\cdots,x_{N-1}) を数列とみなした時に、この数列が持つ「周期性」を検出する機能があります。

論より証拠で具体例を見てみましょう。

まず、\mathbf x の成分がすべて同じ(言うなれば周期 0)の場合で、 x_j = 1\,(j=0,\cdots,15) とします。対応する  y_k\,(k=0,\cdots,15) の方は、(複素数をグラフ表示するのは難しいので)実部を取り出してグラフに描きます。

これを見ると、y_k の方は、y_0 だけが値を持っています。つまり、y_0 は周期 0 (定数)を示すフラグなのです。

次に、\displaystyle x_j = \cos\left(\frac{2  \pi j}{16}\right) として同様のグラフを描きます。

この場合、x_j j=0,\cdots,15 の範囲でちょうど1回振動する(この範囲を単位として)周期1の三角関数です。y_k の方は、y_1y_{15} だけが値を持っています。つまり、この2つが周期1のフラグと言えます。(連続的なフーリエ変換を知っている方は、y_{15} が値を持つのが気持ち悪いかもしれませんが、今は値を持つ部分が離散的なので、周期 1/2 と周期 1/30 の区別がつかないことが理由です。)

あとは大体予想がつきますが、\displaystyle x_j = \cos\left(\frac{4  \pi j}{16}\right) とすると次の結果になります。

x_j j=0,\cdots,15 の範囲で2回振動する(この範囲を単位として)周期0.5の三角関数です。y_k の方は、y_2y_{14} だけが値を持っています。

この変換は、複数の周期を合成したものを検知することもできます。次の関数を考えてみましょう。

 \displaystyle x_j = \frac{1}{2}\left\{\cos\left(\frac{2  \pi j}{16}\right)+\cos\left(\frac{4  \pi j}{16}\right)\right\}

結果は次の通りです。

周期1と周期0.5に対応するフラグがどちらも反応していることがわかります。

このようにフーリエ変換を用いると、さまざまな関数の「周期性」を発見するのに役立てることができます。

・・・これ自体は量子回路と何の関係もありませんが、フーリエ変換を愚直に実行すると計算量は  O(N^2) になります。つまり、N 項の級数を N 変数分計算する必要があります。より高速に計算する FFT (高速フーリエ変換)のアルゴリズムが知られていますが、この場合の計算量は O(N\log N) です。一方、量子回路を用いると、O\left((N\log N)^2\right) の計算量でこれを実行することができます。つまり、フーリエ変換は、量子コンピューターを用いることで、古典コンピューターよりも高速に実行できるのです。

量子ビットによるフーリエ変換の表現

(1) のフーリエ変換はベクトルの成分を用いて表されていましたが、線形変換になっていることがわかります。したがって、この成分表示に対応する正規直交基底を {\mid 0\rangle},\cdots,{\mid N-1\rangle} として、それぞれの基底ベクトルの変換法則がわかれば十分です。具体的には、

 \displaystyle\mathbf x = \sum_{j=0}^{N-1}x_j{\mid j\rangle},\ \mathbf y = \sum_{k=0}^{N-1}y_k{\mid k\rangle}

として、フーリエ変換を \mathbf y = U(\mathbf x) と表すことにすると、次の関係が成り立ちます。

 \displaystyle U(\mathbf x) = \sum_{k=0}^{N-1}y_k{\mid k\rangle} = \sum_{k=0}^{N-1}\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\exp\left(2\pi i\times\frac{jk}{N} \right){\mid k\rangle} =  \sum_{j=0}^{N-1}x_j\left\{\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\exp\left(2\pi i\times\frac{jk}{N} \right){\mid k\rangle}\right\}

これより、基底ベクトルの変換法則は次になることがわかります。

 \displaystyle U({\mid j\rangle}) = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\exp\left(2\pi i\times\frac{jk}{N} \right){\mid k\rangle} --- (2)

ここで、N 個ある基底ベクトルを  n = \log N 個の量子ビットで表現します。これは単純に j=0,\cdots,N-1 を二進数表記に直して、各桁のビットを量子ビットに置き換えます。たとえば、N=4 として、次のような対応になります。

  {\mid 0\rangle} \Leftrightarrow {\mid 00\rangle} = {\mid 0\rangle}\otimes {\mid 0\rangle}
  {\mid 1\rangle} \Leftrightarrow {\mid 01\rangle}  = {\mid 0\rangle}\otimes {\mid 1\rangle}
  {\mid 2\rangle} \Leftrightarrow {\mid 10\rangle} = {\mid 1\rangle}\otimes {\mid 0\rangle}
  {\mid 3\rangle} \Leftrightarrow {\mid 11\rangle} = {\mid 1\rangle}\otimes {\mid 1\rangle}

一般に、n 個の量子ビットによる基底ベクトルを  {\mid k_1\rangle}\otimes\cdots\otimes {\mid k_n\rangle} と表すと、次の対応関係が成り立ちます。

 \displaystyle \sum_{k=0}^{N-1}f(k){\mid k\rangle} \Leftrightarrow \sum_{k_1=0}^1\cdots\sum_{k_n=0}^1f\left(\sum_{l=1}^nk_l2^{n-l}\right){\mid k_1\rangle}\otimes\cdots\otimes {\mid k_n\rangle} --- (3)

ここに、 k = [k_1k_2\cdots k_n]k の二進数表記(つまり \displaystyle k = \sum_{l=1}^n k_l 2^{n-l})とします。

そして、この「量子ビット基底ベクトル」を用いると、(2) の変換は量子ビットごとの変換に置き換えることができます。\displaystyle j=[j_1j_2\cdots j_n]= \sum_{l=1}^n j_l 2^{n-l} とする時、(3) のルールを用いて (2) を書き直すと次のようになります。

 \displaystyle U( {\mid j_1\rangle}\otimes\cdots\otimes {\mid j_n\rangle}) = \frac{1}{2^{n/2}}\sum_{k_1=0}^1\cdots\sum_{k_n=0}^1\exp\left(2\pi i \times \frac{j k}{2^n}\right){\mid k_1\rangle}\otimes\cdots\otimes {\mid k_n\rangle}

  \displaystyle = \frac{1}{2^{n/2}}\sum_{k_1=0}^1\cdots\sum_{k_n=0}^1\exp\left(2\pi i \times j \sum_{l=1}^n k_l 2^{-l}\right){\mid k_1\rangle}\otimes\cdots\otimes {\mid k_n\rangle}

  \displaystyle = \frac{1}{2^{n/2}}\sum_{k_1=0}^1\cdots\sum_{k_n=0}^1\prod_{l=1}^n \exp\left(2\pi i \times j  k_l 2^{-l}\right){\mid k_1\rangle}\otimes\cdots\otimes {\mid k_n\rangle}

  \displaystyle = \frac{1}{2^{n/2}}\sum_{k_1=0}^1\cdots\sum_{k_n=0}^1\bigotimes_{l=1}^n \exp\left(2\pi i \times j  k_l 2^{-l}\right){\mid k_l\rangle}

  \displaystyle = \frac{1}{2^{n/2}}\bigotimes_{l=1}^n \left\{ {\mid 0\rangle} +  \exp\left(2\pi i \times j 2^{-l}\right){\mid 1\rangle}\right\} --- (4)

最後の \displaystyle  \exp\left(2\pi i \times j 2^{-l}\right) の部分は、二進数表記  j = [j_1j_2\cdots j_n] を用いると、

 \displaystyle j2^{-l} =  [j_1\cdots j_{n-l}]+[0.j_{n-l+1}\cdots j_n]

であることから、\displaystyle \exp\left(2\pi i\times [j_1\cdots j_{n-l}]\right) = 1 より、次のように簡単化できます。

 \displaystyle  \exp\left(2\pi i \times j 2^{-l}\right) = \exp\left(2\pi i \times[0.j_{n-l+1}\cdots j_n]\right)

これを (4) に代入して、最終的に次の関係が得られます。

 \displaystyle U( {\mid j_1\rangle}\otimes\cdots\otimes {\mid j_n\rangle} ) = \frac{1}{2^{n/2}}
\left( {\mid 0\rangle} + e^{2\pi i[0.j_n]}{\mid 1\rangle}\right)
\left({\mid 0\rangle}+e^{2\pi i[0.j_{n-1}j_n]}{\mid 1\rangle}\right)
\cdots
\left({\mid 0\rangle}+e^{2\pi i[0.j_1\cdots j_n]}{\mid 1\rangle}\right) --- (5)

ここまでは量子回路とは関係のない、ただのテンソル計算と見ることもできますが、実はこの最後の表式から、この変換はアダマールゲートH と位相シフトゲート

 \displaystyle R_k := \begin{pmatrix}
1 & 0 \\
0 & e^{2\pi i / 2^k}
\end{pmatrix}k=2,\cdots,n)

を用いた量子回路で実装できることがわかります。上記の位相シフトは、\displaystyle R_k = Z^{1/2^{k-1}} として実装できます。(Z 演算を物理実装する制御パルスの照射時間を変化させます。)

また、二進数表記を用いると、位相シフトゲートは次のようにも表現できます。(これが量子回路実装のポイントになります。)

  R_2 = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i[0.01]}\end{pmatrix},\ R_3 = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i[0.001]}\end{pmatrix},\cdots --- (6)

量子回路によるフーリエ変換の実装

結論から言うと、次の量子回路で実装できます。

はじめに、{\mid j_1\rangle} に対する H \rightarrow CR_2  \rightarrow \cdots  \rightarrow CR_n の流れを見ます。まず、

 \displaystyle j_1 = 0 \Rightarrow e^{ 2\pi i[0.j_1] } = 1
 \displaystyle  j_1 = 1 \Rightarrow e^{ 2\pi i[0.j_1] } = -1

の関係に注意すると、

 \displaystyle H{\mid j_1\rangle} = \frac{1}{2^{1/2}}\left({\mid 0\rangle}+e^{2\pi i [0.j_1]}{\mid 1\rangle}\right)

が成り立ちます。次に、CR_2 を演算すると、(6) の関係に注意して次が成り立ちます。

 \displaystyle CR_2 H{\mid j_1\rangle}\otimes{\mid j_2\rangle} = \frac{1}{2^{1/2}} \left({\mid 0\rangle}+e^{2\pi i [0.j_1]}e^{2\pi i [0.0j_2]} {\mid 1\rangle}\right)\otimes{\mid j_2\rangle}
=\frac{1}{2^{1/2}} \left({\mid 0\rangle}+e^{2\pi i [0.j_1j_2]}{\mid 1\rangle}\right)\otimes{\mid j_2\rangle}

以下同様にして、CR_3,\cdots,CR_n を演算すると、最初の量子ビット  \displaystyle{\mid j_1\rangle} は次のように変化します。

  \displaystyle{\mid j_1\rangle} \longrightarrow \displaystyle \frac{1}{2^{1/2}} \left({\mid 0\rangle}+e^{2\pi i [0.j_1j_2\cdots j_n]}{\mid 1\rangle}\right)

2つ目以降の量子ビットについても同様の処理が行われるので、最後の H まで演算したところで、全体の状態は次になります。

 \displaystyle \frac{1}{2^{n/2}}
\left({\mid 0\rangle}+e^{2\pi i[0.j_1\cdots j_n]}{\mid 1\rangle}\right)
\left({\mid 0\rangle}+e^{2\pi i[0.j_2\cdots j_n]}{\mid 1\rangle}\right)
\cdots
\left( {\mid 0\rangle} + e^{2\pi i[0.j_n]}{\mid 1\rangle}\right)

これは、(5) の量子ビットの順番を反転させたものになっているので、最後にスワップゲートを組み合わせて、量子ビットの順序を並び替えれば完成です。

Cirq による実装例

github.com

「量子機械学習(Quantum Machine Learning)」とは?

基本的な考え方

量子回路のすべての構成を人間が設計するのではなく、チューニング可能なパラメーターを含む形で量子回路を構成しておき、これが期待する動作を実現するようにパラメーターをチューニングする。

古典データを量子状態に変換して入力する場合と、もともと量子状態であるものを入力データにする場合がある。

QVE

arxiv.org

あるハミルトニアン H の基底エネルギーを近似的に求める手法。パラメーター(\theta)を持つ量子回路をユニタリ変換 U(\theta) とみなして、この回路が出力する量子状態  |\psi(\theta)\rangle = U(\theta)|0\rangle について、ハミルトニアンの期待値を計算する(期待値計算は古典計算機を組み合わせて行う。)この期待値が減少するように、パラメーター(\theta)をチューニングする。

この問題の場合、学習対象データが量子状態なので、量子回路を利用するのは自然なアプローチと言える。

量子ニューラルネットワーク

arxiv.org

↑比較的シンプルな関数のリグレッションを量子回路で実装した実験結果。

arxiv.org

↑ニューラルネットワークによる分類器を量子回路に置き換えて実装した例。

www.tensorflow.org

↑CNNの量子回路版の提案例

量子データを古典データに変換する手法

量子データが前提であれば、量子回路でコヒーレンスを高めて特徴量を抽出しやすくした後に、それを古典ニューラルネットワークで処理すると言うハイブリッドアプローチも考えられる。

arxiv.org

arxiv.org

↑これらは、量子回路は入力状態をランダムにかき混ぜるだけの固定的な構成、そこから得られた古典データ(観測値)を古典的な線形モデルに入力する。

パラメーターチューニングの方法

古典ニューラルネットワークであれば、数学的に勾配計算を行って、勾配効果法が適用できるが、量子回路の勾配計算はできないので、他のアプローチが必要となる。

arxiv.org

↑よくあるタイプのゲートについては、その微分を量子回路で計算できることを示した結果

arxiv.org

↑単純な差分計算で微分を近似するよりも、解析的な微分値を量子回路で計算した方が有意な場合があることを示した論文

ITエンジニアのための機械学習理論入門:Colaboratory版サンプルスクリプト

ITエンジニアのための機械学習理論入門

ITエンジニアのための機械学習理論入門

  • 作者:中井 悦司
  • 出版社/メーカー: 技術評論社
  • 発売日: 2015/10/17
  • メディア: 単行本(ソフトカバー)

上記の書籍では、Python の実行環境として Canopy を用いたセットアップ手順を紹介していますが、Canopy が公開中止となってしまいました。

代替の方法として、Google Colaboratory で実行可能なノートブック形式のサンプルスクリプトを用意しています。下記の記事に従ってご利用ください。

enakai00.hatenablog.com