統計力学と組合せ最適化の関連は長らく指摘されています．特に，充足可能性問題 (SAT) やグラフ彩色問題などの，離散変数の 制約充足問題 (Constraint Satisfaction Problem, 以下 CSP) に対しては，統計物理学の観点からの研究が進んでいます．一方で，連続変数 CSP に対する統計力学的な研究はあまりなされていません．本論文では，ガラスのモデルとして統計物理学で研究されている「球のパッキング」問題が，連続変数 CSP として捉えられることに着目します．球のパッキングは「ジャミング転移」と呼ばれる相転移現象を示すことが知られています．本論文では，連続変数 CSP の単純な例であるパーセプトロンの挙動を統計力学の手法を用いて解析し，球のパッキングと同様のジャミング転移が起こることを示します．
readD-Waveマシンの3世代間比較
2023年5月31日をもって、約5年間利用されてきたD-Wave 2000Qが廃止となりました。現在はD-Wave Advantage、そして2023-2024年に発売予定のD-Wave Advantage2のプロトタイプが利用可能です。本論文では、最大クリーク問題、最大カット問題を解くことにより、これら3世代のマシンの性能比較を行っています。その結果、最新のAdvantage2が、最適解に近い解を得られる確率において最も優れていることが分かりました。これはハードウェアグラフが密になり、マイナー埋め込みに必要なチェーンが少なくなったことが一因と考えられます。また、Advantage2では、比較的フェアサンプリングしていないことも分かりました。
readNISQデバイスにおけるフェアサンプリング性
量子交互演算子アンザッツ（Quantum Alternating Operator Ansatz：QAOA）は最適化問題に対して有効で、Grover Mixier QAOAと呼ばれる手法は理論的に、全ての要素を等確率でサンプリングすること（フェアサンプリング）が可能です。しかし、実際のデバイスはノイズあり中規模量子（Noisy Intermediate Scale Quantum：NISQ）デバイスと呼ばれ、ノイズが存在しており、完全なフェアサンプリングは難しいです。本論文ではNISQデバイスにおけるGrover Mixier QAOAのフェアサンプリングの現状について調査します。
readD-Waveマシンの限界を超える”大関法”
現状のD-Waveマシンでは、ハードウェア上に解きたい問題のグラフを埋め込む必要があります。このグラフが密になればなるほど、使用できる量子ビット数は少なくなってしまいます。問題をQUBO形式で表現する際、制約を罰金項で記述することがよくあります。しかし、罰金項は2次項であるため必然的にグラフは密になってしまい、使用できる量子ビット数を少なくしてしまいます。本論文では、このようなD-Waveマシンを使用する際に生じてしまう制限を解消する方法を紹介します。
read量子モンテカルロ法で無人航空機の通信網を作成する
この論文では量子アニーリングをシミュレーションする手法である量子モンテカルロ法によって無人航空機(UAV)の無線通信網を作成するアルゴリズムを提案しました。実験の結果、量子モンテカルロ法によって作成した通信網はSAで作成した通信網よりもエネルギー消費量が低くなっていました。
readランダム K-SAT の相転移とアルゴリズム
K-SAT は、いくつかの変数からなる論理式を充足するような真偽値の割当を求める組合せ最適化問題です。K-SATはNP完全問題であることが示されており、現在のところ、入力サイズに対して最悪多項式時間で解くアルゴリズムの存在は知られていません。K-SAT の難しさの原因を理解し、K-SAT を平均的に高速に解くヒューリスティックを開発するための研究が進められています。本論文では、統計力学、特にスピングラス理論の手法を用いて K-SAT を解析し、上の 2 つの問いに対する洞察を与えます。
read量子アニーリングとADMMのハイブリッド方式による不等式制約への対処
最適化問題の中には、不等式の形で表される制約 ( = 不等式制約 ) を含む問題が多くあります。この際に従来の手法では補助変数が用いますが、多数の物理量子ビットが追加で必要となるため問題の規模が制限されてしまいます。
そこで、本論文では、交互方向乗数法 ( ADMM ) という既存のアルゴリズムと量子アニーリングを組み合わせた新たなアルゴリズムを提案しています。このアルゴリズムは補助変数を用いないため従来よりも大規模な問題を解くことが可能となります。
2 次ナップサック問題 ( QKP ) を用いて性能検証を行います。
量子アニーリングで渋滞を解消しよう！
現在使われている信号制御では、局所的にしか渋滞を解消できません。しかし、全体制御の計算量は指数関数的に増大してしまいます。そこで、本論文ではD-Wave2000Qを用いた全体制御手法を提案しています。また、局所制御と比べてどれだけ優位なのかを紹介しています。
read分子動力学法によるハイブリッド量子アニーリング
分子動力学法を量子アニーリングを組み合わせた古典・量子ハイブリッドの最適化手法を紹介します。そして、本手法を用いて最大カット問題とイジングスピングラス問題を解き、得られる解の精度や計算時間を古典的最適化手法 ( タブーサーチやシミュレーテッドアニーリング ) と比較します。
read量子アニーリングでクラスタリングはうまくできるのか？
クラスタリングとは、教師無し学習の一つで、類似した特徴を持ったデータが同じグループに属するようにグループ分けすることを言います。主な手法にk-meansや階層型クラスタリングがありますが、これらは局所探索法であるため厳密解に到達する保証がありません。一方で、SAや遺伝的アルゴリズムのような大域的な探索手法では実行時間が長くなってしまいます。
そこで、本論文では高速に実行可能な量子アニーリングを利用します。まず、量子アニーリングマシンで計算可能な形でクラスタリングを定式化します。そして、それらの問題を解いた結果をk-meansと比較し、提案手法の利点と欠点について議論します。