ゼファーネットのロゴ

テンソル主成分分析のための古典的および量子アルゴリズム

日付:

マシュー・B・ヘイスティングス

Station Q、Microsoft Research、Santa Barbara、CA 93106-6105、USA
Microsoft Quantum and Microsoft Research、レドモンド、WA 98052、米国

この論文を興味深いと思うか、議論したいですか? SciRateを引用するかコメントを残す.

抽象

テンソル主成分分析の問題に対するスペクトル法に基づく古典アルゴリズムと量子アルゴリズムを紹介します。 量子アルゴリズムは、最速の古典的なスペクトル アルゴリズムよりも指数関数的に小さい空間を使用しながら $quartic$ の高速化を達成し、多項式空間のみを使用する古典的なアルゴリズムよりも超多項式の高速化を実現します。 私たちが提示する古典的なアルゴリズムは、参考文献で最近提示されたものとは関連していますが、わずかに異なります。 [1]。 特に、回復のしきい値が改善されており、私たちが提示するアルゴリズムは偶数次数と奇数次数の両方のテンソルに対して機能します。 これらの結果は、大規模推論問題が量子コンピューターの将来の有望なアプリケーションであることを示唆しています。

►BibTeXデータ

►参照

【1] アレクサンダー・S・ウェイン、アーメド・エル・アラウイ、クリストファー・ムーア。 菊地階層とテンソル PCA。 2019.arXiv:1904.03858。
arXiv:1904.03858

【2] アンドレア・モンタナーリとエミール・リチャード。 テンソル PCA の統計モデル。 『神経情報処理システムの進歩』、2897 ~ 2905 ページ、2014 年。

【3] ティボー・レシュー、レオ・ミオラーヌ、マルク・ルラージ、フロラン・クルザカラ、レンカ・ズデボロワ。 スパイクテンソル推定における統計的および計算的相転移。 2017 年の IEEE 情報理論国際シンポジウム (ISIT)。 IEEE、2017 年 10.1109 月。doi:2017.8006580/isit.XNUMX。
https:/ / doi.org/ 10.1109 / isit.2017.8006580

【4] サミュエル・B・ホプキンス、ジョナサン・シー、デイビッド・スチュラー。 二乗和証明によるテンソル主成分分析。 学習理論会議、956 ~ 1006 ページ、2015 年。

【5] サミュエル・B・ホプキンス、ツェリル・シュラム、ジョナサン・シー、デヴィッド・スチュラー。 二乗和証明からの高速スペクトル アルゴリズム: テンソル分解と植え付けられたスパース ベクトル。 第 48 回年次 ACM SIGACT コンピューティング理論に関するシンポジウム議事録 – STOC 2016。ACM Press、2016。doi:10.1145/ 2897518.2897529。
https:/ / doi.org/ 10.1145 / 2897518.2897529

【6] ビジェイVSPバティプロル、ムナルカンティ・ゴーシュ、ウィウン・リー、ヴェンカテサン・グルスワミ、マドゥル・トゥルシアーニ。 単位球上の多項式最適化のための乗法近似。 CoRR、abs/ 1611.05998、2016。URL: http://arxiv.org/abs/1611.05998、arXiv:1611.05998。
arXiv:1611.05998

【7] ヴィジェイ・バティプロル、ムナルカンティ・ゴーシュ、ヴェンカテサン・グルスワミ、ウィウン・リー、マドゥル・トゥルシアーニ。 弱いデカップリング、多項式の折り畳み、および球面上の近似最適化。 2017 年、コンピュータ サイエンスの基礎に関する IEEE 第 58 回年次シンポジウム (FOCS)。 IEEE、2017 年 10.1109 月。doi:2017.97/focs.XNUMX。
https:/ / doi.org/ 10.1109 / focs.2017.97

【8] RFヴェルナー。 大きな偏差と平均場量子システム。 量子確率と関連トピック、349 ~ 381 ページ。 WORLD SCIENTIFIC、1992 年 10.1142 月。doi:9789814354783/ 0024_XNUMX。
https:/ / doi.org/ 10.1142 / 9789814354783_0024

【9] クリスティーナ・V・クラウス、マチェイ・ルーウェンスタイン、J・イグナシオ・シラク。 順列対称性を持つフェルミオン格子ハミルトニアンの基底状態。 Physical Review A、88(2)、2013 年 10.1103 月。doi:88.022335/physreva.XNUMX。
https:/ / doi.org/ 10.1103 / physreva.88.022335

【10] フェルナンド GSL ブランダンとアラム W. ハロー。 量子状態への積状態の近似。 Communications in Mathematical Physics、342(1):47–80、2016 年 10.1007 月。doi:00220/ s016-2575-1-XNUMX。
https:/​/​doi.org/​10.1007/​s00220-016-2575-1

【11] スコット・アーロンソンとリージー・チェン。 量子超越性実験の複雑性理論の基礎。 第 32 回計算複雑性カンファレンス (CCC 2017) にて。 Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik、2017。arXiv:1612.05903。
arXiv:1612.05903

