量子アニーリングを実務で使いこなせることを目標に
パラシュート学習的に, 最短で必要な知識を集めたいと思います.
前提知識は, 量子アニーリングと量子ゲート方式があるというのを聞いたことがある程度です.
参考
https://quantum.fixstars.com/techresouces/
このサイトを参考にまとめています.
量子アニーリングは組み合わせ最適化に特化した量子アルゴリズム
だそうなので, まずは組み合わせ最適化問題とは何かを学習します.
組み合わせ最適化問題とは
その名の通り, 最適な組み合わせを探す問題です.
巡回セールスマン問題を例に
学習してみます.
巡回セールスマン問題とは, セールスマンが複数の都市をそれぞれ一回づつ訪問する際の, 最短経路を求める問題で, 以下の式で表せます.
C = \sum_{i{\neq}j}c_{ij}x_{ij}
$c_{ij}$ は都市iと都市jの距離, $x_{ij}$ は都市ij間を移動する場合に1, そうでない場合は0となります. すると, $C$ は総移動距離になるので, コスト関数やエネルギー関数, 目的関数などと呼ばれます.
都市の数が$n$ だとすると, 組み合わせの数は$n!$ となりますが, これは都市の数$n$が増えるにつれて組み合わせの数が爆発してしまいます.
このような問題は現実的な時間で最適解を厳密に求めることが困難なので, 最適解に近い近似解を求めることで対応することがあり, その近似解を求める方法の一つが量子アニーリングである.
とのことです.
巡回セールスマン問題を量子アニーリングで解くには
どうすれば良いでしょうか.
とのことなので, 巡回セールスマン問題をイジング模型に落とし込む必要がありそうです。ここまで読んで全くイメージが沸かないうえに, 全く量子アニーリングにたどり着きませんでしたが、休憩したいのでこの先は次回に回します... 次はイジング模型あたりを調べます. (絶対にここでやめないと誓って)