量子コンピュータと量子通信 2-量子コンピュータとアルゴリズムー

量子情報理論の世界的な定本の待望の翻訳版!
研究開発が活発な量子コンピュータや量子暗号、量子通信を実現するための量子情報理論についての世界的な定本である"Quantum Computation and Quantum Information"の翻訳版、第 2 巻目。
量子コンピュータの仕組みからその計算アルゴリズムまで、量子コンピュータを実現するための理論と技術をわかりやすく解説している。

量子コンピューターが古典的な計算機より速く解ける問題があるのはなぜか。その答えを回路とアルゴリズムの水準で示す理論書が『量子コンピュータと量子通信 Ⅱ』 (Michael A. Nielsen、Isaac L. Chuang 著、木村 達也 訳、オーム社、2005 年 1 月 20 日発売) です。版元が「量子情報理論についての世界的な定本」と紹介する Quantum Computation and Quantum Information の翻訳版の第 2 巻目で、副題は「量子コンピュータとアルゴリズム」です。版元の紹介文は、量子コンピューターの仕組みからその計算アルゴリズムまで、量子コンピューターを実現するための理論と技術を解説すると案内しています。

第 II 部「量子計算」の 4 章と付録 4 本の構成

この巻に収められているのは第 II 部「量子計算」です。第 4 章「量子回路」、第 5 章「量子 Fourier 変換とその応用」、第 6 章「量子探索アルゴリズム」、第 7 章「量子コンピュータ: 物理的実現法」の 4 章に、付録 B「群論」、付録 C「Solovay-Kitaev の定理」、付録 D「整数論」と、公開鍵暗号と RSA を扱う付録 E が続きます。章番号は第 4 章から、付録は B から始まるので、第 1 章から第 3 章と付録 A はこの巻には含まれていません。第 4 章は単一 q ビット演算、制御演算、測定、普遍的量子ゲートと進み、量子システムのシミュレーションで締めくくられます。第 5 章は位相推定を経て位数発見と素因数分解への応用に至り、第 6 章は量子計数、NP 完全問題の解の高速化、最適な探索アルゴリズム、ブラックボックス・アルゴリズムの限界までを扱います。第 7 章の節は指導原理、量子計算の条件、調和振動子、光子、光共振器量子電気力学、イオン・トラップ、核磁気共鳴、他の実現法という並びです。

干渉で答えを取り出す計算と、素因数分解が持つ意味

量子コンピューター の速さは、多数の状態を同時に重ね合わせられることだけでは説明できません。重ね合わせたまま測定すれば、得られるのはでたらめな 1 つの結果です。有用な計算にするには、正しい答えにつながる振幅どうしを強め合わせ、それ以外を打ち消し合わせるようにゲートを並べる必要があり、この設計が量子アルゴリズムの難しさの中心にあります。周期を持つ関数の周期を干渉で浮かび上がらせる手法は、Shor のアルゴリズムとして知られる素因数分解の高速化の土台になっています。通信を第三者に読めなくする 暗号化 の方式には、大きな数の素因数分解が古典計算機では現実的な時間で終わらないことを安全性の拠り所にするものがあり、量子計算の理論が暗号の研究者から注目される理由もここにあります。整数論と RSA の付録が同じ巻に置かれているのは、こうした応用を読むための道具を手元にそろえる意味を持ちます。

探索の問題でも事情は似ています。印の付いていない候補の中から条件を満たすものを古典的な アルゴリズム で探すと、平均して候補の半分を調べる必要があります。量子探索はこれを候補数の平方根に比例する回数まで減らせますが、指数的な高速化ではありません。どこまで速くできてどこから先は速くできないのかという限界の議論まで含めて読むと、量子計算で得をする問題とそうでない問題の見分けが付くようになります。

中級の読者に向けた理論書、前提知識と向かない目的

版元はこの本を、情報科学 / 情報工学 / 通信 / 電子分野の学生や研究者 / 教員と、情報通信関連のメーカーの技術者にすすめており、おすすめの段は中級としています。状態ベクトル、ユニタリ行列、テンソル積といった線形代数と量子力学の基本を押さえていることが前提になり、第 4 章より前の章がこの巻に無いことも踏まえておく必要があります。量子プログラミング用のソフトウェア開発キットの使い方を知りたい場合は、目次にその種の項目が無いので別の本が向いています。物理的実現法の章は 2005 年の刊行時点の整理で、節題には超伝導回路を用いる方式の名がありません。量子誤り訂正や量子通信路を学びたい場合も、この巻の目次にはそれらの章が無いので、シリーズの他の巻の目次を版元のページで確かめてから選ぶのが確実です。

量子回路の組み立て方から素因数分解と探索のアルゴリズムまでを、証明を含む理論として一度通して理解しておきたい人にとって、この巻は量子計算の論文や専門書を読むための基礎を固める一冊になります。線形代数の準備を整えたうえで、第 4 章の量子回路から順に手を動かして読み進めると、後の章の議論が追いやすくなります。