FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages

量子コンピュータ向けのMicrosoftの新言語「Q#」の勉強 (2. 複数量子ビットの処理)

Q#、というか、量子コンピュータについて勉強するためには、Microsoft のドキュメントを読むのがよさそうだ。

今回は複数の量子ビットについて。 行列の計算が分かっていれば、多少はついていける。なるほど、テンソル積ってこんなところでも使うのか。

関連記事

これは著者が読んだ内容をまとめているだけなので、誤訳、理解不足により誤っている可能性があります!鵜呑みにしないようにお願いします。

複数量子ビット

単一の量子ビットは、同時に複数の状態を持つことができるという直感とは異なる特徴を持っているが、もしすべての量子コンピュータが1つの量子ビットしかもっていないならば、その計算能力は古典的なスーパーコンピュータどころか、電子計算機よりも劣ったものとなる。 量子コンピューティングの真の力は、量子ビットの数を増やしたときに発揮される。 量子ビットの数が増えると、量子状態ベクタの状態空間の次元は指数関数的に増加する。 これはつまり、単一の量子ビットは単純にモデル化することができるが、50個の量子ビットの計算をシミュレーションするためには、現代のスーパーコンピュータの限界を推し進めることにもつながる。 1つの量子ビットを追加するだけで、状態を格納するために必要なメモリのサイズが倍になり、計算に必要な時間は2倍に膨れ上がるのだ。 少量の量子ビットによる量子コンピュータが、現代のスーパーコンピュータを上回る能力を持つことができるのは、このような計算能力が倍増することに起因するものである。

何故、量子状態ベクタは指数関数的に増加するのだろうか? 本セクションの私たちの目標は、単一の量子ビットの状態から、複数量子ビットの状態のルールをレビューし、ユニバーサルな複数量子ビットで構成される量子コンピュータを形成するために含めるべきゲート操作の集合について議論することである。 これらのツールは、Q#のコードにおいて共通に使用されているゲートの集合を理解するために絶対的に必要であり、エンタングルメントや、干渉などの量子効果により、古典的コンピュータと比較して量子コンピュータが協力になる理由を直感的に理解できるようになる。

2つの量子ビットを表現する

1量子ビットの状態を表現するのと、2量子ビット状態の表現の大きな違いは、1量子ビットの場合は2次元であったのが、4次元になるということである。 これは、計算の基本が、2量子ビット状態は1つの量子ビットの状態のテンソル積で表現されるということに基づいている。 例えば、以下のようになる。

 00\equiv\begin{bmatrix}1\\0\end{bmatrix}\otimes\begin{bmatrix}1\\0\end{bmatrix}\otimes=\begin{bmatrix}1\\0\\0\\0\end{bmatrix},  01\equiv\begin{bmatrix}1\\0\end{bmatrix}\otimes\begin{bmatrix}0\\1\end{bmatrix}\otimes=\begin{bmatrix}0\\1\\0\\0\end{bmatrix},  10\equiv\begin{bmatrix}0\\1\end{bmatrix}\otimes\begin{bmatrix}1\\0\end{bmatrix}\otimes=\begin{bmatrix}0\\0\\1\\0\end{bmatrix},  11\equiv\begin{bmatrix}0\\1\end{bmatrix}\otimes\begin{bmatrix}0\\1\end{bmatrix}\otimes=\begin{bmatrix}0\\0\\0\\1\end{bmatrix}

一般化すると、n個の量子ビットの状態を表現するのに、 2^{n} の次元が必要であるということは理解できる。

ベクトル  \begin{bmatrix}\alpha_{00} \\ \alpha_{01} \\ \alpha_{10} \\ \alpha_{11}\end{bmatrix} は、2つの量子ビットの2つの量子状態を表現しており、 \left|\alpha_{00}\right|^2+\left|\alpha_{01}\right|^2+\left|\alpha_{10}\right|^2+\left|\alpha_{11}\right|^2=1 単一量子ビットのように、複数量子ビットの量子状態は、システムの状態を記述するのに必要なすべての情報を保持している。

