文献

J-GLOBAL ID：201702213340449163   整理番号：17A1774697

量子SDPソルバ:より良い上界と下界【Powered by NICT】

Quantum SDP-Solvers: Better Upper and Lower Bounds

著者 (4件)： Van Apeldoorn Joran ,  Gilyen Andras ,  Gribling Sander ,  de Wolf Ronald
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： FOCS  ページ： 403-414  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： Branda oとSvoreは最近約半正定値計画法を解くための量子アルゴリズム,いくつかの領域では問題の次元nと制約の数mの点で最良な実現可能な古典的アルゴリズムよりも速かったが,種々の他のパラメータの点で悪いを与えた。本論文では,いくつかの方法でそのアルゴリズムを改善し,他のパラメータに対する良好な依存性を得る。この目的のために,量子アルゴリズムのための新しい技術,例えばスパースハミルトニアンの滑らかな関数を効率的に実現するための一般的な方法,および一般化最小発見法を開発した。量子SDPソルバへのこの方法の限界を示し,例えば多くの対称性を持つことを組合せ最適化問題。最後に,最悪の場合,mは約nときすべての量子LPソルバ(従って,SDP解法)の複雑さは,Mnと共に直線的にスケールしなければならないことを示すいくつかの一般的な下限,古典的と同じを証明した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *アルゴリズム ,  マンガン ,  対称性 ,  組合せ最適化問題
準シソーラス用語： 量子アルゴリズム ,  半正定値計画法 ,  *下界 ,  *上界 ,  *ソルバ , 【Automatic Indexing@JST】

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 量子 ,  ソルバ ,  上界 ,  下界