情報処理学会 第87回全国大会

2K-04
量子とノイマン型コンピュータを組み合わせた巡回セールスマン問題の近似解法の提案
○宮田 葵,ピトヨ ハルトノ(中京大)
近年、量子力学の特徴である重ね合わせを利用して、複数の状態を同時に保持・計算できる量子コンピュータが注目されている。
この特性により、量子コンピュータはノイマン型コンピュータでは困難とされる組合せ最適化などの膨大な計算時間を必要とする問題への応用が期待できる。
本研究では、このような量子コンピュータの特性を利用し、ゲート型量子コンピュータを用いた巡回セールスマン問題(TSP)に対する経路コストの計算アルゴリズムと、従来のノイマン型コンピュータを利用した制約条件の充足判定アルゴリズムを組み合わせたTSPの近似解法を提案する。本稿では提案手法に関する説明と基礎実験の結果に関して報告する。