2つの分離した量子ビットが与えられたとき、1つの状態は\begin{bmatrix}\alpha\\ \beta\end{bmatrix} で、2つ目の状態が \begin{bmatrix}\gamma\\ \theta\end{bmatrix} であるときに、対応する2量子ビット状態は以下のように表現される。

\begin{bmatrix}\alpha\\ \beta \end{bmatrix}\otimes\begin{bmatrix}\gamma \\ \theta \end{bmatrix}\otimes=\begin{bmatrix}\alpha\begin{bmatrix}\gamma\\ \theta\end{bmatrix}\\ \beta \begin{bmatrix}\gamma \\ \theta\end{bmatrix}\end{bmatrix} = \begin{bmatrix}\alpha\gamma \\ \alpha\theta \\ \beta\gamma \\ \beta\theta\end{bmatrix}

\otimes はベクトルのテンソル積(もしくはクロネッカー積)と呼ばれている。 以降2つの1量子ビット状態のテンソル積をとり2量子ビット状態を取るとき、すべての2量子ビット状態が、2つの1量子ビットテンソル積となるわけではないということに注意である。 例えば、\psi=\begin{bmatrix}\alpha\\ \beta\end{bmatrix}, \phi=\begin{bmatrix}\gamma\\ \theta\end{bmatrix} で、以下のようなテンソル積は存在しない。

\psi\otimes\phi= \begin{bmatrix}\dfrac{1}{\sqrt{2}}\\0\\0\\ \dfrac{1}{\sqrt{2}}\end{bmatrix}

このような2量子ビットの状態、つまり1つの量子ビットテンソル積で表現できないような状態のことを「エンタグル状態」と呼ぶ。 2量子ビットはエンタグルと呼ばれる。 大雑把に言うと、量子状態は1量子ビットテンソル積であると考えることはできないため、保持している状態はそれぞれの量子ビットの状態に限定されない。 2つの状態の間で、状態はかなり非局所的に保存される。 この情報の非局所性は量子コンピューティングにおいて、古典的なコンピューティングと比較して特徴的な部分であり、量子テレポーテーションや量子エラー訂正を含む、量子プロトコルの基本的な要素である。

2量子ビット状態の測定

2量子ビット状態の測定は、1量子ビットの測定と非常に似ている。 以下の状態を測定するものとする:

\begin{bmatrix}\alpha_{00}\\ \alpha_{01}\\ \alpha_{10}\\ \alpha_{11}\end{bmatrix}

は、00\left|\alpha_{00}\right|01\left|\alpha_{01}\right|10\left|\alpha_{10}\right|11\left|\alpha_{11}\right| の確率であることを示す。 変数 \alpha_{00}, \alpha_{01}, \alpha_{10}, \alpha_{11} はこの接続をクリアにするために付けられた任意の名前である。 測定後、もし出力が00 ならば、2量子ビットのシステムの量子状態は破壊され、 00\equiv\begin{bmatrix}1\\0\\0\\0\end{bmatrix} となる。

2量子ビットの状態の中で、1つの量子ビットのみ測定することも可能である。 1量子ビットの状態のみ測定した場合、システム全体は破壊されず、1つのサブシステムのみは解されるため、測定の影響は微妙に異なる。 言い換えれば、1量子ビットのみ測定した場合はサブシステムの一つのみが破壊され、システム全体が破壊されるわけではない。

この考慮すべき最初の量子ビットの状態についてみるために、初期値が"0"状態である2量子ビットに対して、Hadamard変換$H$を適用した場合を考える。

