論文の概要: On the sampling complexity of coherent superpositions
- arxiv url: http://arxiv.org/abs/2501.17071v1
- Date: Tue, 28 Jan 2025 16:56:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-29 16:41:10.755150
- Title: On the sampling complexity of coherent superpositions
- Title（参考訳）: コヒーレント重ね合わせのサンプリング複雑性について
- Authors: Beatriz Dias, Robert Koenig,
- Abstract要約: 重ね合わせにPOVMを適用する際に測定結果の分布からサンプリングする問題を考察する。
我々は、$-$$$$O(chi |c|2 log1/delta)$そのようなサンプルを与えられたアルゴリズムを与え、確率密度関数を評価するためにオラクルを呼び出す。
- 参考スコア（独自算出の注目度）: 0.4972323953932129
- License:
- Abstract: We consider the problem of sampling from the distribution of measurement outcomes when applying a POVM to a superposition $|\Psi\rangle = \sum_{j=0}^{\chi-1} c_j |\psi_j\rangle$ of $\chi$ pure states. We relate this problem to that of drawing samples from the outcome distribution when measuring a single state $|\psi_j\rangle$ in the superposition. Here $j$ is drawn from the distribution $p(j)=|c_j|^2/\|c\|^2_2$ of normalized amplitudes. We give an algorithm which $-$ given $O(\chi \|c\|_2^2 \log1/\delta)$ such samples and calls to oracles evaluating the involved probability density functions $-$ outputs a sample from the target distribution except with probability at most $\delta$. In many cases of interest, the POVM and individual states in the superposition have efficient classical descriptions allowing to evaluate matrix elements of POVM elements and to draw samples from outcome distributions. In such a scenario, our algorithm gives a reduction from strong classical simulation (i.e., the problem of computing outcome probabilities) to weak simulation (i.e., the problem of sampling). In contrast to prior work focusing on finite-outcome POVMs, this reduction also applies to continuous-outcome POVMs. An example is homodyne or heterodyne measurements applied to a superposition of Gaussian states. Here we obtain a sampling algorithm with time complexity $O(N^3 \chi^3 \|c\|_2^2 \log1/\delta)$ for a state of $N$ bosonic modes.
- Abstract（参考訳）: 我々は、POVM を重ね合わせ $|\Psi\rangle = \sum_{j=0}^{\chi-1} c_j |\psi_j\rangle$ of $\chi$ pure 状態に適用する際の測定結果の分布からサンプリングする問題を考察する。
この問題は、重ね合わせにおいて単一の状態 $|\psi_j\rangle$ を測定する際に、結果分布からサンプルを描画することと関係する。
ここで、$j$ は正規化振幅の分布 $p(j)=|c_j|^2/\|c\|^2_2$ から引き出される。
我々は、$-$が与えられた$O(\chi \|c\|_2^2 \log1/\delta)$のアルゴリズムを与え、関連する確率密度関数を評価するオラクルに呼び出し、少なくとも$\delta$の確率を除いて、ターゲット分布からサンプルを出力する。
多くの場合、重ね合わせにおけるPOVMと個々の状態は、POVM要素の行列要素を評価し、結果分布からサンプルを引き出すことができる効率的な古典的記述を持つ。
このようなシナリオにおいて、我々のアルゴリズムは、強い古典シミュレーション(すなわち、計算結果確率の問題)から弱いシミュレーション(すなわちサンプリングの問題)への還元を与える。
有限アウトカムのPOVMに焦点を当てた以前の作業とは対照的に、この削減は連続アウトカムのPOVMにも適用される。
例えば、ホモダインまたはヘテロダインの測定はガウス状態の重ね合わせに適用される。
ここでは、時間複雑性$O(N^3 \chi^3 \|c\|_2^2 \log1/\delta)$を、N$ボソニックモードの状態に対してサンプリングする。
関連論文リスト
- On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。
広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
論文 参考訳（メタデータ） (2025-02-10T06:54:16Z) - Polynomial time sampling from log-smooth distributions in fixed dimension under semi-log-concavity of the forward diffusion with application to strongly dissipative distributions [9.48556659249574]
固定次元の複雑なサンプリングアルゴリズムを提案する。
我々は,提案アルゴリズムが予測される$epsilon$誤差を$KL$ばらつきで達成することを証明する。
応用として、$L$-log-smooth分布からサンプリングする問題に対する指数関数的複雑性の改善を導出する。
論文 参考訳（メタデータ） (2024-12-31T17:51:39Z) - 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) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Optimal Sublinear Sampling of Spanning Trees and Determinantal Point
Processes via Average-Case Entropic Independence [3.9586758145580014]
強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。
グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。
$n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
論文 参考訳（メタデータ） (2022-04-06T04:11:26Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Efficient sampling from the Bingham distribution [38.50073658077009]
我々は、Bingham分布の$p(x)propto exp(xtop A x)$と、$operatornamepoly(d, lambda_max(A)-lambda_min(A))$の期待ランタイムを持つ球面$mathcal Sd-1$の正確なサンプリングアルゴリズムを与える。
直接応用として、ランク1行列推論問題の後方分布を時間内にサンプリングする。
論文 参考訳（メタデータ） (2020-09-30T22:48:03Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Learning and Sampling of Atomic Interventions from Observations [11.522442415989818]
本研究では, 因果ベイズネットワークにおける観測サンプルを用いて, 介入が単一変数(原子介入)に与える影響を効率的に推定する問題について検討した。
我々のゴールは、非パラメトリックな設定で時間とサンプルの複雑さの両方で効率的なアルゴリズムを提供することです。
論文 参考訳（メタデータ） (2020-02-11T07:15:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。