文献

J-GLOBAL ID：201702284770750572   整理番号：17A1774698

半正定値プログラムのための量子高速化【Powered by NICT】

Quantum Speed-Ups for Solving Semidefinite Programs

著者 (2件)： Brandao Fernando G.S.L. ,  Svore Krysta M.
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： FOCS  ページ： 415-426  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 半正定値計画法(SDP)を解くための量子アルゴリズムを与えた。最悪ケース実行時間n{1/2}m^{1/2}^2/ポリ(log(n),log(m),R,R,1/δ),NおよびSを,それぞれ,入力行列の大きさと列スパースm制約条件の数,δ解の精度,および最適な主および双対解の大きさにR,R上界それぞれを持っている。これはnとmの両方でSDPを解くための任意の古典的方法を上回る平方根無条件スピードアップを示した。アルゴリズムは実質的に改善した(nとmの)定数s,R,Rとδと半正定値計画法を解くためのΩ(n^{1/2}+m^{1/2})量子下限を与えることができない証明した。量子アルゴリズムを量子Gibbsサンプリングと乗法的重量法の組合せにより構築した。特に,約SDPを解くためのArora及びケールの古典的アルゴリズムに基づいている。は独立した関心がある内部線形計画を解くための必要性を排除するために,アルゴリズムの修正を提案した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 透視図法 ,  乗算 ,  *高速化 ,  線形計画法 ,  アルゴリズム
準シソーラス用語： Gibbsサンプリング ,  実行時間 ,  量子アルゴリズム ,  半正定値計画法 , 【Automatic Indexing@JST】

分類 (3件)： 無線通信一般  (ND08010L) ,  信号理論  (ND02020G) ,  数理計画法  (KA03030M)

タイトルに関連する用語 (3件)： 半正定値プログラム ,  量子 ,  高速化