【12] マダン・ラル・メータ。 ランダム行列、第 142 巻。エルゼビア、2004 年。

【13] ジェームズ・デメル、イオアナ・ドゥミトリウ、オルガ・ホルツ。 高速な線形代数は安定しています。 Numericche Mathematik、108(1):59–91、2007 年 10.1007 月。doi:00211/ s007-0114-XNUMX-x。
https:/ / doi.org/ 10.1007 / s00211-007-0114-x

【14] グアン・ハオ・ロウ氏とアイザック・L・チュアン氏。 量子信号処理による最適なハミルトニアンシミュレーション。 物理学。 Rev. Lett.、118:010501、2017。arXiv:1606.02685v2、doi:10.1103/ PhysRevLett.118.010501。
https:/ / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv:1606.02685v2

【15] グアン・ハオ・ローとアイザック・L・チュアン。 量子化によるハミルトニアンシミュレーション。 2016.arXiv:1610.06546 https:/ / doi.org/ 10.22331/ q-2019-07-12-163。
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
arXiv:1610.06546

【16] ドミニク・W・ベリー、アンドリュー・M・チャイルズ、リチャード・クリーブ、ロビン・コタリ、ロランド・D・ソンマ。 スパースなハミルトニアンをシミュレートする精度が飛躍的に向上しました。 ページ 283–292、2014。arXiv:1312.1414、doi:10.1145/ 2591796.2591854。
https:/ / doi.org/ 10.1145 / 2591796.2591854
arXiv:1312.1414

【17] ドミニク・W・ベリー、アンドリュー・M・チャイルズ、リチャード・クリーブ、ロビン・コタリ、ロランド・D・ソンマ。 切り詰められたテイラー級数を使用してハミルトニアン ダイナミクスをシミュレートします。 物理学。 Rev. Lett.、114:090502、2015。arXiv:1412.4687、doi:10.1103/PhysRevLett.114.090502。
https:/ / doi.org/ 10.1103 / PhysRevLett.114.090502
arXiv:1412.4687

【18] DW ベリー、AM チャイルズ、R. コタリ。 すべてのパラメータにほぼ最適に依存するハミルトニアン シミュレーション。 2015 年の IEEE 56th Annual Symposium on Foundations of Computer Science、792 ~ 809 ページ、2015 年 1501.01715 月。arXiv:10.1109、doi:2015.54/ FOCS.XNUMX。
https:/ / doi.org/ 10.1109 / FOCS.2015.54
arXiv:1501.01715

【19] アレクセイ・ユ・キタエフ、アレクサンダー・シェン、ミハイル・N・ヴィャリィ。 古典および量子計算、第 47 巻。米国数学協会プロビデンス、2002 年。doi:10.1090/gsm/047。
https:/ / doi.org/ 10.1090 / gsm / 047

【20] ジル・ブラッサール、ピーター・ホイヤー、ミケーレ・モスカ、アラン・タップ。 量子振幅の増幅と推定。 現代数学、305:53–74、2002。doi:10.1090/ conm/ 305。
https:/ / doi.org/ 10.1090 / conm / 305

【21] アンソニー・カーベリーとジェームス・ライト。 ${R^n}$ の凸体上の多項式に対する分布不等式と ${L^q}$ ノルム不等式。 Mathematical Research Letters、8(3):233–248、2001。doi:10.4310/ mrl.2001.v8.n3.a1。
https:/​/​doi.org/​10.4310/​mrl.2001.v8.n3.a1

【22] デイブ・ウェッカー、マシュー・B・ヘイスティングス、ネイサン・ウィーブ、ブライアン・K・クラーク、チェタン・ナヤック、マティアス・トロイヤー。 量子コンピューター上で強相関電子モデルを解く。 Physical Review A、92(6)、2015 年 10.1103 月。doi:92.062318/physreva.XNUMX。
https:/ / doi.org/ 10.1103 / physreva.92.062318

< p class="休憩">【23] マシュー・B・ヘイスティングス。 量子最大フロー最小カットの漸近線。 Communications in Mathematical Physics、351(1):387–418、2016 年 10.1007 月。doi:00220/s016-2791-8-XNUMX。
https:/​/​doi.org/​10.1007/​s00220-016-2791-8

によって引用

[1] Alexander S. Wein、Ahmed El Alaoui、Cristopher Moore、「キクチ階層とテンソル PCA」、 arXiv:1904.03858.

上記の引用は SAO / NASA ADS (最後に正常に更新された2020-02-28 01:28:52)。 すべての出版社が適切で完全な引用データを提供するわけではないため、リストは不完全な場合があります。

On Crossrefの被引用サービス 作品の引用に関するデータは見つかりませんでした(最後の試行2020-02-28 01:28:50)。

ソース:https://quantum-journal.org/papers/q-2020-02-27-237/

スポット画像

最新のインテリジェンス

スポット画像

私たちとチャット

やあ! どんな御用でしょうか?