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

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

概要 記事「量子アニーリングを用いたグラフ彩色」では貪欲法でグラフ彩色を行うときに独立点集合を量子アニーリングで求めたときと古典コンピュータで求めたときとで最適化性能の比較を行った論文を紹介しました。本記事ではこの手法を […]

本記事では独立点集合を求める3つの近似的なアルゴリズムRamsey、CliqueRemoval、SampleISを説明します。

グラフ彩色とは隣接した頂点対を異なる色になるように彩色することです。3色以上のグラフ彩色はNP困難であり、高速に計算することが困難な問題の一つです。したがって、厳密性を犠牲にした近似的な解を求めるのが妥当であると考えられています。近似解を求める方法の一つにグラフから独立点集合(どの頂点も隣接していない頂点の集合)を求め、一つの独立点集合ごとに1色ずつ割り当てる貪欲法があります。本論文では、このアルゴリズムでグラフ彩色を行うときに独立点集合を量子アニーリングを用いて求めます。この提案手法を古典コンピュータで独立点集合を求めたときの結果を比較します。