論文の概要: Optimal algorithms for learning quantum phase states
- arxiv url: http://arxiv.org/abs/2208.07851v1
- Date: Tue, 16 Aug 2022 17:15:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-30 22:44:46.207567
- Title: Optimal algorithms for learning quantum phase states
- Title(参考訳): 量子相状態学習のための最適アルゴリズム
- Authors: Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, Theodore J. Yoder
- Abstract要約: 未知の次数$d$相状態を学ぶ際のサンプルの複雑さは、分離可能な測定を許せば$Theta(nd)$であることを示す。
また、f$がsparsity-$s$, degree-$d$を持つ場合の学習フェーズ状態も検討する。
- 参考スコア(独自算出の注目度): 8.736370689844682
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze the complexity of learning $n$-qubit quantum phase states. A
degree-$d$ phase state is defined as a superposition of all $2^n$ basis vectors
$x$ with amplitudes proportional to $(-1)^{f(x)}$, where $f$ is a degree-$d$
Boolean polynomial over $n$ variables. We show that the sample complexity of
learning an unknown degree-$d$ phase state is $\Theta(n^d)$ if we allow
separable measurements and $\Theta(n^{d-1})$ if we allow entangled
measurements. Our learning algorithm based on separable measurements has
runtime $\textsf{poly}(n)$ (for constant $d$) and is well-suited for near-term
demonstrations as it requires only single-qubit measurements in the Pauli $X$
and $Z$ bases. We show similar bounds on the sample complexity for learning
generalized phase states with complex-valued amplitudes. We further consider
learning phase states when $f$ has sparsity-$s$, degree-$d$ in its
$\mathbb{F}_2$ representation (with sample complexity $O(2^d sn)$), $f$ has
Fourier-degree-$t$ (with sample complexity $O(2^{2t})$), and learning quadratic
phase states with $\varepsilon$-global depolarizing noise (with sample
complexity $O(n^{1+\varepsilon})$). These learning algorithms give us a
procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP
circuits.
- Abstract(参考訳): 我々は、n$-qubitの量子状態の学習の複雑さを分析する。
次数-$d$位相状態は、$n$変数上の次数-$d$ Boolean多項式である$(-1)^{f(x)}$に比例する振幅を持つすべての2^n$基底ベクトル$x$の重ね合わせとして定義される。
未知の次数-d$位相状態の学習のサンプル複雑性は、分離可能な測定を許すならば$\theta(n^d)$であり、絡み合った測定を許すなら$\theta(n^{d-1})$である。
分離可能な測定に基づく学習アルゴリズムは、実行時$\textsf{poly}(n)$(一定の$d$)を持ち、pauli $x$と$z$ベースでシングルキュービットの測定のみを必要とするため、短期的なデモンストレーションには適しています。
複素数値振幅を持つ一般化位相状態の学習におけるサンプルの複雑さに類似した境界を示す。
さらに、$f$が$\mathbb{f}_2$表現を持つ場合(サンプル複雑性$o(2^d sn)$)、$f$がフーリエ度$t$を持つ場合(サンプル複雑性$o(2^{2t})$)、$\varepsilon$-global非分極化ノイズ(サンプル複雑性$o(n^{1+\varepsilon})$)で二次位相状態を学ぶ場合も検討する。
これらの学習アルゴリズムは、クリフォード階層とiqp回路の対角ユニタリを学ぶ手順を与える。
関連論文リスト
- Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳(メタデータ) (2024-06-25T06:07:20Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
論文 参考訳(メタデータ) (2023-02-07T22:58:12Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳(メタデータ) (2022-03-28T23:53:48Z) - Optimal learning of quantum Hamiltonians from high-temperature Gibbs
states [0.9453554184019105]
我々は、サンプル複雑性$S = O(log N/(betavarepsilon)2)$とサンプルサイズにおける時間線型である$O(S N)$で、ハミルトンの係数を誤差$varepsilon$で学習する方法を示す。
付録では、ほぼ同じアルゴリズムを用いて、類似のサンプルと時間複雑性を持つ小さな$tレジームにおいて、リアルタイム進化単位の$e-it Hilonから$H$を学習できることが示されている。
論文 参考訳(メタデータ) (2021-08-10T18:00:49Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳(メタデータ) (2020-12-29T14:06:09Z) - Improved quantum data analysis [1.8416014644193066]
我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。
また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
論文 参考訳(メタデータ) (2020-11-22T01:22:37Z) - 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) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳(メタデータ) (2020-06-11T00:55:35Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。