基礎から学ぶ量子計算

丁寧な解説と豊富な演習問題により、量子計算のアルゴリズムと計算量理論について一から理解できる。
量子計算のアルゴリズムと計算量理論について、一からわかりやすく解説した書籍です。
現在、大きな注目を集めている量子コンピュータは、量子計算の計算モデルを採用することで、従来のコンピュータや人手による計算 (古典計算) と比べて、指数関数的な高速化を実現します。これは、「古典計算は量子計算で効率的に実行可能である」という事実にもとづくものです。
したがって、量子コンピュータを理解し、使いこなすには、重ね合わせの原理とエンタングルメントをはじめとした量子計算のアルゴリズムと計算量理論をひと通り理解する必要があります。
本書は、線形代数と離散数学の基本的な知識のみを前提として、量子計算の原理について初学者向けに丁寧な解説を行っています。数多くの例題と演習問題を収載しており、読者自ら手を動かしながら学ぶことができます。
第 1 章 計算理論の基礎事項
第 2 章 ブラケット記法と量子計算でおなじみの行列
第 3 章 量子情報の基礎
第 4 章 量子回路
第 5 章 量子アルゴリズム
第 6 章 量子計算量クラス

量子コンピューターがなぜ一部の問題で古典計算機を大きく上回り得るのかを、雰囲気の説明ではなくアルゴリズムと計算量理論の言葉で理解したい人のための教科書です。『基礎から学ぶ量子計算』は西村 治道 著、オーム社から 2022 年 11 月 18 日に発売された単著で、副題は「アルゴリズムと計算量理論」です。版元は線形代数と離散数学の基本的な知識のみを前提として、量子計算の原理を初学者向けに丁寧に解説し、数多くの例題と演習問題で読者自ら手を動かしながら学べる本と紹介しています。

全 6 章の構成、計算理論の基礎事項から量子計算量クラスまで

章立ては第 1 章「計算理論の基礎事項」から第 6 章「量子計算量クラス」までの 6 章と、付録 3 本です。第 1 章は文字列と計算問題、ブール回路、計算量クラスといった古典側の準備にあてられ、第 2 章「ブラケット記法と量子計算でおなじみの行列」でベクトルと行列の道具立てを揃えます。第 3 章「量子情報の基礎」は量子ビットと量子状態に始まり、複数の量子ビット、観測量、混合状態、POVM、発展的な概念へと進みます。第 4 章「量子回路」では基本ゲート、古典計算と量子計算の比較、万能量子ゲート集合などを扱い、第 5 章「量子アルゴリズム」は Shor と Grover のアルゴリズムが扱う問題の整理から入って、Deutsch-Jozsa、Grover、Simon の各アルゴリズム、位数発見アルゴリズム、通信を含む計算問題に対する量子プロトコル、そのほかの量子アルゴリズムを順に取り上げます。付録は離散数学の補足、計算量理論の補足、量子フーリエ変換に対する回路の正当性の 3 本です。

量子の速さを計算量で測るという視点

量子計算の解説でよく聞く「重ね合わせですべての答えを同時に試すから速い」という説明は、測定すると状態が確率的に 1 つへ定まることを無視しており、正確ではありません。実際の高速化は、重ね合わせとエンタングルメントを使ったうえで、干渉によって正しい答えの振幅を強め、誤った答えの振幅を打ち消すように回路を設計できた問題でだけ起こります。その効果の大きさも問題ごとに違い、素因数分解では Shor のアルゴリズムが多項式時間で解を与え、古典計算機で知られている最良の解法を大きく上回る一方、Grover のアルゴリズムによる探索の高速化は要素数の平方根のオーダーにとどまります。こうした違いを正確に語るには、計算量 の考え方と、P や NP といった計算量クラスの語彙が欠かせません。本書は第 6 章で、量子コンピューター で効率よく解ける問題のクラスとして、P の量子版としての BQP、NP の量子版としての QMA、量子対話型証明を取り上げています。

中級の若手技術者と大学院生に向く理由と前提知識

版元がおすすめの読者として挙げるのは、システムエンジニアリングや情報工学の若手技術者 / 研究者と、情報工学系の大学院生で、段の表示は中級です。前提は線形代数と離散数学の基本とされ、本文はベクトル空間、行列の積、固有値といった操作と、計算量クラスの定義を使って進みます。逆に、量子コンピューターの産業動向やクラウドで提供される実機の使い方、特定の開発キットでのプログラミングを知りたい人には、本書の目次はその用途に沿っていません。目次に、実機の操作や開発キットでのプログラミングを扱う章はありません。

量子アルゴリズムの論文や解説を読んで、計算量の主張がどこまで成り立つのかを自分で判断できるようになりたい人にとって、本書は計算理論の準備から量子計算量クラスまでを一冊の流れで追える教科書です。版元の紹介どおり、本書には数多くの例題と演習問題が収められています。