On Quantum Versions of Record-Breaking Algorithms for SAT

E. Dantsin, V. Kreinovich, A. Wolpert
SIGACT News, 36(4), pages 103-108, December 2005.

Groverのアルゴリズムをそのまま使えば量子的に1.414^nぐらいの時間でSATが解ける，と．
なるほど．
この論文の目的はそれを他のSATアルゴリズムに適用するということ．
指数時間アルゴリズムの研究するには，量子アルゴリズムも視野にいれないといけない気がしてきた．
Parametricサーチが並列アルゴリズムの結果を普通のアルゴリズムに応用する道を開いたように，ある手法で量子アルゴリズムをうまく普通のアルゴリズムに応用する道が開けるかもしれない．