H^{\otimes 2}\left(\begin{bmatrix}1\\0\end{bmatrix}\otimes\begin{bmatrix}1\\0\end{bmatrix}\right) = \dfrac{1}{2}\begin{bmatrix}1\\1\\1\\1\end{bmatrix} \rightarrow \begin{cases}\text{outcome} = 0\dfrac{1}{\sqrt{2}}\begin{bmatrix}1\\1\\0\\0\end{bmatrix}\\ \text{outcome}=1\dfrac{1}{\sqrt{2}}\begin{bmatrix}0\\0\\1\\1\end{bmatrix}\end{cases}

どちらの出力も、50%の可能性で発生する。 50%の発生確率は、最初の量子ビットの状態を0から1に変更しても最初の量子状態ベクトルは普遍であると言うことから、直感的に分かるだろう。

1番目と2番目の量子ビットを測定するための数学的なルールは単純だ。 $e_k$を$k$番目の計算基底ベクトルとし、S を問題の量子ビットが1となる k の全ての e_k であるとしよう。 例えば、もし1番目の量子ビットを測定したい場合、 Se_2\equiv 10e_3\equiv 11 である。 同様に、2番目の量子ビットを測定したい場合は、 Se_1\equiv 01 および e_3\equiv 11 である。 従って、選択した量子ビットが1となる確率は、 状態ベクトル \psi を用いて以下のように表現できる。

P\left(\text{outcome}=1\right)=\sum_{k\text{in the set}S} \psi^{\dagger} e_k e^{\dagger} \psi

量子ビットの測定では、0と1しか観測されないため、0が測定される確率は単純に$1-P(\text{outcome}=1)$ である。 これが、我々が1を測定する確率しか示さなかった理由である。

このような状態の測定は、数学的に以下のように表現することが出来る。

[tex:\psi\mapsto\dfrac{\sum{k\text{in the set}S} e_k e^{\dagger}k \psi}{1}]

読者の皆さんは、測定の確率が0である場合について考慮する必要は無い。 このような状態は技術的に起こりえないため、私たちはそのような例外的な条件について考慮する必要は無い!

$\psi$ が上記のようにuniform state vectorで与えられ、1番目の量子ビットの測定について興味がある場合、以下のようになる。

P\left(1番目の量子ビットを測定した結果=1\right) = \left(\psi^{\dagger}e_2\right) \left(e_2^{\dagger}\psi\right) + \left(\psi^{\dagger}e_3\right) \left(e_3^{\dagger}\psi\right) = \left|e_2^{\dagger}\psi\right|^2+\left|e_3^{\dagger}\psi\right|^2

これは、測定結果が10もしくは11になる確率の輪であることに注意して欲しい。 例えば、以下のように示すことが出来、直感的な確率と等価になる。

$$\dfrac{1}{4}\left|\begin{bmatrix}0&&0&&1&&0\end{bmatrix}\begin{bmatrix}1\\1\\1\\1\end{bmatrix}\right|^2 + \dfrac{1}{4}\left|\begin{bmatrix}0&&0&&0&& 1\end{bmatrix}\begin{bmatrix}1\\1\\1\\1\end{bmatrix}\right|^2 = \dfrac{1}{2} $$

同様に、状態は以下のように記述することが出来、直感と一致する。

\dfrac{\frac{e_2}{2}+\frac{e_3}{2}}{\sqrt{\frac{1}{2}}} = \dfrac{1}{\sqrt{2}}\begin{bmatrix}0\\0\\1\\1\end{bmatrix}

2量子ビットの演算

1量子ビットの場合、任意のユニタリ変換は、量子ビットの有効な演算であった。 一般的に、n 個の量子ビットについてユニタリ変換は 2^{n}\times 2^{n} のサイズの行列 U の変換である(つまり、 2^{n} サイズのベクトル演算が発生する)。 例えば、CNOT(制御NOT)ゲートは一般的に2つの量子ビットゲートを用いて、以下のユニタリ行列を使って表現される。 $$ \text{CNOT}=\begin{bmatrix}1&&0&&0&&0\\0&&1&&0&&0\\0&&0&&0&&1\\0&&0&&1&&0\end{bmatrix} $$

