論文の概要: Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

• arxiv url: http://arxiv.org/abs/2610.06721v1
• Date: Mon, 05 Oct 2026 17:13:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 23:22:59.800393
• Title: Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness
• Title（参考訳）: 量子サンプリングのための厳密なクエリローバウンドと証明ランダムネスへの応用
• Abstract要約: 我々は、信頼できない量子デバイスについて、高いXEBスコアが何を示すかを調査する。 量子クエリーモデルでは、真正なサンプリング器の理想的なスコアが効率的なデバイスに対してTsirelsonバウンドとして機能することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we show that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness. First, exceeding the ideal score by a constant requires $Ω(N^{1/3})$ queries for the Haar and Fourier oracle ensembles with $N$ outcomes, and this bound is tight; this proves an earlier conjecture for Haar-random states and extends it to Fourier sampling. Second, for Fourier sampling and for Haar-random states accessed through the canonical state-preparation oracle, the $n$-bit output of a device that makes polynomially many queries and scores within $o(1)$ of the ideal score has $n-O(\log n)$ bits of smooth min-entropy, even against an adversary who is entangled with the device and later learns the oracle; this is nearly optimal. As a corollary, sampling the collision distribution, which is proportional to the square of the ideal distribution, has query complexity $Θ(N^{1/3})$, and a coherent version of the same algorithm approximately prepares quantum Hadamard products of states with uniform amplitude magnitudes. Both lower bounds rest on progress measures that bound the excess over the ideal score and increase only slightly with each query. For Fourier sampling the measure is the norm of the coherent amplitudes for removing pairs in a purification of the random function, combining the polynomial method with the compressed oracle technique; for Haar-random states it is the square root of the average level in an expansion in Dirichlet orthogonal polynomials, controlled by an exact identity for the effect of one observation.
• Abstract（参考訳）: 量子計算優位の先駆的な実証であるランダム回路サンプリング実験は、線形クロスエントロピーベンチマーク(XEB)を用いてテストされ、その理想的な確率で結果を評価する。 我々は、信頼できない量子デバイスについて、高いXEBスコアが何を示すかを調査する。 量子クエリモデルでは、真正なサンプリング器の理想的なスコアが、効率的なデバイスと証明されたランダム性のためにTsirelsonバウンドとして機能することを示す。 第一に、定数による理想的なスコアを超えるためには、ハールとフーリエのオラクルのアンサンブルに対する$Ω(N^{1/3})$クエリと$N$の結果が必要であり、この境界は厳密である。 第二に、フーリエサンプリングとハールランダム状態が正準状態準備オラクルを通してアクセスされる場合、理想スコアの$o(1)$以内に多項式的に多くのクエリとスコアを出力するデバイスの$n$-bitの出力は、デバイスに絡み合って後にオラクルを学ぶ敵に対しても、滑らかなミンエントロピーのビットが$n-O(\log n)$である。 座標系として、理想的な分布の平方に比例する衝突分布をサンプリングすると、クエリ複雑性は$(N^{1/3})$であり、同じアルゴリズムのコヒーレントなバージョンは、一様振幅の等級を持つ状態の量子アダマール積をほぼ準備する。 両方の下位境界は、理想的なスコアを越えて過大な値を束縛し、クエリごとにわずかに増加するプログレス測度に依存している。 フーリエサンプリングの場合、この測度はランダム関数の精製においてペアを除去するコヒーレント振幅のノルムであり、多項式法と圧縮オラクル法を組み合わせることで、ハールランダムはディリクレ直交多項式の展開における平均レベルの平方根であり、1つの観測の効果に対する正確な同一性によって制御される。

関連論文リスト

• Towards Optimal Quantum Estimators for State Frame Potential [12.326210204717336]
  本稿では, 3 つのより弱いアクセスモデルの下で, 次数 $t$ の状態フレームポテンシャルを付加誤差 $varepsilon$ に推定する問題について検討する。 クエリモデルでは、$widetilde(sqrtt/varepsilon)$のほぼ最適クエリ複雑性を確立します。 一般的なサンプルモデルでは、最適なサンプル複雑性を$(t/varepsilon2)$とする。
  論文  参考訳（メタデータ） (2026-08-25T15:29:24Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems [1.0878040851638]
  我々は3世代にわたるD-Wave量子アニールのベンチマークを報告する。 イジングあるいは等価なQUBOは、これらの問題の定式化は順序の減少のために補助変数を必要としない。
  論文  参考訳（メタデータ） (2023-01-08T10:02:56Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  我々は、係数に応じてハミルトン式からサンプリングしてランダムな積公式を構築するqDriftプロトコルを導入する。 サンプリング段階における個別のシミュレーションコストを考慮し、同じ精度でシミュレーションコストを削減可能であることを示す。 格子核効果場理論を用いて数値シミュレーションを行った結果, 実験結果が得られた。
  論文  参考訳（メタデータ） (2022-12-12T15:06:32Z)
• Testing randomness of series generated in Bell's experiment [62.997667081978825]
  おもちゃの光ファイバーをベースとしたセットアップを用いてバイナリシリーズを生成し、そのランダム度をVilleの原理に従って評価する。 標準統計指標の電池、ハースト、コルモゴロフ複雑性、最小エントロピー、埋め込みのTakensarity次元、および拡張ディッキー・フラーとクワイアトコフスキー・フィリップス・シュミット・シン(英語版)でテストされ、ステーション指数をチェックする。 Toeplitz 抽出器を不規則級数に適用することにより得られる系列のランダム性のレベルは、非還元原料のレベルと区別できない。
  論文  参考訳（メタデータ） (2022-08-31T17:39:29Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• Efficient approximation of experimental Gaussian boson sampling [2.805766654291013]
  最近の2つの目覚しい実験は、最大144個の出力モードで、プログラム不可能な線形干渉計としきい値検出器を備えたガウスボソンサンプリング(GBS)を行った。 ここでは、これらの実験よりも全変動距離とクルバック・リーブラーの偏差がよい古典的なサンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-23T17:47:06Z)

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

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