論文の概要: Learning low-degree quantum objects

• arxiv url: http://arxiv.org/abs/2405.10933v1
• Date: Fri, 17 May 2024 17:36:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-20 15:24:17.340152
• Title: Learning low-degree quantum objects
• Title（参考訳）: 低次量子オブジェクトの学習
• Authors: Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, Carlos Palazuelos,
• Abstract要約: 低次量子オブジェクトを、$ell$-distanceで$varepsilon$-errorまで学習する方法を示す。 我々の主な技術的貢献は、量子チャネルと完全有界ポリリノミアルに対する新しいボネンブラスト・ヒル不等式である。
• 参考スコア（独自算出の注目度）: 5.2373060530454625
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of learning low-degree quantum objects up to $\varepsilon$-error in $\ell_2$-distance. We show the following results: $(i)$ unknown $n$-qubit degree-$d$ (in the Pauli basis) quantum channels and unitaries can be learned using $O(1/\varepsilon^d)$ queries (independent of $n$), $(ii)$ polynomials $p:\{-1,1\}^n\rightarrow [-1,1]$ arising from $d$-query quantum algorithms can be classically learned from $O((1/\varepsilon)^d\cdot \log n)$ many random examples $(x,p(x))$ (which implies learnability even for $d=O(\log n)$), and $(iii)$ degree-$d$ polynomials $p:\{-1,1\}^n\to [-1,1]$ can be learned through $O(1/\varepsilon^d)$ queries to a quantum unitary $U_p$ that block-encodes $p$. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded~polynomials.
• Abstract（参考訳）: 低次量子オブジェクトを、$\ell_2$-distanceで$\varepsilon$-errorまで学習する問題を考察する。 以下の結果を示す。 (i)$ unknown $n$-qubit degree-$d$(Pauliベース)量子チャネルとユニタリは$O(1/\varepsilon^d)$クエリ($n$に依存しない)$$で学習することができる。 (ii)$ polynomials $p:\{-1,1\}^n\rightarrow [-1,1]$ arising from $d$-query quantum algorithm can be classicly learn from $O((1/\varepsilon)^d\cdot \log n)$ many random examples $(x,p(x))$ (これは$d=O(\log n)$) and $(iii)$ degree-$d$ polynomials $p:\{-1,1\}^n\to [-1,1]$$は$O(1/\varepsilon^d)$クエリから$pをブロックする量子ユニタリな$U_p$へのクエリから学べる。 我々の主な技術的貢献は、量子チャネルと完全に有界な−ポリノミアルに対する新しいボネンブラスト・ヒルの不等式である。

関連論文リスト

• Testing and learning structured quantum Hamiltonians [4.137418441736385]
  正規化フロベニウスノルムの下で、未知の$n$qubit Hamiltonian $H$をクエリからその進化作用素 $e-iHt$ までテストし、学習する問題を考察する。
  論文  参考訳（メタデータ） (2024-10-31T17:54:13Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。 最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
  論文  参考訳（メタデータ） (2021-04-29T14:50:03Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)
• Quantum algorithms for the Goldreich-Levin learning problem [3.8849433921565284]
  Goldreich-Levinアルゴリズムは元々暗号目的のために提案され、その後学習に適用された。 ウォルシュ係数を持つベクトルを$w$で出力するには$poly(n,frac1epsilonlogfrac1delta)$時間を要する。 本稿では,この問題に対する量子アルゴリズムをクエリ複雑性$O(fraclogfrac1deltaepsilon4)$で与えられる。
  論文  参考訳（メタデータ） (2019-12-31T14:52:36Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。