2量子ビットゲートは、単一量子ゲートを両方の量子ビットに適用することによって構成することが出来る。例えば、以下の2つのゲートを適用したとする。 $$\begin{bmatrix}a&&b\\c&&d\end{bmatrix}$$ と $$\begin{bmatrix}e&&f\\g&&h\end{bmatrix}$$ これらをそれぞれの量子ビットに適用すると、以下のテンソル積を適用したものと同じ意味になる。

$$\begin{bmatrix}a&&b\\c&&d\end{bmatrix}\otimes \begin{bmatrix}e&&f\\g&&h\end{bmatrix} = \begin{bmatrix}ae&&af&&be&&bf\\ag&&ah&&bg&&bh\\ce&&cf&&de&&df\\cg&&ch&&dg&&dh\end{bmatrix}$$

すなわち、2つの量子ビットゲートは2つの1ビット量子ゲートのテンソル積によって表現できる。 2量子ビットゲートの例としては、H\otimes H, X\otimes 1, X\otimes Z などがある。

注意したいのは、量子ビットゲート2つのテンソル積の全てが、2量子ビットゲートを構成することが出来るが、その逆は真ではないということである。 全ての2量子ビットゲートを、1量子ビットゲートを2つ用いたテンソル積と表現することは出来ない。このようなゲートを「エンタングリングな」ゲートと呼ぶ。 一つのエンタングリングなゲートの例としては、CNOTゲートが挙げられる。

制御されていないゲートの背後にある直観は、任意のゲートに一般化できる。 一般的な制御されたゲートは、特定の量子ビットが1でない限り同一である。

このような、制御されたユニタリ、x でラベリングされている量子ビット上で制御されている場合に、これを \Lambda_x(U) と記述する。 例えば、

  • \Lambda_0(U)e_1\otimes\psi=e_1\otimes U\psi
  • \Lambda_0(U)e_1\otimes\psi=e_0\otimes\psi

ここで、e_0e_1 は単一量子ビットであり、伝統的な量子ビットの0と1に相当する。 例えば、以下の制御された Z ゲートについて考えてみる。

$$\Lambda_0(Z)=\begin{bmatrix}1&&0&&0&&0\\0&&1&&0&&0\\0&&0&&1&&0\\0&&0&&0&&-1\end{bmatrix}=\left(1\otimes H\right)\text{CNOT}\left(1\otimes H\right)$$

効率的な方式で制御されたユニタリを構成するのは難しい。 最も単純にこれを実装する他の方法は、基本的なゲートの制御された版のデータベースを構築し、 ユニタリ形式で表現された基本的な全てのゲートを、制御されたものに置き換えることである。 これはしばしば無駄な処理であるが、いくつかのゲートを、同じ影響のある制御された制御されたゲートに置き換えるために使用される賢いものであるxxx これらの理由により、私たちは、ナイーブな方法、制御された方法、もしくは最適化された手で書き換えた版を見つけた場合に、ユニタリを制御する版に置き換えたものを置き換える手段を提供する。

ゲートは、古典的な情報を用いて置き換えることが出来る。 例えば古典的な制御されたNOTゲートは、もともとNOTゲートであるが、量子ビットとは対照的に、古典的なビットが1である場合にのみ適用される。 この意味で、古典的な制御されたゲートは、ゲートのコードの1つの分岐内にのみ適用される量子コードのif文と考えることが出来る。

単一量子ビットの場合と同様に、2つの量子ビットの集合は、任意の 4\times 4 のユニタリ行列は任意の精度のゲートの積の近似として捉えることが出来る。 ユニバーサルなゲート集合の例は、Hadamardゲート、Tゲート、そしてCNOTゲートである。 これらのゲートの積を取ることにより、2つの量子ビットの任意のユニタリ行列を近似することが出来る。

