T-QARD Harbor

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

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

本記事では、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 […]

文献情報 概要 組合せ最適化問題の一つであるジョブショップスケジューリング問題を定式化し、これをD-Wave Twoにより解いた。 問題 ジョブショップスケジューリング問題(JSP:Job Shop Scheduling […]

文献情報 タイトル: Ising formulations of many NP problems 著者: Andrew Lucas (Google Scholar) 書誌情報: Frontiers in Ph […]

文献 概要 あるグラフの部分グラフのうち、それに含まれる任意の二点間に辺があるような部分グラフで最大のものを最大クリークと呼ぶ。与えられたグラフから最大クリークを発見する問題は最大クリーク問題と呼ばれており、これはNP困 […]

文献情報 概要 組合せ最適化問題の類型のひとつにナップサック問題がある。これをIsing模型（変数が1 or -1）と等価な形式であるQUBO形式（変数が1 or 0）によって表現した。 ナップサック問題とは 導入 ナッ […]