第2章 量子アルゴリズム入門

量子コンピュータは、量子力学的な重ね合わせによって、\(n\)個の量子ビットを用いて\(2^n\)個の状態を同時に処理できる。しかし、これだけでは「計算が速い」ということにはならない。なぜなら、計算終了後に結果を観測する際に、\(2^n\)個の状態の内どれか一つがランダムに得られるのみだからである。したがって、欲しい答えが高確率で得られるように設計された、量子コンピュータ専用のアルゴリズムが不可欠である。そのようなアルゴリズムを量子アルゴリズムと呼ぶ。量子アルゴリズムの有名な例として、Shorの素因数分解アルゴリズム、Groverの探索アルゴリズム等がある。

この章では、量子アルゴリズムの初歩を学んでいく。まず、量子アルゴリズムは、この数年で実現される量子コンピュータ=「NISQデバイス」で実行可能(と思われる)なアルゴリズムと、十年後以降に実現されるであろう誤り訂正ありの真の量子コンピュータでしか実行が難しいアルゴリズムとの2種類に大別されることを見る。次に、アダマールテストという最も簡単な量子アルゴリズムを学ぶ。その後、量子フーリエ変換、その発展である位相推定アルゴリズムという、量子コンピュータの応用を考える上で最も重要な量子アルゴリズムについて学ぶ。(ちなみに、量子フーリエ変換・位相推定アルゴリズム共に、実用的なサイズの問題をNISQマシンで実行することは難しいと考えられているので、long-termアルゴリズムに分類される)