複数量子ビットシステム

2量子ビットのケースから、複数の量子ビットを持ったシステムまで拡張することができる。 これは、以下のテンソル積によって表現することができる。 例えば、ビット列 1011001量子コンピュータ上でエンコーディングすることを考える。 これは、以下の用にエンコードすることができる。

$$1011001\equiv\begin{bmatrix}0\\1\end{bmatrix}\otimes\begin{bmatrix}1\\0\end{bmatrix}\otimes\begin{bmatrix}0\\1\end{bmatrix}\otimes\begin{bmatrix}0\\1\end{bmatrix}\otimes\begin{bmatrix}1\\0\end{bmatrix}\otimes\begin{bmatrix}1\\0\end{bmatrix}\otimes\begin{bmatrix}0\\1\end{bmatrix}$$

量子ゲートは、まったく同様な動きをする。 例えば最初の量子ビットX ゲートを適用し、2つ目と3つ目の量子ビットの間にCNOTゲートを適用したいと考えたときに、以下のように表現することができる。

$$\left(X\otimes\text{CNOT}_{12}\otimes 1\otimes 1\otimes 1\right)\begin{bmatrix}0\\1\end{bmatrix}\otimes\begin{bmatrix}1\\0\end{bmatrix}\otimes\begin{bmatrix}0\\1\end{bmatrix}\otimes\begin{bmatrix}0\\1\end{bmatrix}\otimes\begin{bmatrix}1\\0\end{bmatrix}\otimes\begin{bmatrix}1\\0\end{bmatrix}\otimes\begin{bmatrix}0\\1\end{bmatrix}\equiv 0011001$$

多くの量子ビットシステムでは、量子コンピュータのために、一時的なメモリとして量子ビットを割り当てたり、解放したりする。 このような量子ビットは「補助量子ビット」と呼ばれる。 デフォルトでは、量子ボットの状態は e_0 で初期化され、割り当てられた状態である。 また、量子ビットが解放される前に、e_0 が設定される。 この仮定は重要である。なぜなら、補助量子ビットが他の量子ビットレジスタと絡み合って、それが解放されたときに、解放されたプロセスが補助量子ビットを損傷するからである。 このような理由から、私たちは常にこのような量子ビットが解放される前に、初期状態に戻されると仮定する。

最後に、ユニバーサルな2量子ビット量子コンピュータのために、私たちのゲート集合に新しいゲートを追加する必要が生じても、複数量子ビットの場合には新しいゲートを挿入する必要がない。 複数な量子ビットにおいて、H,T およびCNOTゲートによってユニバーサルなゲートを構成する。 なぜならば、任意の一般的なユニタリ変換は2つの量子ビットの回転によって破壊されるからである。 2量子ビットのために作られた理論を活用することができ、複数量子ビットのときにも、この理論を使うことができるのである。

これまで使用してきた線形代数表記は、確かに複数量子ビットの状態を記述するために使用することが出来るが状態のサイズを大きくするにつれてますます煩雑になる。 例えば、7ビット長の縦ベクトルでは、128次元のベクトルとなり、これまでに説明するために利用した表現では非常に煩雑になる。 このような理由から、私たちは量子コンピューティングにおいて高次元のベクトルを記述するための簡潔な表現について紹介する。

追記

CNOTゲートについて (2018/02/14)

CNOTゲートについて何を表現しているのか全く理解できていなかったのだが、要するに2つのビットa,bにおいて、

  • a が 0 ならば標的ビットbはそのまま
  • a が 1 ならば標的ビットを反転する

という意味をなしており、だから制御NOTと呼ばれるのか。行列積の意味もやっと理解できた。

以下の資料がとっても参考になる。

https://www.appi.keio.ac.jp/Itoh_group/abe/pdf/ap2016_4.pdf

f:id:msyksphinz:20180214011019p:plain
図. CNOTの意味。上記資料より抜粋。

関連記事