量子アニーリングを用いたグラフ彩色
グラフ彩色とは隣接した頂点対を異なる色になるように彩色することです。3色以上のグラフ彩色はNP困難であり、高速に計算することが困難な問題の一つです。したがって、厳密性を犠牲にした近似的な解を求めるのが妥当であると考えられています。近似解を求める方法の一つにグラフから独立点集合(どの頂点も隣接していない頂点の集合)を求め、一つの独立点集合ごとに1色ずつ割り当てる貪欲法があります。本論文では、このアルゴリズムでグラフ彩色を行うときに独立点集合を量子アニーリングを用いて求めます。この提案手法を古典コンピュータで独立点集合を求めたときの結果を比較します。
ボルツマン機械学習にD-Waveマシンを用いる
ボルツマン機械学習では対数尤度関数を最大化するために、ギブス・ボルツマン分布からのサンプリングによる平均値を計算する必要があります。その方法の一つとして、マルコフ連鎖モンテカルロ法 (MCMC) が使われています。しかし、MCMCは初期状態から平衡状態への緩和に長時間の計算を要する場合があります。また、緩和した後も平均値を精度良く求めるための十分なサンプリング数の確保に時間がかかるといった課題もあります[1]。そこで本論文では、D-Waveマシンから得られる出力の分布がギブス・ボルツマン分布に近いことを利用して、平均値の計算にD-Waveマシンを用います。本手法により、手書き数字画像の生成・復元が可能であることに加え、ランダムなイジング模型も学習可能であることを示します。
ナーススケジューリング問題をD-Wave 2000Qで解く
医療現場では人の命に関わる業務を行っているため、看護師の勤務の質が厳しく求められています。しかし、看護師の生活の質も守らなければいけないため、勤務表の作成が困難になっています。ナーススケジューリング問題 (Nurse scheduling Problem, NSP)とは、複数の制約の下で看護師に最適なシフトを割り当てる問題です。NSPは1969年以前より研究されており、NP困難であることが知られています。
量子アニーリングによる配送計画
CVRP (容量制約有りの配送計画問題)は、積載容量に制約のある車両で効率よく荷物を配送することを目的とした問題です。CVRPは、NP困難な問題であり、顧客の数が増えると組合せも爆発的に増加するため、全探索を用いて最適解を求めるには限界があります。そのため、古典的な手法では近似解を求めるのが主流です。この論文では、CVRPを小さな問題に分割し、量子アニーリングマシンと古典コンピュータの両方を用いたハイブリッドな手法を用いて解きます。そして、解の質や計算時間について古典的な手法との比較、および量子アニーリングマシン(D-Wave 2000Q)の性能の評価を行っています。
経路最適化問題を量子アニーリングで解く
D-Wave Systemsによって開発が行われている量子アニーリングマシンは、組合せ最適化を高速に解くソルバーとして活発な分析が行われています。本論文では、渋滞解消を目的とした自動車の移動経路割当を組合せ最適化問題として定式化します。連続的な経路割当を実現するには最適化の高速性が求められるが、北京首都国際空港近辺における過去のドライブデータを用いてシミュレーションを行った結果、量子アニーリングは有効的な手法の一つであることを示しています。
非負値行列分解 “Nonnegative/binary matrix factorization with a D-Wave quantum annealer” by Daniel O’Malley, et al. (2017)
本記事で紹介する論文では、D-Waveマシンを用いた量子アニーリングにより二値変数制約のついた 非負値行列分解 の手法と顔画像認識に応用した結果を示している。速度性能評価のために、古典的アルゴリズムを用いるGurobiとqbsolv（タブーサーチ）を用いた場合とD-Wave 2Xで得られた最適解に逹する累積TTT (time-to-target)を測り、そのアニーリング回数依存性を比較・検討している。 文献情報 Daniel O’Malley, Velimir V. Vesselinov, Boian S. Alexandrov, Ludmil B. Alexandrov, “Nonnegative/binary matrix factorization with a D-Wave quantum annealer”, arXiv:1704.01605. 非負値行列分解 (NMF)とは 非負値行列分解 (Nonnegative Matrix Factorization; NMF) は、$n \times m$行列$V$を全て非負値の要素からなる$n \times…
量子アニーリングで 迷路 から脱出する “Navigating a Maze using a Quantum Annealer” by Scott Pakin
本記事で取り上げる論文では 迷路 における最短経路を求める問題をイジングスピングラスとして定式化し、D-Wave 2Xを用いて解いた結果を示している。補助ツールとして、問題を小問題に分割し、D-WaveマシンのキメラグラフにマップするQMASM(quantum macro assembler)を用いている。入出力やイジング模型へのマッピング、さらには 量子アニーリング にかかる時間のベンチマークや、そしてアニーリング時間による解の時間対精度などについても考察をしている。 文献情報 Scott Pakin, “Navigating a Maze using a Quantum Annealer”, Proceeding of PMES’17 Proceedings of the Second International Workshop on Post Moores Era Supercomputing, 30-36 (2017). 迷路の組合せ最適化問題としての定式化 迷路の定義と解の経路が満たすべき条件 本論文では、以下のような6×6のマスから構成…
グラフ分割問題 への応用 “Graph Partitioning using Quantum Annealing on the D-Wave System” by H. Ushijima-Mwesigawa, et al. (2017).
与えられたグラフを, 切断する辺の数を最小にしていくつかの部分グラフに分割する（最小カット問題） グラフ分割問題 をイジングスピングラス表現で定式化し, D-Wave 2Xにより解いた。グラフ分割問題 はKarpの21の組合せ最適化問題の1つとなっている。分割数が2の場合とそれ以上の数の場合では表現形式が異なることが興味深い。 文献情報 Hayato Ushijima-Mwesigwa, Christian F. A. Negre, Susan M. Mniszewski, “Graph Partitioning using Quantum Annealing on the D-Wave System”, arXiv:1705.03082 [quant-ph]. グラフ分割問題 本論文で扱う問題の定式化は, 分割数が2の場合とそれより大きい一般のKの場合でイジングスピングラス表現が少々異なる. 分割数が2の場合 最適化問題の定式化 分割数が2の場合, イジング表現（二値変数として+1か-1）で表現するのが自然である. 変数 $$s_i = \{ -1, 1 \}…
衝突回避のための最適な 航空経路選択 への応用 “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 著者 Tobias Stollenwerk, Bryan O’Gorman, Davide Venturelli, Salvatore Mandra, Olga Rodionova, Hok K. Ng, Banavar Sridhar, Eleanor G. Rieffel, and Rupak BiswasarXiv:1711.04889 [quant-ph] 概要 大西洋横断飛行において、風に対する最適な軌道を採用することで生じるフライト間の衝突を、フライトの遅延によって回避するという問題がある。これをD-Wave 2XおよびD-Wave 2000Qを用いて解いた。 問題 航空における交通量は年々増加しており、使用可能な空域が限られてきている。大西洋に存在するジェット気流の影響を受ける大西洋横断飛行(NAT)において風に対する最適な軌道が採用されると、潜在的な衝突が発…