人工知能と量子コンピュータ
2018/11/19 「人工知能と量子コンピュータ -- NP-完全問題とその含意」概説
量子コンピュータが、人間の認識の「限界」をどのように拡大するかは、人工知能の未来を考える上で、重要な問題です。
BQP（量子コンピュータで多項式時間で解ける問題のクラス）が、P（古典的コンピュータで多項式時間で解ける問題のクラス）を完全に包含していることの発見と、その応用としてのShorの素因数分解アルゴリズムの発見は、今なお、量子複雑性理論と量子アルゴリズムの金字塔です。
残念なことに、多くの数学者は、複雑性の階層の中のNP完全のクラスは、BQPに含まれないだろうと考えています。
ただ、NP完全の問題に、量子コンピュータが、「近似的」に取り組むことは可能です。講演では、こうした「量子最適化」と呼ばれる問題群（QAOAあるいはVQE）の取り組みを紹介しようと思います。
新しい量子アルゴリズムの発展はめざましいものがあるのですが、講演では、もう一つのトピックとして、これらの取り組みで多く利用されている、QRAM（量子ランダムアクセスメモリー）というアーキテクチャーを紹介します。
資料の構成
Part INP-完全問題とその含意
- 人間と機械の「認識可能性」の認識の拡大
- NP-完全問題 手におえない問題の存在
- Cook-Levin Theorem: SATはNP完全である
- Karp: 多項式時間で還元可能なNP完全問題
- Clique 問題
- Graph Coloring 問題
- Hamiltonian Path 問題
- 実際に実装されているNP-完全問題のプログラム
- 量子断熱コンピュータとNP-完全問題
- 量子断熱コンピュータと量子ゲート型コンピュータとの「等価性」
Part II広がる量子アルゴリズムの世界-- BQP-完全問題とQRAM
- 量子組み合わせ最適化 QAOAとVQE
- 量子アニーリング
- 量子ディープラーニング
- QRAMと量子逆行列変換 HHLアルゴリズム
- QRAMとは何か？
- 半正定値プログラミング
- 量子リコメンデーション
