量子コンピュータの基礎

量子コンピュータの基礎

執筆済 量子計算

計算の流れ#

  1. 初期化 — 全量子ビットを |0⟩⊗n に用意する
  2. 回路の適用 — ユニタリゲートを順に作用させる
  3. 測定 — 計算基底で測り、古典ビット列を得る
  4. 繰り返し — 確率的なので、多数回実行して統計を取る

何が高速化を生むのか#

干渉。2n 個の振幅を持てることそのものではない。

測定で取り出せるのは n ビットだけ（Holevo 限界）なので、 「全部を並列に計算して全部読む」ことはできない。

アルゴリズムの仕事は 誤った答えの振幅を打ち消し、正しい答えの振幅を強めること。

アルゴリズム 干渉の使い方
Grover 反転と拡散で解の振幅を増幅
Shor 周期性をQFTで抽出

万能性#

任意のユニタリは、 1 量子ビットゲート + CNOT の組み合わせで 任意の精度で近似できる（万能ゲートセット）。

有限のゲートセット（Clifford + T など）でも Solovay-Kitaev の定理により効率的に近似できる。 つまり有限種類のゲートで何でも作れる。

古典計算を包含する#

Toffoli ゲートで古典の論理演算を可逆に実現できるので、 量子計算機は古典計算機ができることをすべてできる。 問題は速さであって、可能性ではない。

参考文献#