T-QARD Harbor

本論文では量子アニーリングを用いた新たな作曲手法を提案します。音楽を構成する要素をメロディ・リズム・ハーモニーの３つに分け、それぞれに対して D-Wave マシンを用いた生成方法を示します。本記事では ｢ メロディ ｣ の生成に関する説明を行います。

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

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

先日開催された量子アニーリングソリューションコンテストにTQARD-410として参加し、量子アニーリングでフォトモザイクアートを作成するPhosaiqを提案しました。Phosaiqは画像の並びを最適化したフォトモザイクアートを作成し、またユーザーが調整することでフォトモザイクアートの質とユーザの体験価値を高めるプロダクトです。このコンテストにおいて、Phosaiqは優勝(D-Wave Systems社賞を受賞)することができました。

記事「ナーススケジューリング問題をD-Wave 2000Qで解く」では、ナーススケジューリング問題(NSP)をD-Wave 2000Qで解くことにより、量子アニーリング(QA)の計算性能を評価する論文を紹介しました。結果として、NSPを解くことに関しては、QAよりもシミュレーテッドアニーリング(SA)の方が有用でした。しかし、この論文では制約の係数を人数や日数といった設定毎に変えていないため、係数を調整することで、より良い結果を得られる可能性があります。そこで本記事ではまず、最適だと考えられる係数を探索します。そして、その係数を用いることで、論文の結果よりも基底状態の解を見つける確率が向上するのか検証します。

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

本論文では、グラフ分割問題を取り扱う。グラフ分割問題とはグラフのノードを複数のグループに分割することであり、以下の二つの条件を満たすことを考える。

医療現場では人の命に関わる業務を行っているため、看護師の勤務の質が厳しく求められています。しかし、看護師の生活の質も守らなければいけないため、勤務表の作成が困難になっています。ナーススケジューリング問題 (Nurse scheduling Problem, NSP)とは、複数の制約の下で看護師に最適なシフトを割り当てる問題です。NSPは1969年以前より研究されており、NP困難であることが知られています。

D-Wave Systemsによって開発が行われている量子アニーリングマシンは、組合せ最適化を高速に解くソルバーとして活発な分析が行われています。本論文では、渋滞解消を目的とした自動車の移動経路割当を組合せ最適化問題として定式化します。連続的な経路割当を実現するには最適化の高速性が求められるが、北京首都国際空港近辺における過去のドライブデータを用いてシミュレーションを行った結果、量子アニーリングは有効的な手法の一つであることを示しています。

今回は、（株）リクルートコミュニケーションズが開発し、オープンソースにより公開されたドメイン固有言語 PyQUBO (プレスリリース) を紹介する。PyQUBOは、組合せ最適化問題を制約なし二値変数二次計画問題 (QUB […]