1IBMTJワトソンリサーチセンター
2インド統計研究所、コルカタ、インド
3オーストラリア、シドニー工科大学、量子ソフトウェアおよび情報センター
4QuSoft、CWIおよびオランダのアムステルダム大学
この論文を興味深いと思うか、議論したいですか？ SciRateを引用するかコメントを残す.
抽象
量子コンピューターによる正確な学習に関する1.5つの新しい結果を提示します。 最初に、$ O（k ^ {2}（log k）^ 15）$均一量子関数の例から$ k $-フーリエスパース$ n $ビットブール関数を正確に学習する方法を示します。 これは、$ widetilde {Theta}（kn）$の均一にランダムな$ classic $の例の範囲を超えて改善されます（HavivおよびRegev、CCC'1.5）。 さらに、$ k $-フーリエスパースブール関数のチャンの補題の改善を証明することにより、$ widetilde {O}（k ^ {2}）$の上限を改善するための可能な方向性を提供します。 次に、概念クラス$ mathcal {C} $が$ Q $量子メンバーシップクエリを使用して正確に学習できる場合、$ Oleft（frac {Q ^ 04} {log Q} log | mathcal）を使用して学習できることを示します。 {C} | right）$ $ classic $メンバーシップクエリ。 これにより、以前の最良のシミュレーション結果（Servedio and Gortler、SICOMP'XNUMX）が$ log Q $係数で改善されます。
►BibTeXデータ
►参照
【1] J. Adcock、E。Allen、M。Day、S。Frick、J。Hinchliff、M。Johnson、S。Morley-Short、S。Pallister、A。Price、およびS.Stanisic。 量子機械学習の進歩、2015年。URLhttps：/ / arxiv.org/ abs /1512.02900。
arXiv：1512.02900
【2] A.アンバイニス。 量子引数による量子の下限。 Journal of Computer and System Sciences、64（4）：750–767、2002。10.1006 /jcss.2002.1826。 STOC'00の以前のバージョン。
https：/ / doi.org/ 10.1006 / jcss.2002.1826
【3] S.アルナチャラムとR.デウルフ。 ゲストコラム：量子学習理論の調査。 SIGACT News、48（2）：41–67、2017年。10.1145/ 3106700.3106710。 arXiv：1701.06806。
https：/ / doi.org/ 10.1145 / 3106700.3106710
arXiv：1701.06806
【4] S.アルナチャラムとR.デウルフ。 学習アルゴリズムの最適な量子サンプルの複雑さ。 Journal of Machine Learning Research、19年2018日。URLhttp：/ / jmlr.org/ papers / v19 /18-195.html。 CCC'17の以前のバージョン。
http：/ / jmlr.org/ papers / v19 / 18-195.html
【5] A.AtıcıとR.Servedio。 juntasを学習およびテストするための量子アルゴリズム。 量子情報処理、6（5）：323–348、2009年。10.1007/ s11128-007-0061-6。
https://doi.org/10.1007/s11128-007-0061-6
【6] H.バーナム、M。サックス、M。セゲディ。 量子クエリの複雑さと半正定値計画法。 計算の複雑さに関する第18回IEEE会議の議事録、179〜193ページ、2003年。10.1109/ CCC.2003.1214419。
https：/ / doi.org/ 10.1109 / CCC.2003.1214419
【7] E.ベルンシュタインとU.ヴァジラーニ。 量子複雑性理論。 SIAM Journal on Computing、26（5）：1411–1473、1997。10.1137 / S0097539796300921。 STOC'93の以前のバージョン。
https：/ / doi.org/ 10.1137 / S0097539796300921
【8] J. Biamonte、P。Wittek、N。Pancotti、P。Rebentrost、N。Wiebe、およびS. Lloyd 量子機械学習。 Nature、549（7671）、2017年。10.1038/ nature23474。
https：/ / doi.org/ 10.1038 / nature23474
【9] J.ブルガン。 制限された等長写像問題の改善された推定。 機能分析の幾何学的側面、数学の講義ノートの第2116巻、65〜70ページ。 Springer、2014年。10.1007/ 978-3-319-09477-9_5。
https://doi.org/10.1007/978-3-319-09477-9_5
【10] NHBshoutyとJCジャクソン。 量子例のオラクルを使用して、一様分布でDNFを学習します。 SIAM Journal on Computing、28（3）：1136––1153、1999。10.1145 /225298.225312。 COLT'95の以前のバージョン。
https：/ / doi.org/ 10.1145 / 225298.225312
【11] EJカンデスとT.タオ。 ランダム投影からのほぼ最適な信号回復：ユニバーサルエンコーディング戦略？ IEEE Transactions on Information Theory、52（12）：5406–5425、2006。10.1109 /TIT.2006.885507。
https：/ / doi.org/ 10.1109 / TIT.2006.885507
【12] Sourav Chakraborty、Nikhil S Mande、Rajat Mittal、Tulasimohan Molli、Manaswi Paraashar、およびSwagatoSanyal。 ブール関数の厳密なチャンの補題タイプの境界、2020年。URLhttps：/ / arxiv.org/ abs /2012.02335。
arXiv：2012.02335
【13] MCチャン。 フレイマンの定理の多項式限界。 Duke Mathematics Journal、113（3）：399–419、2002。10.1215 / S0012-7094-02-11331-3。
https://doi.org/10.1215/S0012-7094-02-11331-3
【14] M. Cheraghchi、V。Guruswami、およびA.Velingker。 フーリエ行列の制限された等長写像とランダム線形コードのリストデコード可能性。 SIAM Journal on Computing、42（5）：1888–1914、2013。10.1137 / 120896773。
https：/ / doi.org/ 10.1137 / 120896773
【15] TMカバーとJAトーマス。 情報理論の要素。 Wiley、1991年。10.1002/ 047174882X。
https：/ / doi.org/ 10.1002 / 047174882X
【16] V.DunjkoとHJBriegel。 量子領域における機械学習と人工知能：最近の進歩のレビュー。 Reports on Progress in Physics、81（7）：074001、2018。10.1088 / 1361-6633 / aab406。
https：/ / doi.org/ 10.1088 / 1361-6633 / aab406
【17] P.ゴパラン、R。オドネル、RAセルベディオ、A。シュピルカ、K。ウィマー。 フーリエ次元とスパース性のテスト。 SIAM Journal on Computing、40（4）：1075–1100、2011年。10.1137/ 100785429。 ICALP'09の以前のバージョン。
https：/ / doi.org/ 10.1137 / 100785429
【18] LKグローバー。 データベース検索のための高速量子力学的アルゴリズム。 第28回ACMSTOCの議事録、212〜219ページ、1996年。10.1145/ 237814.237866。
https：/ / doi.org/ 10.1145 / 237814.237866
【19] A.ハロー、A。ハシディズム、S。ロイド。 線形連立方程式を解くための量子アルゴリズム。 フィジカルレビューレター、103（15）：150502、2009年。10.1103/ PhysRevLett.103.150502。
https：/ / doi.org/ 10.1103 / PhysRevLett.103.150502
【20] H. Hassanieh、P。Indyk、D。Katabi、およびE.Price。 ほぼ最適なスパースフーリエ変換。 第44回ACMSTOCの議事録、ページ563–578、2012年。10.1145/ 2213977.2214029。
https：/ / doi.org/ 10.1145 / 2213977.2214029
【21] I.ハビブとO.レジェフ。 フーリエスパースブール関数のリストデコードサイズ。 計算理論に関するACMトランザクション、8（3）：10：1–10：14、2016年。10.1145/ 2898439。 CCC'15の以前のバージョン。
https：/ / doi.org/ 10.1145 / 2898439
【22] P.インディクとM.カプラロフ。 サンプル-任意の一定次元での最適なフーリエサンプリング。 第55回IEEEFOCSの議事録、514〜523ページ、2014年。10.1109/ FOCS.2014.61。
https：/ / doi.org/ 10.1109 / FOCS.2014.61
【23] E.モッセル、R。オドネル、R。セルベディオ。 $ k $関連変数の学習関数。 Journal of Computer and System Sciences、69（3）：421–434、2004。10.1016 /j.jcss.2004.04.002。 STOC'03の以前のバージョン。
https：/ / doi.org/ 10.1016 / j.jcss.2004.04.002
【24] マイケル・A・ニールセンとアイザック・L・チュアン。 量子計算と量子情報：10周年記念版。 ケンブリッジ大学出版局、2010 年。10.1017/ CBO9780511976667。
https：/ / doi.org/ 10.1017 / CBO9780511976667
【25] R.オドネル。 ブール関数の分析。 ケンブリッジ大学出版局、2014年。10.1017/ CBO9781139814782。
https：/ / doi.org/ 10.1017 / CBO9781139814782
【26] M.ラデルソンとR.バーシニン。 フーリエおよびガウス測定からのスパース再構成について。 Communications on Pure and Applied Mathematics、61（8）：1025-1045、2008。10.1002 /cpa.20227。
https：/ / doi.org/ 10.1002 / cpa.20227
【27] SwagatoSanyal。 フーリエスパース性と次元。 15巻、1〜13ページ。 計算理論、2019年。10.4086/ toc.2019.v015a011。
https：/ / doi.org/ 10.4086 / toc.2019.v015a011
【28] M. Schuld、I。Sinayskiy、およびF.Petruccione。 量子機械学習の紹介。 Contemporary Physics、56（2）：172–185、2015。10.1080 /00107514.2014.964942。
https：/ / doi.org/ 10.1080 / 00107514.2014.964942
【29] R.セルベディオとS.ゴートラー。 量子学習可能性と古典的学習可能性の間の同等性と分離。 SIAM Journal on Computing、33（5）：1067–1092、2004。10.1137 / S0097539704412910。 ICALP'01とCCC'01の以前の論文を組み合わせたものです。
https：/ / doi.org/ 10.1137 / S0097539704412910
【30] R.ŠpalekとM.Szegedy。 すべての量子敵の方法は同等です。 Proceedings of 32nd ICALP、volume 3580 of Lecture Notes in Computer Science、pages 1299–1311、2005。10.1007 / 11523468_105。
https：/ / doi.org/ 10.1007 / 11523468_105
【31] L.ヴァリアント。 学習可能な理論。 Communications of the ACM、27（11）：1134–1142、1984。10.1145 /1968.1972。
https：/ / doi.org/ 10.1145 / 1968.1972
【32] KAVerbeurgt。 準多項式時間の一様分布の下でDNFを学習します。 計算論的学習理論に関する第3回年次ワークショップ（COLT'90）の議事録、314〜326ページ、1990年。URLhttps：/ / dl.acm.org/ doi / 10.5555 /92571.92659。
https：/ / dl.acm.org/ doi / 10.5555 / 92571.92659
【33] P.ウィッテック。 量子機械学習：量子コンピューティングがデータマイニングに意味するもの。 エルゼビア、2014年。10.1016/ C2013-0-19170-2。
https://doi.org/10.1016/C2013-0-19170-2
【34] R.デウルフ。 ブールキューブのフーリエ解析の簡単な紹介。 計算理論、2008年。10.4086/ toc.gs.2008.001。 ToCライブラリ、大学院調査1。
https：/ / doi.org/ 10.4086 / toc.gs.2008.001
【35] A.CC。 八尾。 確率的計算：複雑さの統一された測定に向けて。 第18回IEEEFOCSの議事録、222〜227ページ、1977年。10.1109/ SFCS.1977.24。
https：/ / doi.org/ 10.1109 / SFCS.1977.24
によって引用
[1] SrinivasanArunachalamとReevuMaity、「Quantum Boosting」、 arXiv：2002.05056.
[2] Srinivasan Arunachalam、Alex B. Grilo、およびAarthi Sundaram、「浅い古典回路を学習する量子硬度」、 arXiv：1903.02840.
[3]AndrásGilyénとTongyangLi、「量子世界での分布特性試験」、 arXiv：1902.00814.
[4] Matthias C. Caro、「積の分布によるブール線形関数の量子学習」、 量子情報処理19 6、172（2020）.
上記の引用は SAO / NASA ADS （最後に正常に更新された2021-11-29 14:57:49）。 すべての出版社が適切で完全な引用データを提供するわけではないため、リストは不完全な場合があります。
On Crossrefの被引用サービス 作品の引用に関するデータは見つかりませんでした（最後の試行2021-11-29 14:57:47）。
この論文は、 Creative Commons Attribution 4.0 International（CC BY 4.0） ライセンス。 著作権は、著者やその機関などの元の著作権者にあります。
PlatoAi。 Web3の再考。 増幅されたデータインテリジェンス。
アクセスするには、ここをクリックしてください。
