量子アルゴリズムの基礎

共通の骨格#

ほとんどの量子アルゴリズムは 3 段階でできている。

1. 重ね合わせを作る — アダマールで一様重ね合わせ
2. 位相に情報を書き込む — オラクル、あるいは問題ハミルトニアン
3. 干渉させて読み出す — QFT、拡散変換など

2 で「答えを位相として埋め込み」、3 で「位相の情報を振幅に変換する」。 この往復が量子アルゴリズムの基本設計。

位相キックバック#

制御ユニタリの固有状態を標的にすると、 位相が制御ビット側に現れる。

$$|c⟩|u⟩\to e^{2\pi i\phi c}|c⟩|u⟩$$

量子位相推定も、Deutsch-Jozsa も、 Shor もこの仕掛けを使っている。 知りたい量を位相に載せるのが定石。

オラクル#

「関数 $f$ を計算するブラックボックス」として与えられる操作。

$$U_f|x⟩|y⟩=|x⟩|y\oplus ︎f(x)⟩$$

理論的な計算量はオラクルの呼び出し回数で測る（クエリ計算量）。 ただし実際の問題ではオラクルを回路として実装する必要があり、 そのコストが無視できないことが多い。 理論上の加速が実用に直結しない主要因のひとつ。

限界#

• 構造の無い探索は $\mathrm{\Omega }(\sqrt{N})$ が下限（BBBV 定理）。 Grover はこの下限に到達しており、これ以上速くできない
• NP 完全問題が量子で多項式時間になるとは考えられていない

参考文献#

• Michael A. Nielsen, Isaac L. Chuang. Quantum Computation and Quantum Information, 10th Anniversary Edition. Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511976667
• Charles H. Bennett et al. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing 26(5), 1997. https://doi.org/10.1137/S0097539796300933
• Ashley Montanaro. Quantum algorithms: an overview. npj Quantum Information 2, 2016. https://doi.org/10.1038/npjqi.2015.23