量子コンピュータ・アニーリングまわり、調査メモ
ゼネラリスト・ポリバレント属性（過去記事参照）を最大限発揮して、量子コンピュータ・（量子）アニーリングマシンまわりのいろいろについて調査中。そのメモまとめ。（なぜこれを調べているのかなどの全体としてのストーリーについては、今は記載・言及しません。）
性能評価・ベンチマーク
特にアニーリング領域では、「最大カット問題」というのをベンチマークに用いている事が多いようだ。最大カット問題についてはいろいろなところに解説があるが、例えばここ。
最大カット問題がなぜベンチマークとして用いられるのか、最大カット問題が実際上どのように役立つのかについては、このサイト（↓）およびそこから引用されているこの資料にわかりやすく説明されていた。例に挙げられているのは、画像処理において領域分割するケース、より具体的に言うと、CT画像から特定の組織部分だけをきれいに分割する方法だったり、逆に複数の画像をきれいに繋ぎたいとき（モンタージュ）にそのつなぎ目の部分をスムーズに切り出す方法だったり。
画像処理以外の応用例として、通信ネットワーク（広域ネットワーク）を大規模災害発生時に分断されないように構築するためにはどのように構成しておけばよいかの指標を計算したり、データセンターにおいて物理マシンに仮想マシンを配備するときの配備計画の算出、などの例もある。
最大カット問題をベンチマークとして具体的にどのように使うのか、については、最大カットのベンチマークを最適化ソルバーで解く、という下記の（解説）論文↓がとても参考になった。これには具体的な結果（実行時間）についても記述があり参考になる。
この論文に記載があるが、最大カット問題のベンチマークは、G-setという、ランダムに作られたグラフ（のデータ）を70種類ほどセットにしたものをよく用いるようだ。このグラフデータを元にして最大カット問題を数式（２次無制約２値計画？）として定義して、それをソルバーなり（量子）アニーリングマシンに解かせ、その時間や精度（厳密解との差異）を評価するということになる。
G-setの場所はここらしい。
量子コンピュータ・アニーリングマシンを用いた事例
最大カット問題を含む最適化問題を解く、という観点から、現状で使えるコンピュータやソフトウェア、それらを用いた評価事例について。
メルカリ（R4D?）でD-wave（量子アニーリングマシン）を使って最大カット問題を解いてみた事例。
これはIBMのQ（ゲート型量子コンピュータ）とそれを使うソフトウェアライブラリのqiskitで最大カット問題を解く事例。
qiskitの本家はこちら。qiskitは、実際にIBM量子コンピュータ上で計算する（つまり計算ジョブをリモートに投げる）方法と、自前のコンピュータでシミュレーションする方法の２通りがあるっぽい？（詳細追えてません）
QAOA（(Quantum Approximate Optimization Algorithm）は、ゲート型量子コンピュータで組合せ最適化計算を行うアルゴリズムのこと。
このQiitaの記事は、QAOAについて最初に提案した論文と、Rigetti社が量子コンピュータでQAOAを実装したという論文の２本を読んでまとめたものだが、とても良く書けている。著者曰く、QAOAは（これらの論文によれば）原理的には古典計算機での最適値算出計算を性能的に超えられる、とされているが、1. これは比較がフェアでない（古典計算機での計算アルゴリズムとして古いものを用いているため）、（すなわち最新アルゴリズムを用いれば、QAOAを用いなくても性能的に優位な結果が得られる＝QAOAいらねんじゃね、と暗黙的に言っている）、2. そうであればQAOAではなく（量子）アニーリングマシンを使えばいいのでは？、と述べている。
NISQについて触れなければいけないが、調査不十分。
古典計算機による方法
数理計画問題（最適化計算、最大カット問題などを含んだ大きな問題、ジャンルの定義）を解くソルバーと呼ばれるソフトウェアは、CPLEXがメジャーらしい。IBMのグループ会社ILOGの製品。（またしてもIBMか。）
これが非常に優秀らしく、現時点では、（量子）アニーリングマシンのハードウェア・ソフトウェア制約から、CPLEXで問題を解くことを（量子）アニーリングマシンが覆すまでには至っていないようだ。
とりあえず、今日はここまで。
この記事が気に入ったらサポートをしてみませんか？