Ch.2_量子計算基礎｜『量子情報科学入門』読解メモ #2

#1では「量子情報科学入門」を読み始めた経緯と、1章として設けられている『量子ビット系の量子力学』の読解メモをまとめました。

#2では2章の量子計算基礎についてまとめたいと思います。
以下目次になります。

1. 第2章_量子計算基礎
1.1 「計算」とは何か？(2.1)
1.2 情報科学で必須となる数学記号・記法(2.2)
1.3 古典回路モデル(2.3)
1.4 量子回路モデル(2.4)
2. まとめ

1. 第2章_量子計算基礎

0.5節に戻ると、2章では計算機科学の基礎に触れた後に古典的な論理演算との関係から後に現れる重要な量子回路について説明するとされています。後の章の計算のベースとなるので読んでおくことが推奨されています。が、詳しいところは実際に出てきてからの方がイメージがつきやすいので、古典回路と量子回路において具体的な計算が記述されている2.3、2.4についてはざっと大枠をつかんで一旦読み流して後から戻ってくる方が読みやすいのではと思います。

1.1 「計算」とは何か？(2.1)

2.1節では「計算」という行為を数理科学的にどう扱うかということで理論計算機科学について言及されています。「抽象的には計算とは単純な基本演算の組み合わせにより入力された情報を変形し、その結果を出力する操作である」とされており、素数判定アルゴリズムを元に色々と説明されています。
素数判定アルゴリズムのような一連の計算の手続きは何らかのプログラミング言語を知っていればすぐに実装できる簡単なもので、条件分岐や加減剰余などの単純な基本演算を組み合わせることで実現可能であるとされています。このようにあらかじめ決められた単純な基本演算の組み合わせで計算を実現する手続きを一般にアルゴリズム(algorithm)と呼ぶとされています。ちなみにプログラミングの初心者向けの問題としてよくFizzBuzzがあがりますが、FizzBuzz問題はここで言及されている基本演算の大部分を用いているためちゃんとプログラムを組めるかどうかを判断するには最適な問題です。FizzBuzzについては下記にまとめていますので、復習したい方は下記をご確認いただけたらと思います。

本文に戻りますが、このアルゴリズムを考える際に効率の良さの議論が必要となってくるのですが、この際の指標としては一般的に計算量(complexity)と呼ばれるものを用います。計算量を大雑把にいうと計算に必要十分な基本演算の回数であるとされています。素数判定アルゴリズムについては、nビットを考えた際に最も簡易的な考え方のアルゴリズムを用いた場合ではのオーダーとされています。が、これは工夫次第でいかほどか速くなり、多項式時間アルゴリズムまで落とせると本文内で言及されています（各論なので読解メモとしては飛ばします）。
「上記では通常の計算機上で実現される古典計算のみを議論したが、さらにアルゴリズム中で量子力学の原理を取り入れた基本演算が可能な計算を量子計算と呼ぶ」とされており、今後話をそちらの方に展開していくにあたっての前振りがされています。

また、以降の節の話の展開についてもまとめられており、2.2節では本で取り扱われている範囲内での情報科学全般において必須となる数学記号についてのまとめ、2.3節では古典計算モデルとしての古典回路の解説、2.4節では量子情報の媒体である量子ビットを扱う量子計算モデルである量子回路について取り扱われているなどとまとめられています。

1.2 情報科学で必須となる数学記号・記法(2.2)

まず実数を整数に対応づける関数として、床関数(floor function)と天井関数(ceiling function)が導入されています。それぞれ一言でいうと床関数はx以下の最大の整数、天井関数はx以上の最小の整数です。また、対数も重要な役割を果たすということで導入されていますが、底が2であることに注意です。これは1ビットの単位として0と1の二種類の数字を扱うからです。また、計算量の議論にあたって重要な役割を果たすオーダー記法(order notation)について導入されているので、これはしっかり抑えておくのが良いと思われます。上界を与えるO(g(n))と下界を与えるΩ(g(n))が今後の話の展開に色々と出てきそうです。

2.2はどちらかというと数学記号や記法の導入なので、さらっと把握できる話ではないかと思われました。

1.3 古典回路モデル(2.3)

2.3ではアルゴリズムを数理科学的に取り扱うにあたって、計算モデルの設定を行なっています。2.3節では理論的な取り扱いが比較的しやすい代表的な計算モデルである古典回路(classical circuit)モデルについて紹介されています。古典回路は予め決められた数種類の基本素子から構成されるとされており、表2.1で言及されているAND素子、OR素子、NOT素子の組み合わせで諸々の演算を定義しています。
具体的な問題の例として、偶奇判定問題(parity problem)が挙げられており、排他的論理和から基本素子まで式を展開しています。

ここまでの流れがわかればざっと雰囲気はわかると思うので、一旦残りは読み流して必要に応じて戻るで問題ないかと思います。（古典回路モデルはこの本のテーマではないため、戻る必要はないかもしれません）

1.4 量子回路モデル(2.4)

2.4節では2.3の古典回路モデルで行なっていた計算を量子力学に基づく概念へ拡張することで、より強力な計算を実現するとされています。それにあたって、2.4では量子計算の計算モデルである量子回路(quantum circuit)について解説がなされています。
量子計算において量子アルゴリズムが基本的に許される操作は測定及びユニタリ変換のいずれかであるとされているので、手始めにユニタリ行列の一例であるPauli行列やHadamard変換(Hadamard transform)について諸々言及されています。
大体雰囲気はつかめたので一旦残りは飛ばしました。（後の章で言及されそうな雰囲気があるので、戻ってきた際に追記する可能性が高いです。）

2. まとめ

一旦雰囲気をつかんだだけなのですが、詳細は勉強会で意見交換したり後ろの章から戻ってきたりの際に読めば十分そうなのでそうしたいと思います。