論文の概要: Product testing with single-copy measurements

• arxiv url: http://arxiv.org/abs/2510.07820v1
• Date: Thu, 09 Oct 2025 06:01:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:14.896442
• Title: Product testing with single-copy measurements
• Title（参考訳）: 単一コピー計測による製品テスト
• Authors: Jacob Beckey, Luke Coffman, Ariel Shlosberg, Louis Schatzki, Felix Leditzky,
• Abstract要約: 単一コピー測定に制限された2種類の製品テストのサンプル複雑性について検討した。 特に、両部製品テスト(すなわち、状態が製品であるような、少なくとも1つの非自明なカットが存在するか)と多部製品テスト(すなわち、各カットにまたがる状態は完全に製品である)の両方を考慮する。
• 参考スコア（独自算出の注目度）: 5.89376242995877
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we study the sample complexity of two variants of product testing when restricted to single-copy measurements. In particular, we consider both bipartite product testing (i.e., does there exist at least one non-trivial cut across which the state is product) and multipartite product testing (i.e., is the state fully product across every cut). For the first variant, we prove an exponential lower bound on the sample complexity of any algorithm for this task which utilizes only single-copy measurements. When comparing this with known efficient algorithms that utilize multi-copy measurements, this establishes an exponential separation for this and several related entanglement learning tasks. For the second variant, we prove another sample lower bound that establishes a separation between single- and multi-copy strategies. To obtain our results, we prove a crucial technical lemma that gives a lower bound on the overlap between tensor products of permutation operators acting on subsystems of states that themselves carry a tensor structure. Finally, we provide an algorithm for multipartite product testing using only single-copy, local measurements, and we highlight several interesting open questions arising from this work.
• Abstract（参考訳）: 本研究では, 単一コピー計測に制限された2種類の製品テストのサンプル複雑性について検討した。 特に、両部製品テスト(すなわち、状態が製品であるような、少なくとも1つの非自明なカットが存在するか)と多部製品テスト(すなわち、各カットにわたる状態完全製品)の両方を考慮する。 最初の変種について、単一コピー計測のみを利用するこのタスクに対して、任意のアルゴリズムのサンプリング複雑性の指数的下界を証明した。 これを、マルチコピー計測を利用する既知の効率的なアルゴリズムと比較すると、これと関連する絡み合い学習タスクの指数的分離が確立される。 2つ目の変種について、単コピー戦略と複数コピー戦略の分離を確立する別のサンプル下界を証明した。 この結果を得るためには、テンソル構造を持つ状態のサブシステムに作用する置換作用素のテンソル積間の重なり合いを低くする重要な技術的補題が証明される。 最後に,単一コピー,局所測定のみを用いた多部製品テストのためのアルゴリズムを提案し,本研究から得られたいくつかの興味深いオープンな疑問を強調した。

関連論文リスト

• Robust Self-Testing of Multiqudit Supersinglet Slater States via Constant Number of Binary Measurements [0.0]
  自己検査は、観測された相関のみに基づいて、量子状態と物理実験にかかわる測定の両方の形を推定できる強力な技術である。 本稿では,観測者毎に一定数の2値測定しか行わない,真に絡み合った状態の関連クラスの最初の自己検定手法を提案する。
  論文  参考訳（メタデータ） (2025-08-21T13:27:20Z)
• On the Structure of Replicable Hypothesis Testers [26.31630129580797]
  仮説テストアルゴリズムは、同じ分布から2つの異なるサンプルを走らせると、高い確率で同じ出力を生成する場合に複製可能である。 レプリカ可能なテスタのサンプル複雑性に対して,下限と上限を証明するための一般的なツールを構築します。 正準特性の集合を同定し、これらの特性を満たすために任意のレプリカブルなテストアルゴリズムを変更可能であることを証明する。
  論文  参考訳（メタデータ） (2025-07-03T17:51:31Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。 グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。 提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
  論文  参考訳（メタデータ） (2024-02-08T14:43:56Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Distributed quantum inner product estimation [14.222887950206658]
  2つの量子コンピュータ上で準備された状態の忠実度を推定することを目的とした、クロスプラットフォーム検証として知られるベンチマークタスクが提案されている。 ハードウェアの制約により、2つの物理プラットフォーム間で量子通信を行うことはできない。 サンプルの複雑さは、最強の設定でも少なくとも$Omega(max1/varepsilon2,sqrtd/varepsilon)$でなければならない。
  論文  参考訳（メタデータ） (2021-11-05T05:35:03Z)
• Sampling from a $k$-DPP without looking at all items [58.30573872035083]
  カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。 既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。 そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-06-30T16:40:44Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Genetic Algorithms for Redundancy in Interaction Testing [0.6396288020763143]
  インタラクションテストには一連のテストの設計が含まれており、少数のコンポーネントが連携して動作する場合、障害を検出することが保証される。 これらのテストスイートを構築するための既存のアルゴリズムは通常、ほとんどのテストを生成する1つの"高速"アルゴリズムと、テストスイートを"完全"する別の"より遅い"アルゴリズムを含んでいる。 我々は、これらのアプローチを一般化する遺伝的アルゴリズムを用いて、選択したアルゴリズムの数を増やして冗長性も含み、それを「ステージ」と呼ぶ。
  論文  参考訳（メタデータ） (2020-02-13T10:16:46Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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