1INRIA –フランス、パリ、シエラプロジェクトチーム
2イギリス、ロンドン、ユニバーシティカレッジロンドン、コンピューターサイエンス学科
3Rahko Ltd.、ロンドン、イギリス
4テキサス大学オースティン校、米国オースティン、コンピューターサイエンス学科
5イギリス、オックスフォード、オックスフォード大学、コンピューターサイエンス学科
6計算統計学および機械学習、IIT、ジェノヴァ、イタリア
この論文を興味深いと思うか、議論したいですか？ SciRateを引用するかコメントを残す.
抽象
量子力学システムの時間進化のシミュレーションはBQP困難であり、量子コンピューターの最も重要なアプリケーションのXNUMXつになると予想されます。 ランダム化数値線形代数からのサブサンプリング法を使用したハミルトニアンダイナミクスの近似のための古典的なアルゴリズムを検討します。 量子ビット数とハミルトニアンのフロベニウスノルムで多項式時間でスケーリングされるシミュレーション手法を導き出します。 直接の応用として、ハミルトニアンが密度行列である進化の一種であるサンプルベースの量子シミュレーションを、特定の構造条件下で効率的に古典的にシミュレートできることを示します。 主な技術的貢献は、エルミート行列の指数関数を近似するためのランダム化アルゴリズムです。 この証明は、Nyström法による低ランクの対称近似を活用します。 私たちの結果は、強いサンプリングの仮定の下で、量子計算の古典的な多対数時間シミュレーションが存在することを示唆しています。
►BibTeXデータ
►参照
【1] AharonovとTa-Shmaによる「断熱量子状態生成と統計的ゼロ知識」の第20回ACMシンポジウムの計算29-2003（XNUMX）のプロシーディングス。
https：/ / doi.org/ 10.1145 / 780542.780546
【2] AleksandrovとPellerの「Operator Lipschitz functions」Russian Mathematical Surveys 71、605（2016）。
https：/ / doi.org/ 10.1070 / RM9729
【3] BelabbasとWolfeの「共分散行列の高速低ランク近似」第2回IEEEインターナショナルワークショップ、マルチセンサー適応処理における計算の進歩、2007年。293-296年（2007年）。
https：/ / doi.org/ 10.1109 / CAMSAP.2007.4498023
【4] BelabbasとWolfe「線形演算子のスパース表現と行列積の近似について」第42回年次情報科学およびシステム会議258-263（2008）。
https：/ / doi.org/ 10.1109 / CISS.2008.4558532
【5] Berry、Childs、およびKothari、「すべてのパラメータにほぼ最適に依存するハミルトニアンシミュレーション」IEEE 56th Annual Symposium on Foundations of Computer Science（FOCS）792-809（2015）。
https：/ / doi.org/ 10.1109 / FOCS.2015.54
【6] Biamonte、Wittek、Pancotti、Rebentrost、Wiebe、およびLloyd、「Quantum machine learning」Nature 549、195（2017）。
https：/ / doi.org/ 10.1038 / nature23474
【7] Bravyi、Browne、Calpin、Campbell、Gosset、およびHoward、「低ランクの安定化分解による量子回路のシミュレーション」arXivプレプリントarXiv：1808.00128（2018）。
https://doi.org/10.22331/q-2019-09-02-181
【8] Chia、Gilyén、Li、Lin、Tang、およびWang、「量子機械学習を逆量子化するためのサンプリングベースのサブリニア低ランクマトリックス算術フレームワーク」arXivプレプリントarXiv：1910.06151（2019）。
【9] チャイルズとコタリ「星の分解による疎なハミルトニアンのシミュレーション」第5回量子計算、通信、および暗号理論に関する会議の議事録94-103（2011）。
https://doi.org/10.1007/978-3-642-18073-6_8
【10] チャイルズアンドウィーブ「単一演算の線形結合を使用したハミルトニアンシミュレーション」量子情報。 計算。 12、901-924（2012）。
https：/ / doi.org/ 10.5555 / 2481569.2481570
【11] チャイルズ、クリーブ、デオット、ファリー、グットマン、スピルマン、「量子ウォークによる指数アルゴリズムの高速化」第59回コンピューティング理論に関する年次ACMシンポジウムの議事録68-2003（XNUMX）。
https：/ / doi.org/ 10.1145 / 780542.780552
【12] Ciliberto、Herbster、Ialongo、Pontil、Rocchetto、Severini、およびWossnig、「量子機械学習：古典的な視点」Proc。 R. Soc。 A 474、20170551（2018）。
https：/ / doi.org/ 10.1098 / rspa.2017.0551
【13] Drineas、Kannan、およびMahoney、「行列の高速モンテカルロアルゴリズムI：近似行列乗算」SIAM Journal on Computing 36、132-157（2006）。
https：/ / doi.org/ 10.1137 / S0097539704442684
【14] Drineas、Kannan、およびMahoney、「マトリックスの高速モンテカルロアルゴリズムII：マトリックスへの低ランクの近似の計算」SIAM Journal on compute 36、158-183（2006）。
https：/ / doi.org/ 10.1137 / S0097539704442696
【15] DrineasとMahoney「カーネルベースの学習を改善するためにグラム行列を近似するためのNyström法について」J. Mach。 学ぶ。 解像度 6、2153-2175（2005）。
https：/ / doi.org/ 10.5555 / 1046920.1194916
【16] DrineasとMahoney「ランダム化された数値線形代数に関する講義」The Mathematics of Data 25、1（2018）。
【17] Drineas、Mahoney、Muthukrishnan、Sarlós、「最小最小二乗近似」数値。 数学。 117、219-249（2011）。
https://doi.org/10.1007/s00211-010-0331-6
【18] Fowlkes、Belongie、Chung、およびMalik、「Nyström法を使用したスペクトルのグループ化」IEEE Trans。 パターンアナル。 マッハ。 Intell。 26、214-225（2004）。
https：/ / doi.org/ 10.1109 / TPAMI.2004.1262185
【19] Frieze、Kannan、およびVempala、「低ランク近似を見つけるための高速モンテカルロアルゴリズム」J. ACM 51、1025-1041（2004）。
https：/ / doi.org/ 10.1145 / 1039488.1039494
【20] Haegeman、Cirac、Osborne、Pižorn、Verschelde、およびVerstraete、「量子格子の時間依存変分原理」物理的レビューレター107、070601（2011）。
https：/ / doi.org/ 10.1103 / PhysRevLett.107.070601
【21] Higham「マトリックス指数のスケーリングと二乗法の再考」SIAM J. Matrix Anal。 アプリケーション 26、1179-1193（2005）。
https：/ / doi.org/ 10.1137 / 04061101X
【22] Higham「マトリックス指数のスケーリングおよび二乗法の再考」SIAM Rev. 51、747-764（2009）。
https：/ / doi.org/ 10.1137 / 090768539
【23] Hsu「外部製品の加重サンプリング」arXivプレプリントarXiv：1410.4429（2014）。
【24] Huang、Newman、およびSzegedy、「強力な量子シミュレーションの明示的な下限」arXivプレプリントarXiv：1804.10368（2018）。
【25] Jónsson、Bauer、およびCarleo、「量子コンピューティングの古典的なシミュレーションのニューラルネットワーク状態」arXivプレプリントarXiv：1808.05232（2018）。
【26] KerenidisとPrakashの「量子推奨システム」arXivプレプリントarXiv：1603.08675（2016）。
【27] Kimmel、Lin、Low、Ozols、およびYoder、「最適なサンプル複雑度のハミルトニアンシミュレーション」npj量子情報3、13（2017）。
https://doi.org/10.1038/s41534-017-0013-7
【28] Kumar、Mohri、および Talwalkar、「サンプリングに基づく近似スペクトル分解について」Proceedings of the
機械学習に関する第 26 回年次国際会議 553-560 (2009)。
https：/ / doi.org/ 10.1145 / 1553374.1553446
【29] Kumar、Mohri、およびTalwalkar、「Nyström法のサンプリング法」Journal of Machine Learning Research 13、981-1006（2012）。
https：/ / doi.org/ 10.5555 / 2188385.2343678
【30] Li、Kwok、およびLu、「大規模なニストロム近似を可能にする」第27回国際機械学習会議に関する国際会議の議事録631-638（2010）。
https：/ / doi.org/ 10.5555 / 3104322.3104403
【31] Lloyd“ Universal Quantum Simulators” Science 273、1073-1078（1996）。
https：/ / doi.org/ 10.1126 / science.273.5278.1073
【32] Lloyd、Mohseni、およびRebentrost、「Quantum主成分分析」Nature Physics 10、631（2014）。
https：/ / doi.org/ 10.1038 / nphys3029
【33] Lowand Chuang「均一スペクトル増幅によるハミルトニアンシミュレーション」arXivプレプリントarXiv：1707.05391（2017）。
【34] Mackey、Talwalkar、およびJordan、「Divide-and-Conquer Matrix Factorization」Proceedings of the 24th International Conference on Neural Information Processing Systems 1134-1142（2011）。
https：/ / doi.org/ 10.5555 / 2986459.2986586
【35] Mahoneyの「行列とデータのランダム化アルゴリズム」Foundations andTrends®3、123-224（2011）。
https：/ / doi.org/ 10.1561 / 2200000035
【36] Mathias「行列値関数の近似」SIAM Journal on matrix analysis and applications 14、1061-1063（1993）。
https：/ / doi.org/ 10.1137 / 0614070
【37] Al-Mohyand Higham「マトリックス指数用の新しいスケーリングおよび二乗アルゴリズム」SIAM Journal on Matrix Analysis and Applications 31、970-989（2009）。
https：/ / doi.org/ 10.1137 / 09074721X
【38] Al-Mohyand Higham「行列指数の作用の計算、指数積分器への応用」科学計算に関するSIAMジャーナル33、488-511（2011）。
https：/ / doi.org/ 10.1137 / 100788860
【39] 中本「エルミート演算子の標準不等式」アメリカの数学月刊誌110、238（2003）。
https：/ / doi.org/ 10.1080 / 00029890.2003.11919961
【40] Nyström "Überdie praktischeAuflösungvon Integralgleichungen mit Anwendungen auf Randwertaufgaben" Acta Mathematica 54、185-204（1930）。
https：/ / doi.org/ 10.1007 / BF02547521
【41] Orecchia、Sachdeva、およびVishnoi、「第1141回コンピューティングの理論に関する第1160回年次ACMシンポジウム（2012）」のプロシーディングス「バランスセパレーターの指数関数、ランチョス法、およびÕ（m）時間スペクトルアルゴリズムの近似」
https：/ / doi.org/ 10.1145 / 2213977.2214080
【42] Orús「テンソルネットワークの実用的な入門：行列積状態と予測されたエンタングルドペア状態」Annals of Physics 349、117-158（2014）。
https：/ / doi.org/ 10.1016 / j.aop.2014.06.013
【43] Rebentrost、Mohseni、およびLloydの「ビッグデータ分類用の量子サポートベクターマシン」物理レビューレター113、130503（2014）。
https：/ / doi.org/ 10.1103 / PhysRevLett.113.130503
【44] Rebentrost、Schuld、Wossnig、Petruccione、およびLloyd、「量子勾配降下法と制約付き多項式最適化のためのニュートン法」New Journal of Physics 21、073023（2019）。
https://doi.org/10.1088/1367-2630/ab2a9e
【45] Rudi、Camoriano、およびRosasco、「Less is More：NyströmComputational Regularization」第28回神経情報処理システム国際会議の議事録–ボリューム1 1657-1665（2015）。
https：/ / doi.org/ 10.5555 / 2969239.2969424
【46] Rudi、Camoriano、およびRosasco、「Less is More：NyströmComputational Regularization」arXiv preprint arXiv：1507.04717（2015）。
【47] Schuld、Sinayskiy、およびPetruccione、「量子コンピューターでの線形回帰による予測」Physical Review A 94、022342（2016）。
https：/ / doi.org/ 10.1103 / PhysRevA.94.022342
【48] SchwarzとNestの「スパースな出力分布を持つ量子回路のシミュレーション」arXivプレプリントarXiv：1310.6749（2013）。
【49] SpielmanとTeng「グラフ分割、グラフスパース化、および線形システムの解法のためのほぼ線形の時間アルゴリズム」第81回コンピューティング理論に関する年次ACMシンポジウムの議事録90-2004（XNUMX）。
https：/ / doi.org/ 10.1145 / 1007352.1007372
【50] SpielmanとTengの「グラフのスペクトルスパース化」SIAM Journal on Computing 40、981-1025（2011）。
https：/ / doi.org/ 10.1137 / 08074489X
【51] 鈴木「一般化されたトロッターの公式と指数演算子の体系的近似および多体問題への応用を伴う内部導出」Communications in Mathematical Physics 51、183-190（1976）。
https：/ / doi.org/ 10.1007 / BF01609348
【52] Talwalkar、Kumar、およびRowley、「大規模多様体学習」コンピュータビジョンおよびパターン認識に関するIEEE会議1-8（2008）。
https：/ / doi.org/ 10.1109 / CVPR.2008.4587670
【53] Tang「コンピューティング理論に関する第51回ACM SIGACTシンポジウム217-228（2019）のプロシーディングス「推奨システムのための量子にヒントを得た古典的なアルゴリズム」のプロシーディングス。
https：/ / doi.org/ 10.1145 / 3313276.3316310
【54] Tropp「ランダムマトリックスの合計のユーザーフレンドリーなテール境界」が見つかりました。 計算。 数学。 12、389-434（2012）。
https：/ / doi.org/ 10.1007 / s10208-011-9099-z
【55] Trotter「オペレーターの半グループの製品について」Proceedings of the American Mathematical Society 10、545-551（1959）。
https://doi.org/10.1090/S0002-9939-1959-0108732-6
【56] Van Den Nest「量子計算の古典的シミュレーション、ゴッテスマン」Quantum Information＆Computation 10、258-271（2010）。
https：/ / doi.org/ 10.5555 / 2011350.2011356
【57] Verstraete、Garcia-Ripoll、およびCirac、「行列積密度演算子：有限温度および散逸系のシミュレーション」物理的レビューレター93、207204（2004）。
https：/ / doi.org/ 10.1103 / PhysRevLett.93.207204
【58] Verstraete、Murg、およびCirac、「行列積状態、投影されたエンタングルドペア状態、および量子スピンシステムの変分くりこみ群法」Advances in Physics 57、143-224（2008）。
https：/ / doi.org/ 10.1063 / 1.5026985
【59] Vidal「93次元量子多体系の効率的なシミュレーション」Phys。 レット牧師。 040502、2004（XNUMX）。
https：/ / doi.org/ 10.1103 / PhysRevLett.93.040502
【60] ウィリアムズとシーガーは、「Nyström法を使用してカーネルマシンを高速化する」ニューラル情報処理システムの進歩13 682-688（2001）を発表しました。
https：/ / doi.org/ 10.5555 / 3008751.3008847
【61] Williams、Rasmussen、Schwaighofer、およびTresp、「Gaussian Process PredictionのNyström法に関する観察」レポート（2002）。
【62] Woodruff「数値線形代数のツールとしてのスケッチ」Foundations andTrends®10、1-157（2014）。
https：/ / doi.org/ 10.1561 / 0400000060
【63] Zhang and Kwok「大規模多様体学習と次元削減のためのクラスター化ニストロム法」IEEE Transactions on Neural Networks 21、1576-1587（2010）。
https：/ / doi.org/ 10.1109 / TNN.2010.2064786
【64] Zhang、Tsang、およびKwok、「改良されたNyström低ランク近似とエラー分析」第25回機械学習に関する国際会議の議事録1232-1239（2008）。
https：/ / doi.org/ 10.1145 / 1390156.1390311
によって引用
[1] Ewin Tang、「主成分分析と教師ありクラスタリングのための量子にヒントを得た古典的なアルゴリズム」、 arXiv：1811.00414.
[2] Juan A. Acebron、「ベクトルに対する行列指数の作用を計算するためのモンテカルロ法」、 arXiv：1904.12759.
[3] Nai-Hui Chia、AndrásGilyén、Tongyang Li、Han-Hsuan Lin、Ewin Tang、およびChunhao Wang、「量子機械学習を逆量子化するためのサンプリングベースのサブリニア低ランク行列演算フレームワーク」、 arXiv：1910.06151.
上記の引用は SAO / NASA ADS （最後に正常に更新された2020-02-20 15:40:36）。 すべての出版社が適切で完全な引用データを提供するわけではないため、リストは不完全な場合があります。
取得できませんでした クロスリファレンス被引用データ 最終試行2020-02-20 15:40:34：10.22331 / q-2020-02-20-234の被引用データをCrossrefから取得できませんでした。 DOIが最近登録された場合、これは正常です。
この論文は、 Creative Commons Attribution 4.0 International（CC BY 4.0） ライセンス。 著作権は、著者やその機関などの元の著作権者にあります。
