T-QARD Harbor

量子アニーリングでは、組合せ最適化問題の制約は罰金項として表現することが一般的です。しかしこの手法は量子アニーリング (QA) の性能を落としてしまうことが知られています。本論文では 制約付き量子アニーリング (Constrained Quantum Annealing, CQA) と呼ばれる手法を用いて組合せ最適化問題を解きます。この手法は制約を罰金項として表現するのではなく、量子効果を表す driver Hamiltonian を適切に用いることで制約を満たした解のみに限定して探索を行うことができる手法です。本論文では組合せ最適化問題の一例としてグラフ彩色問題に注目して、グラフ彩色問題を CQA を用いて解きます。実験の結果では CQA により最適解に近い解を得ることができました。一方で予想と違う結果も得られ、この考察も行います。

量子交互演算子アンザッツ（Quantum Alternating Operator Ansatz：QAOA）は最適化問題に対して有効で、Grover Mixier QAOAと呼ばれる手法は理論的に、全ての要素を等確率でサンプリングすること（フェアサンプリング）が可能です。しかし、実際のデバイスはノイズあり中規模量子（Noisy Intermediate Scale Quantum：NISQ）デバイスと呼ばれ、ノイズが存在しており、完全なフェアサンプリングは難しいです。本論文ではNISQデバイスにおけるGrover Mixier QAOAのフェアサンプリングの現状について調査します。

この論文では量子アニーリングをシミュレーションする手法である量子モンテカルロ法によって無人航空機(UAV)の無線通信網を作成するアルゴリズムを提案しました。実験の結果、量子モンテカルロ法によって作成した通信網はSAで作成した通信網よりもエネルギー消費量が低くなっていました。

K-SAT は、いくつかの変数からなる論理式を充足するような真偽値の割当を求める組合せ最適化問題です。K-SATはNP完全問題であることが示されており、現在のところ、入力サイズに対して最悪多項式時間で解くアルゴリズムの存在は知られていません。K-SAT の難しさの原因を理解し、K-SAT を平均的に高速に解くヒューリスティックを開発するための研究が進められています。本論文では、統計力学、特にスピングラス理論の手法を用いて K-SAT を解析し、上の 2 つの問いに対する洞察を与えます。

現在使われている信号制御では、局所的にしか渋滞を解消できません。しかし、全体制御の計算量は指数関数的に増大してしまいます。そこで、本論文ではD-Wave2000Qを用いた全体制御手法を提案しています。また、局所制御と比べてどれだけ優位なのかを紹介しています。

分子動力学法を量子アニーリングを組み合わせた古典・量子ハイブリッドの最適化手法を紹介します。そして、本手法を用いて最大カット問題とイジングスピングラス問題を解き、得られる解の精度や計算時間を古典的最適化手法 ( タブーサーチやシミュレーテッドアニーリング ) と比較します。

クラスタリングとは、教師無し学習の一つで、類似した特徴を持ったデータが同じグループに属するようにグループ分けすることを言います。主な手法にk-meansや階層型クラスタリングがありますが、これらは局所探索法であるため厳密解に到達する保証がありません。一方で、SAや遺伝的アルゴリズムのような大域的な探索手法では実行時間が長くなってしまいます。
そこで、本論文では高速に実行可能な量子アニーリングを利用します。まず、量子アニーリングマシンで計算可能な形でクラスタリングを定式化します。そして、それらの問題を解いた結果をk-meansと比較し、提案手法の利点と欠点について議論します。

航空機に対する発着ゲートの割り当ては航空管制において重要な業務の一つとなっています。この際、最も効率良いようなゲート割り当てを求めたいわけだが、これは組合せ最適化問題として扱うことができます。しかしながら、このような問題では最適解を高速に求めることが困難であることが知られています。したがって、本論文では量子アニーリングマシンのような新しいハードウェアの有用性を評価します。しかし、現実世界の問題では数多くの量子ビットを必要とするため、現状の量子アニーリングマシンでそのまま計算を行うことはできません。そこで、問題の構造を維持したまま、データを前処理することで、量子ビットを削減することを試みました。

国際学会AQC2022で信号機最適化に関するポスター発表を行いました。本記事では、発表内容を日本語で解説します.

マルチカーペイントショップ問題において、ブラックファーストとシミュレーテッドアニーリングの実装実験を行い、結果を比較した。