論文の概要: Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions

• arxiv url: http://arxiv.org/abs/2610.37122v1
• Date: Tue, 27 Oct 2026 12:21:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-28 21:04:31.583943
• Title: Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions
• Title（参考訳）: 行列サンプリング器と量子証明エクストラクタ--その対応性とほぼ最適構成
• Abstract要約: 行列サンプリング器と量子保護ランダムネス抽出器の等価性を確立する。 最適ランダム性オーバーヘッドと準最適サンプル複雑性を有する明示的な強い行列サンプリング器を構築した。
• 参考スコア（独自算出の注目度）: 3.8530395083350606
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We establish an equivalence between matrix samplers and quantum-proof randomness extractors. The classical sampler--extractor equivalence is established by a seminal work of Zuckerman (Random Structures & Algorithms, 1997). Using this equivalence, we construct explicit strong matrix samplers with optimal randomness overhead and near-optimal sample complexity via constructing quantum-proof extractors. Specifically for matrix dimension $D$, accuracy $\varepsilon$ and failure probability $δ\leq\varepsilon$, our matrix sampler uses $m+O_α(\log(D/δ))$ random bits and $O_α(\varepsilon^{-2-α}\log^{1+α}(D/δ))$ samples, for any constant $α>0$. Compared with the matrix sampler of Xun and Zuckerman (CCC 2025), our construction has improvements in two aspects. Under the same optimal random seed length, we can replace the $\operatorname{poly} D$ dependence in the number of samples by $O(\log^{1-γ} D)$. Under the same scale of sample size, we can remove their $\log\log D$ factor in the length of the random seed. Our underlying strong quantum-proof extractor has output length $n-O_α(a+\log(1/η))$ and seed length at most $(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $η$. We also obtain strong quantum-proof extractors for every constant entropy rate, for any error as small as $2^{-Ω(n)}$, having optimal seed length $O(\log(n/η))$ and output length $Ω(n)$, improving previous constructions.
• Abstract（参考訳）: 行列サンプリング器と量子保護ランダムネス抽出器の等価性を確立する。 古典的なサンプル-抽出等価性は、Zuckerman (Random Structures & Algorithms, 1997) のセミナーによって確立される。 この等価性を用いて、量子保護抽出器の構築により、最適ランダム性オーバーヘッドと準最適サンプル複雑性を有する明示的な強い行列サンプリング器を構築する。 具体的には、行列次元$D$、精度$\varepsilon$および故障確率$δ\leq\varepsilon$に対して、我々の行列サンプルは、任意の定数$α>0$に対して$m+O_α(\log(D/δ))$ランダムビットと$O_α(\varepsilon^{-2-α}\log^{1+α}(D/δ))$サンプルを使用する。 Xun と Zuckerman (CCC 2025) の行列標本と比較すると, 構造は2つの点で改善されている。 同じ最適なランダムシード長の下では、サンプル数に対する$\operatorname{poly} D$依存を$O(\log^{1-γ} D)$で置き換えることができる。 同じサンプルサイズで、ランダムシードの長さに$\log\log D$ factorを除去できる。 我々の根底にある強力な量子防御抽出器は出力長$n-O_α(a+\log(1/η))$と最大値$(1+α)\log a+(2+α)\log(1/η)+O_α(1)$ for $n$-bit sources with conditional min-entropy $n-a$ and error $η$である。 また、全ての一定のエントロピーレートに対して、最適なシード長$O(\log(n/η))$と出力長$Ω(n)$を持つ誤差を2^{-Ω(n)}$とすることで、前の構成を改善する。

関連論文リスト

• Efficient Quantum State Identity Testing [0.7639235704257864]
  回路深度とサンプル複雑度を相補的に保証する2つの量子アルゴリズムを提案する。 1つは、並列スワップテストを使用して一定の深さで実行し、各入力状態のコピーを$O(log(n/)log(2/))で、少なくとも1-$の確率で成功する。 第二に、サンプルの複雑さを$O(log(n/))$に減らし、Jucys--Murphy 要素と Schur サンプリングに関する分析を行う。
  論文  参考訳（メタデータ） (2026-10-03T15:33:21Z)
• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Tight Sample Bounds for Renyi and Min-Entropy Estimation [4.866431869728017]
  サンプルからエントロピーを推定することは、情報理論とプロパティテストにおいて基礎となる。 定数加法精度に対する最小エントロピー推定が標本複雑性$(klog k)$であることを証明する。
  論文  参考訳（メタデータ） (2026-07-18T21:01:38Z)
• Improved sample complexity bound for sample-based Lindbladian simulation [10.583368233681378]
  We established improve sample-complexity bounds for sample-based Lindbladian Simulation based on the Wave Matrix Lindbladization (WML) algorithm。 次元 $d$ のジャンプ作用素 $L$ に対して、明示的な非漸近的なサンプル複雑性を$n_d*(t,varepsilon) le left( frac2d+38 right) |L|_infty2 left( fract2varepsilon right) で導いた。
  論文  参考訳（メタデータ） (2026-05-28T17:46:25Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity [6.812247730094931]
  任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。 また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
  論文  参考訳（メタデータ） (2023-09-25T09:50:15Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Classical shadows of fermions with particle number symmetry [0.0]
  我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。 ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
  論文  参考訳（メタデータ） (2022-08-18T17:11:12Z)

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

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