断熱的量子最適化はナップサック問題を解決できない【JST・京大機械翻訳】

Pusey-Nazzaro Lauren; Date Prasanna

プレプリント

J-GLOBAL ID：202202205346870619 整理番号：22P0182329

断熱的量子最適化はナップサック問題を解決できない【JST・京大機械翻訳】

Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2020年08月17日プレプリントサーバーでの情報更新日： 2020年08月17日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

本研究では,D-Wave 2000Q断熱量子コンピュータを用いて,整数重みナップサック問題を解くことを試みた。ナップサック問題は,経済学,ビジネス,財政などにおける応用とともに,コンピュータ科学におけるよく知られたNP完全問題である。最適解が知られている多数の小さなナップサック問題を解明することを試みた。断熱量子最適化は,全ての問題事例においてナップサックの最適充填に対応する解を生成できないことを見出した。量子ハードウェアについて得られた結果を,古典的シミュレーテッドアニーリングアルゴリズムおよびハイブリッド分枝限定アルゴリズムを用いた二つのソルバと比較した。また,シミュレーテッドアニーリングアルゴリズムは,シミュレーションおよび量子アニーリングにより得られた解が正しい解よりも互いに似ていないが,ナップサックの最適充填を生成できなかった。断熱量子最適化のこの観測された破壊の可能性のある原因を論じた。【JST・京大機械翻訳】

, , , , , , , , , ,
, , , , , 【Automatic Indexing@JST】

計算理論 , 数値計算 , その他のオペレーションズリサーチの手法 , 人工知能

, , ,

前のページに戻る