論文の概要: Learning Sparse Quantum States
- arxiv url: http://arxiv.org/abs/2609.12219v1
- Date: Thu, 10 Sep 2026 21:28:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-15 07:38:31.54739
- Title: Learning Sparse Quantum States
- Title（参考訳）: スパース量子状態の学習
- Abstract要約: 我々は、$n$-qubit $k$-sparse純量子状態を学ぶための最初の近似アルゴリズムを与える。
我々は、$tildeO(k/varepsilon)$状態のコピーと$tildeO(kn/varepsilon)$時間を使って、高い確率で少なくとも1-varepsilon$を得る。
例えば、ほぼ最適な$tildeO(kr/varepsilon)$サンプル複雑性を持つアルゴリズムも得られ、$k$-sparse rank-$rを学習する。
- 参考スコア（独自算出の注目度）: 0.8122270502556375
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of tomography for $k$-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning $n$-qubit $k$-sparse pure quantum states, obtaining fidelity at least $1-\varepsilon$ with high probability using $\tilde{O}(k/\varepsilon)$ copies of the state and $\tilde{O}(kn/\varepsilon)$ time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal $\tilde{O}(kr/\varepsilon)$ sample complexity for learning $k$-sparse rank-$r$ mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for $r>1$, remains an important open question.
- Abstract（参考訳）: 我々は、$k$sparse量子状態に対するトモグラフィーの問題を研究する。
古典的な分布学習とは対照的に、サポートサイズの観点からは、厳密なサンプルと時間複雑性の境界がよく理解されているため、この問題に対して非自明な境界がこれまで示されていなかった。
我々は、$n$-qubit $k$-sparse純量子状態を学ぶための最初の近似アルゴリズムを与え、$\tilde{O}(k/\varepsilon)$状態のコピーと$\tilde{O}(kn/\varepsilon)$時間を使って、高い確率で少なくとも1-\varepsilon$を得る。
どちらの境界も多対数因子に最適である。
また、ランダムな浄化チャネル技術を用いて、$k$-sparse rank-$r$混合状態の学習に最適な$\tilde{O}(kr/\varepsilon)$サンプル複雑性を持つアルゴリズムも得られる。
サンプルの複雑さとほぼ一致する時間的複雑さを$r>1$で達成することは、依然として重要なオープンな問題である。
関連論文リスト
- Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model [67.75889920324124]
最短経路問題(SSP)問題において,$$-optimal Policy($-optimal Policy)を学習する際のサンプル複雑性について検討した。
我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
驚くべきことに、$c_min = 0$のSSP問題はいつでも学習できない。
論文 参考訳（メタデータ） (2026-04-17T14:47:52Z) - Sample-optimal single-copy quantum state tomography via shallow depth measurements [0.42970700836450487]
深度$mathcalO!left(fracd3epsilon2right)$n$-qubitシステム上で2つのコントリビューションを行う。
まず、ランク-r$$$d$-dimensional state $$は、サンプル複雑性$mathcalO!left(tfracdr2 ln depsilon2right)$で達成できる。
第二に、$r = d$の一般的な場合、$lnを削除できる。
論文 参考訳（メタデータ） (2025-09-16T05:54:01Z) - Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
勾配降下は連続最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、クエリの複雑さを$widetildeO (1/varepsilon)$とすることで、その勾配の$varepsilon$-approximationを返す量子アルゴリズムを提案する。
また、ニュートン法の量子アナログを改善することを目的としたヘッセン推定のための2つの量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-04T11:03:48Z) - 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) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - 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 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。