藤井啓祐 「驚異の量子コンピュータ」ﾒﾓ
藤井啓祐 「驚異の量子コンピュータ」ﾒﾓ
第Ⅱ部 量子コンピュータの仕組み
第5章 量子コンピュータのからくり
----------------------------------------------------------------------------------
【まとめ】
・量子コンピュータは、量子ビットに対し量子演算を行う。
・重ね合わせ状態を量子ビットで物理的に表現し、物理法則に従い自然に処理可能。
・量子コンピュータは実数・複素数の重みをもつ可能性の世界へと計算を拡張。
・３種類の演算を組み合わせ、量子力学で許された全ての計算を実行可能。
⇒万能量子コンピュータ（宇宙最強のコンピュータ）
・並列性と干渉による確率の増幅を利用することで、量子コンピュータの高速性を享受可能。
・素因数分解問題を量子コンピュータが効率よく解けることは、拡張チャーチ＝チューリングのテーゼに反する帰結。
・量子という観点から考え直すことで、優秀な古典アルゴリズムを見つけることができる。
----------------------------------------------------------------------------------
◎量子コンピュータへの拡張
・量子コンピュータは、情報を量子ビットで表現する。
・量子ビットに対し量子演算を行うことで計算を行う。
・量子の世界では状態は確率ではなく、確率振幅で書き表す。
・０状態の量子ビットを準備する。
・量子演算（９０度回す操作）で０と１の重ね合わせ状態の量子ビットを作る。
・この段階では０か１か決まっていない。
・再び量子演算を作用させる。
・重ね合わせの場合、０がひっくり返り、重ね合わせのない１状態になる。
・この状態は重ね合わせっておらず、何回測定しても１状態を得る。
・一度重ね合わせとして分岐した可能性が、再び集まり一つの状態になることが可能。
→干渉と呼ぶ
・可能性を打ち消したり、強め合う干渉効果を用いることで答えに可能性を集める操作が、量子コンピュータの高速性に重要な役割を担う。
◎たくさんの量子ビット
・量子コンピュータは、たくさんの量子ビットがある場合に威力を発揮する。
＜古典ビット場合＞
・Ｎビットからなるビット列は、０や１をＮ個並べて書き表せる。
＜量子ビットの場合＞
・二つの量子ビットがある場合を考える。
・箱が二つあり、それぞれに粒子が一つずつ入っている状況。
・箱の中心に壁を作ると、それぞれの箱で全４パターンの可能性が重ね合わさる。（それぞれの箱の右側と左側に粒子がいる状態）
・二つのビットがとりうるすべてのパターン、００、０１、１０、１１の重ね合わせが許される。
・それぞれのパターンの可能性の大きさは、４個の確率振幅を用いる。・一般的にＮ個の量子ビットがあった場合に拡張する。
・Ｎビットのビット列は、０から１までの２^Ｎ個のパターンをとりうる。
・どのビット列が、どの程度の可能性で重ね合わさっているかを示す確率振幅を、２^Ｎ個のすべてのパターンに対して複素数を用いて表現する
。
◎量子ビットを古典コンピュータで表現すると？
・重ね合わせの強さを決める確率振幅のパラメータ数は、量子ビット数Ｎに対して指数関数的に増える。
（古典ビットではＮビットに対してＮ個の数字でよい）
・量子系のふるまいを古典コンピュータ上でシミュレーションするには、粒子数に対して指数関数的にたくさんのメモリが必要。
・量子コンピュータでは、確率振幅も含めて複雑なパターンの重ね合わせ状態を、そのまま量子ビットを用いて物理的に表現可能。
・それら量子ビットを物理法則に従い自然に処理できる。
◎０と１だけの世界から解き放たれたコンピュータ
・量子コンピュータは、１か０だけの可能性の世界から、実数もしくは複素数の重みをもつ可能性の世界へと計算を拡張したもの。
・重ね合わせ状態を作り出すアダマール演算は、量子特有の量子コンピュータの基本演算として利用されている。
・可逆な足し算（ＸＯＲ）はＣＮＯＴ演算と呼ばれ、重要な基本演算の一つ。
・量子コンピュータのＸＯＲは、重ね合わせのまま、０の場合と１の場合に分岐して並列に処理できる。
・アダマール演算とＣＮＯＴ演算を用いてエンタングルした状態を作ることができる。
・複素数成分をもつ行列を導入し、位相回転演算も可能。
・確率振幅のみを、大きさを変えずに複素平面上の位相を回転する。
・３種類の演算（アダマール演算、ＣＮＯＴ演算、位相回転演算）を組み合わせ、量子力学で許されたどのような計算も実行可能。
・これらは量子コンピュータのための万能演算。
・これらを実行できる量子コンピュータを、万能量子コンピュータと呼ぶ。
・確率振幅の波を分けたりひっくり返したりねじったりすることで、どのような複雑な波も作れる。
・万能量子コンピュータは、宇宙最強のコンピュータ。
・基本的な演算素子（ゲート）で構成している場合、ゲート型、回路型の量子コンピュータと呼ぶ。
・測定型量子コンピュータや断熱型量子コンピュータなど様々なものを研究中。
◎並列性と干渉
・量子コンピュータが得意とする計算は？
・どのような意味で量子コンピュータは古典コンピュータより速いのか？
・量子ビットはすべてのパターンを同時に計算できるわけではない。
・答えもすべてのパターンの重ね合わせなので、測定すると確率的にどれか一つのパターンに可能性が収縮する。
・可能性は２^Ｎ個のパターンに広がっているので、一つ一つは小さい確率になる。
・量子コンピュータが古典コンピュータよりも速く答えを見つけるためのプロセスは、確率の増幅。
・複素数である確率振幅は、量子演算を経て干渉し、特定の答えに確率を集めることができる場合がある。
・確率の増幅を行うには、確率振幅で状態が記述される量子力学の性質が必須。
・重ね合わせによる並列性と干渉による確率の増幅を利用することで、はじめて量子コンピュータの高速性を享受できる。
◎ショアの素因数分解
・素因数分解問題はスパコンでも解くのが難しい問題の代表格。
・ショアによる素因数分解アルゴリズムの驚異的な点
①暗号の安全性の拠り所としてきた素因数分解問題が、量子コンピュータで簡単に解くことができること。
②チューリングマシンに対し、量的に性能を上回る計算モデルが見つかったこと。
＜チャーチ＝チューリングのテーゼ＞
・チューリングマシンが現実世界で実現しうる最も一般的計算マシン。
・チューリングマシンを基準として計算可能な関数を定義する。
・計算可能性は、計算がいずれ終了し、答えが必ず出るか否かという計算の難しさの”質的側面”をもつ。
・どのくらいの時間で答えをだせるかという、計算の難しさの”量的側面”は考慮しない。
＜拡張チャーチ＝チューリングのテーゼ＞
・計算の難しさの量的側面にチャーチ＝チューリングのテーゼを拡張したもの
・現実世界で実現しうるコンピュータで効率良く解ける問題は、チューリングマシンでも効率よく解くことができる。
・素因数分解問題を量子コンピュータでは効率よく解けるが、チューリングマシンでは効率よく解けない
→拡張チャーチ＝チューリングのテーゼに反する帰結で、大インパクト。
◎量子ビットのいらない量子アルゴリズム
・量子アルゴリズムに問題を適応させるために制約が付く。
・古典アルゴリズムでもこの制約を使うことで高速化できる場合がある。
・量子アルゴリズムを研究することで、有用な古典アルゴリズムを見つけることができる。
・量子という観点から問題やアルゴリズムを考え直すこと、そこに量子でなければ達成できない計算の加速が寄与しているか検討することで、
優秀な古典アルゴリズムを見つけることができる。
