本記事では、Karpの21のNP完全問題の一つである 充足可能性問題 (SAT; satisfiability problem)に関して、最大独立集合問題 (MIS; maximum independent set)に帰 […]
readグラフ分割問題 をD-Wave 2000Qで解く(実践編)
T-Wave開設以来、いくつかの先行研究や導入事例に関する記事が出ている中で、どのように具体的な問題をD-Waveマシンで解くのかということは皆さん気になっていると思います。本記事では グラフ分割問題 を例に、サポートツ […]
readクリーク被覆問題 をD-Waveマシンで解く
Karpの21のNP完全問題の一つである クリーク被覆問題 (Clique Cover Problem)を、D-Wave 2000Qを用いて解いた。クリーク被覆問題のQUBO表現による定式化を解説したのち、Python […]
read宮城県の市区町村を塗り分けろ – グラフ彩色問題 をD-Waveマシンで解く
本記事ではKarpの21のNP完全問題の一つである グラフ彩色問題 (Graph Coloring)とそのQUBO表現について解説し、具体的な応用例として宮城県における市区町村の塗り分けをとりあげ、D-Wave 2000 […]
read量子アニーリングで 迷路 から脱出する “Navigating a Maze using a Quantum Annealer” by Scott Pakin
本記事で取り上げる論文では 迷路 における最短経路を求める問題をイジングスピングラスとして定式化し、D-Wave 2Xを用いて解いた結果を示している。補助ツールとして、問題を小問題に分割し、D-Waveマシンのキメラグラ […]
readグラフ分割問題 への応用 “Graph Partitioning using Quantum Annealing on the D-Wave System” by H. Ushijima-Mwesigawa, et al. (2017).
与えられたグラフを, 切断する辺の数を最小にしていくつかの部分グラフに分割する(最小カット問題) グラフ分割問題 をイジングスピングラス表現で定式化し, D-Wave 2Xにより解いた。グラフ分割問題 はKarpの21の […]
read衝突回避のための最適な 航空経路選択 への応用 “Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management” by Tobias Stollenwerk et al. (2017).
文献情報 タイトル Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management 著者 Tobia […]
readジョブショップスケジューリング問題への応用 “Job Shop Scheduling Solver based on Quantum Annealing” by D. Venturelli, et al. (2015).
文献情報 概要 組合せ最適化問題の一つであるジョブショップスケジューリング問題を定式化し、これをD-Wave Twoにより解いた。 問題 ジョブショップスケジューリング問題(JSP:Job Shop Scheduling […]
read組合せ最適化問題のイジングモデル表現 “Ising formulations of many NP problems” by Andrew Lucas (2014)
文献情報 タイトル: Ising formulations of many NP problems 著者: Andrew Lucas (Google Scholar) 書誌情報: Frontiers in Ph […]
read最大クリーク問題への応用 “Finding Maximum Cliques on the D-Wave Quantum Annealer” by Guillaume Chapuis et al. (2018)
文献 概要 あるグラフの部分グラフのうち、それに含まれる任意の二点間に辺があるような部分グラフで最大のものを最大クリークと呼ぶ。与えられたグラフから最大クリークを発見する問題は最大クリーク問題と呼ばれており、これはNP困 […]
read