論文の概要: Fully tolerant product state testing and closest product state learning
- arxiv url: http://arxiv.org/abs/2610.01979v1
- Date: Thu, 01 Oct 2026 16:25:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-03 01:19:24.277523
- Title: Fully tolerant product state testing and closest product state learning
- Title（参考訳）: 完全寛容な製品状態テストと最も近い製品状態学習
- Abstract要約: 未知の$n$-qudit状態$$が製品状態に対して$a$-closeなのか、それとも製品状態から遠く離れた$b$-farなのかをテストする問題に対処する。
我々は、未知の状態のコピー数$n$非依存の問題を解くための時間効率のアルゴリズムを提供する。
特に、$widetildeObig((nd)2big), 2widetildeO(1/varepsilon8)$の未知の状態をコピーして生成するアルゴリズムを与えます。
- 参考スコア（独自算出の注目度）: 3.3263205689999444
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of testing whether an unknown $n$-qudit state $ρ$ is $a$-close to a product state or $b$-far away from any product state, as measured in terms of state overlap. We provide a time-efficient algorithm to solve this problem that requires an $n$-independent number of copies of the unknown state. Our random coloring argument shows that for any unknown state there always exists a partition of $[n]$ into $q$ parts such that the square of the overlap with the closest product state with respect to this partition is only an additive factor $O(1/q)$ larger. This reduces the problem to tolerant testing of $q$ parties, with potentially growing local dimensions. Combining this insight with blockwise spectral projection arguments we can show that the natural $k$-copy generalization of Harrow & Montanaro's product state test provides an efficient tolerant tester. We use the same random coloring and blockwise spectral projection techniques to obtain a substantially improved algorithm for closest product state learning. In particular we give an algorithm that takes in $\widetilde{O}\big((nd)^2\big)\, 2^{\widetilde{O}(1/\varepsilon^8)}$ copies of the unknown state and produces an $\varepsilon$-approximately optimal product state. The key technical components of this learner are a qudit variant of the Bakshi et al. high-fidelity product state learning algorithm and a sampling technique based on Werner's optimal cloning channel.
- Abstract（参考訳）: 状態重なりの観点から、未知の$n$-qudit状態$ρ$が製品状態に$a$-closeであるか、あるいは任意の製品状態から$b$-far離れているかをテストする問題に対処する。
我々は、未知の状態のコピー数$n$非依存の問題を解くための時間効率のアルゴリズムを提供する。
ランダムな色付けの議論は、任意の未知の状態に対して常に$[n]$から$q$への分割が存在し、この分割に関して最も近い積状態との重なり合いの正方形が単に加法的因子$O(1/q)$であることを示している。
これにより、局所的な次元が増大する可能性のある$q$パーティの耐久テストに問題が軽減される。
この洞察をブロックワイズスペクトル射影論と組み合わせることで、Harrow & Montanaro の積状態テストの自然な $k$-copy の一般化が、効率的な耐久テストを提供することを示すことができる。
我々は、同じランダムな色付けとブロックワイドスペクトル投影技術を用いて、最も近い製品状態学習のための大幅に改良されたアルゴリズムを得る。
特に、未知の状態のコピーを$\widetilde{O}\big((nd)^2\big)\, 2^{\widetilde{O}(1/\varepsilon^8)}$とすると、$\varepsilon$-a optimal product stateが生成される。
この学習者の重要な技術要素は、Bakshi et al 高忠実度製品状態学習アルゴリズムのqudit変種と、Wernerの最適なクローンチャネルに基づくサンプリング技術である。
関連論文リスト
- Agnostic Product Mixed State Tomography via Robust Statistics [43.0170609941244]
本研究では, アンザッツを混合した非依存トモグラフィーの問題点を考察する。
目標は、ほぼ自明な混合状態近似を$rho$に出力することである。
そこで本研究では,製品混合状態の非依存トモグラフィーから,二項積分布を逐次学習する古典的タスクへの,新たなブラックボックス効率の低下を実証する。
論文 参考訳（メタデータ） (2025-10-09T17:13:03Z) - Learning the closest product state [12.421740476704759]
我々は、$rho$のコピーを与えられた未知の$n$-qubit量子状態$rho$に最適な(純粋な)積状態を求める問題を研究する。
我々は、$N = ntextpoly (1/varepsilon)$コピーの$rho$と$textpoly(N)$クラシックオーバーヘッドを使って、製品フィデリティの$varepsilon$-closeを最適に見つけるアルゴリズムを与える。
論文 参考訳（メタデータ） (2024-11-06T22:08:08Z) - Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer [7.319050391449301]
量子状態の近接性の基本的な尺度として、トレース距離と不完全性は、一般に量子状態の識別、認証、トモグラフィーに使用される。
本稿では, 純状態間のトレース距離と平方根の忠実度を, 同一コピーへのサンプルアクセスを条件として, 加算誤差$varepsilon$で推定する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-28T16:48:21Z) - 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) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - 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) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。