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

はじめに 量子アニーリングマシンの応用事例として、素因数分解への応用がいくつか既になされている。（例えば、[S. Jiang et al., Scientific Reports 8, 17667 (2018).]） ま […]

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

N-クイーン問題とは 導入 5 × 5マスのチェス盤に5個のクイーンをどのように置いたら、お互いの効きが当たらないか考えてみよう。クイーンは、縦横斜めに他の駒によって遮られない限り進める。 これを一般化した問題はN-クイ […]

本記事では、Karpの21のNP完全問題の一つである 充足可能性問題 (SAT; satisfiability problem)に関して、最大独立集合問題 (MIS; maximum independent set)に帰 […]

T-Wave開設以来、いくつかの先行研究や導入事例に関する記事が出ている中で、どのように具体的な問題をD-Waveマシンで解くのかということは皆さん気になっていると思います。本記事では グラフ分割問題 を例に、サポートツ […]

Karpの21のNP完全問題の一つである クリーク被覆問題 (Clique Cover Problem)を、D-Wave 2000Qを用いて解いた。クリーク被覆問題のQUBO表現による定式化を解説したのち、Python […]

本記事ではKarpの21のNP完全問題の一つである グラフ彩色問題 (Graph Coloring)とそのQUBO表現について解説し、具体的な応用例として宮城県における市区町村の塗り分けをとりあげ、D-Wave 2000 […]