※この商品はタブレットなど大きいディスプレイを備えた端末で読むことに適しています。また、文字だけを拡大することや、文字列のハイライト、検索、辞書の参照、引用などの機能が使用できません。

※この電子書籍は紙版書籍のページデザインで制作した固定レイアウトです。

丁寧な解説と豊富な演習問題により、量子計算のアルゴリズムと計算量理論について一から理解できる
量子計算のアルゴリズムと計算量理論について、一からわかりやすく解説した書籍です。
現在、大きな注目を集めている量子コンピュータによる計算（量子計算）は、従来のコンピュータによる計算（古典計算）と比べて、いわゆる指数関数的な高速化を実現することがあります。
その一方で、この高速化は量子力学の基礎原理をもとにしており、アルゴリズムと計算量理論の分野の言葉で記述されるものです。したがって、この高速化の現象を正しく理解するには、量子力学特有の重ね合わせの原理とエンタングルメントをはじめとした量子計算のアルゴリズム、および、計算量理論をひと通り理解する必要があります。
本書は、線形代数と離散数学の基本的な知識のみを前提として、量子計算の原理について初学者向けに丁寧な解説を行っています。
数多くの例題と演習問題を収載しており、読者自ら手を動かしながら学ぶことができます。

第1章　計算理論の基礎事項
1.1　文字列，計算問題
1.2　ブール回路
1.3　二進列に対する演算
1.4　計算量クラス
1.4.1　P, NP, EXP
1.4.2　多項式時間帰着とNP完全問題
1.4.3　オラクル
1.4.4　乱択アルゴリズムと計算量クラス

第2章　ブラケット記法と量子計算でおなじみの行列
2.1　ベクトル
2.2　行　列
2.3　量子計算でよく出現する行列
2.3.1　ユニタリ行列
2.3.2　正規行列，エルミート行列
2.3.3　射影行列
2.3.4　半正定値行列

第3章　量子情報の基礎
3.1　量子ビット，量子状態
3.1.1　量子ビット，量子状態の測定
3.1.2　量子ビットの幾何的描像
3.1.3　量子ビット，量子状態の時間発展
3.1.4　量子ランダムアクセス符号
3.1.5　量子鍵配送
3.2　複数の量子ビット
3.2.1　テンソル積
3.2.2　複数の量子ビットからなる量子状態
3.2.3　複数の量子ビットの時間発展および測定
3.2.4　部分系の測定
3.2.5　CHSHゲーム
3.2.6　量子テレポーテーション
3.3　観測量
3.4　混合状態
3.4.1　1量子ビットと密度行列
3.4.2　部分トレースと混合状態
3.5　POVM
3.5.1　3ビット量子ランダムアクセス符号
3.5.2　2値POVM の実現方法
3.6　発展的な概念
3.6.1　トレース保存完全正値写像
3.6.2　近似と距離

第4章　量子回路
4.1　基本ゲート，量子回路
4.2　古典計算vs量子計算
4.3　量子計算の計算木
4.4　万能量子ゲート集合
4.5　よく使用される量子回路
4.5.1　量子回路のワイヤの交換
4.5.2　量子アダマール変換と一様重ね合わせ状態の生成
4.5.3　量子フーリエ変換
4.5.4　アダマールテスト
4.5.5　SWAPテスト
4.6　空間的制約が課された量子回路

第5章　量子アルゴリズム
5.1　Deutsch?Jozsaの量子アルゴリズム
5.2　Groverのアルゴリズム
5.2.1　量子計算に古典アルゴリズムを組み込む
5.2.2　量子振幅増幅
5.3　Simonのアルゴリズム
5.4　位数発見アルゴリズム
5.5　量子特有の問題に対する量子アルゴリズム
5.5.1　位相推定
5.5.2　量子シミュレーション
5.6　その他の量子アルゴリズム
5.7　通信を含む計算問題に対する量子プロトコル

第6章　量子計算量クラス
6.1　Pの量子版：BQP
6.1.1　BQPとNPの関係
6.1.2　BQPを含む古典計算量クラス
6.2　NPの量子版：QMA
6.3　量子対話型証明
6.4　量子多証明者対話型証明

付録
A.1　群と体
A.2　オーダ記法
A.3　チューリング機械
A.4　非決定性チューリング機械
A.5　確率チューリング機械
A.6　PSPACEとEXP