講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編のPDF資料を快適に閲覧・印刷することができます。
セミナーの概要
本セミナーは、「人工知能と量子コンピュータ」という大きな問いのもと、計算複雑性理論の核心である「NP-完全問題」と、それを取り巻く量子アルゴリズムの最前線を一貫した視座から論じた講義です。[p.1, p.2] 講師が出発点に据えるのは、「人工知能にとって最も基本的な問いとは、機械と人間の認識の限界を正確に知ることである」という信念です。[p.2] 1950年代のチャーチ＝チューリングのテーゼによる計算可能性の限界の確立から、1970年代の計算複雑性理論の誕生、1980年代のチャーチ＝チューリング＝ドイッチェのテーゼによる計算可能性概念の物理化、そして1990年代の量子複雑性理論（BQP）の確立へと至る知的系譜が、丁寧にトレースされます。[p.12〜p.16] この歴史的文脈の中で、「NP-完全」という概念の発見が、ゲーデルの不完全性定理が計算可能性理論に与えたのと同質の、根源的なインパクトを持つものとして位置づけられます。[p.2] Part Iでは、1971年のCookによるSATのNP完全性の証明（Cook-Levin定理）、そして1972年のKarpによる21のNP完全問題の体系化を軸に、Clique問題、Graph Coloring問題、Hamiltonian Path問題といった多様な問題が、いかにして一つのアルゴリズムの難しさに帰着されるかという「還元」の論理が展開されます。[p.33, p.68] 量子コンピュータがNP完全問題を解けるという「誤解」を解きほぐすことが、このPartの重要な動機の一つです。[p.4] 量子断熱コンピュータによるNP完全問題への挑戦とその限界についても詳論されます。[p.108〜p.124] Part IIでは、NP完全問題を解けないとしても、量子コンピュータが活躍できる広大なフィールドが存在することが示されます。QAOA・VQEという量子古典ハイブリッドアルゴリズムによる近似最適化、量子アニーリング、量子ディープラーニング、そしてQRAMを基盤とするHHLアルゴリズム（量子逆行列変換）、半正定値プログラミング、量子リコメンデーションシステムという、急速に拡大する量子アルゴリズムの世界が俯瞰されます。[p.142〜p.253] 最終的に講師が注目するのは「BQP完全問題」というコンセプトであり、それを解く量子デバイスを人類が手にする日、人間と機械の認識の限界についての理解は新たな段階に入ると展望されます。[p.5]
講義のロードマップ
ここでは、セミナーの講演資料がどのようなパートから構成されているかを示します。また、それぞれのパートのポイントを紹介します。
■ Part 0: 導入認識の限界という問いの射程
人工知能論の根本問題を「計算の限界」として定式化し、計算可能性理論から量子複雑性理論に至る認識論的発展の地図を提示します。量子コンピュータとNP完全問題についての「よくある誤解」を明示し、本講義全体の問題意識を確立します。[p.2〜p.5]
■ Part I: NP完全問題とその含意
計算複雑性理論の中核概念「NP完全」を、SAT問題を起点に丁寧に構築します。Cook-Levin定理による「あらゆるアルゴリズムは論理式にコード可能」という洞察、KarpによるNP完全問題の体系、そして量子断熱コンピュータによるNP完全問題攻略の試みとその限界が論じられます。[p.29〜p.139]
# セクション1: SAT問題とCook-Levin定理
充足可能性問題（SAT）を丁寧に定義し、それがNP完全であることを証明したCook-Levin定理の証明の骨格を解説します。「全てのNP問題はSATに多項式時間で還元できる」という命題の巨大なインパクトが示されます。[p.38〜p.56]
■ Part II: 広がる量子アルゴリズムの世界BQP完全問題とQRAM
NP完全問題の攻略こそ叶わないものの、量子コンピュータが古典的コンピュータを指数関数的に上回る可能性を持つ応用領域は急速に広がっています。Preskillの講演をベースに、QAOA/VQE・量子アニーリング・量子ディープラーニング・HHLアルゴリズム・半正定値プログラミング・量子リコメンデーションという多様なフロンティアが俯瞰されます。[p.141〜p.253]
# セクション1: QAOA（量子近似最適化アルゴリズム）とVQE
NP困難な組み合わせ最適化問題に対し、厳密解ではなく近似解を量子・古典ハイブリッドで求めるパラダイムが提示されます。Farhi（2014）のQAOAと、量子化学等に応用されるVQEが中心です。[p.146〜p.175]
ページのナビゲート