訳者前書き

この記事はStephen Jordan氏によって作成され運営されているWebサイトQuantum Algorithm Zooを、運営者の許可を得て日本語訳したものである。Quantum Algorithm Zooは現在知られている古典アルゴリズムより高速な量子アルゴリズムをまとめたWebページで、2018年2月現在60個のアルゴリズムが紹介されている。この翻訳記事は2018年1月18日でNISTにおいて公開されていたバージョンをもとに作られている。

本記事は以下のの三つ記事に分かれている。

• 代数アルゴリズム、数論アルゴリズム
• オラクルアルゴリズム
• 近似アルゴリズム、シミュレーションアルゴリズム

著者(運営者のStephen Jordan氏)について

• 著者：Stephen Jordan

• 所属：Applied and Computational Mathematics Division, NIST (アメリカ国立標準技術研究所)

• 最終更新日時：2018年1月18日

• 作成日時：2011年4月22日

QuICSも参照

用語について

問題のサイズを $n$ とする。既知の古典アルゴリズムで最良の実行時間 $C(n)$ と量子アルゴリズムでの最良の実行時間 $Q(n)$ について、 $C = 2^{\Omega(Q^{\alpha})}$ を満たす正定数 $\alpha$ があるとき、量子計算機による計算の加速は超多項式的(Superpolynomial)と呼ぶ。そうでない場合は、量子計算機による計算の加速は多項式的(Polynomial)であると呼ぶ。説明では、オーダーを表すランダウ記法 ( $O,\Omega,\Theta,\tilde{O}$,... ) が登場するが、これらの定義についてはWikipediaの記事を参照すること。