文献情報 タイトル: 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整数ナップサック問題のIsing表現ハミルトニアン：Knapsack with Integer Weights
文献情報 概要 組合せ最適化問題の類型のひとつにナップサック問題がある。これをIsing模型（変数が1 or -1）と等価な形式であるQUBO形式（変数が1 or 0）によって表現した。 ナップサック問題とは 導入 ナッ […]
read交通渋滞緩和のための経路選択への応用 “Traffic Flow Optimization Using a Quantum Annealer” by Florian Neukart, et al. (2017).
文献情報 概要 交通渋滞を緩和するために複数台の車の経路選択を組合せ最適化問題として定式化し、これをD-Wave 2Xにより解いた。 方法 方針 古典: 現時点の位置から目的地までの経路を各車両ごとに3つ用意する量子: […]
read