量子アルゴリズム

量子アルゴリズム

量子計算機で動かすアルゴリズム。指数的加速が確立しているのは構造のある限られた問題だけ。

執筆済 量子アルゴリズム

量子計算機で動かすアルゴリズム。

高速化の型#

量子アルゴリズムの加速は、いくつかの型に分類できる。

型 加速 例
指数的 𝒪(2n)→poly(n) Shor、Hamiltonian simulation
二次 𝒪(N)→𝒪(N) Grover
不明・ヒューリスティック 未確立 QAOA、VQE

指数的加速が確立しているのは限られた問題だけ。 どんな問題でも速くなるわけではない。

何が加速を生むのか#

重ね合わせそのものではなく、 干渉によって誤った答えの振幅を打ち消すこと。

Shor が速いのは、周期性という構造を 量子フーリエ変換で 抽出できるから。構造の無い問題では Grover の二次加速が上限になる。

NISQ 期のアルゴリズム#

深い回路が実行できないため、 浅い回路と古典最適化を組み合わせる 変分アルゴリズムが中心になっている。 VQE と QAOA が代表。

これらは理論的な加速の保証が無いヒューリスティックである点が、 Shor や Grover と決定的に違う。

参考文献#

この階層のノート

量子アルゴリズムの基礎 Groverアルゴリズム Shorアルゴリズム 量子フーリエ変換 量子位相推定 VQE 7 / 7 ハミルトニアンの最小固有値を、浅い量子回路と古典最適化の往復で求める手法。NISQ 期の主力。 QAOA 量子ウォーク HHL 量子微分方程式アルゴリズム