論文の概要: Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice
- arxiv url: http://arxiv.org/abs/2609.28226v1
- Date: Wed, 23 Sep 2026 14:53:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-25 00:05:18.078823
- Title: Pinpointing Super-Quadratic Quantum Enumeration Speedups: Exact and Certified Evaluation of the Guessing-Moment Exponent under Product-Distribution Advice
- Title（参考訳）: 超量子量子列挙速度のピンポイント化:製品流通アドバイザによるゲスティング・モーメント指数の実行と評価
- Abstract要約: 与えられたアドバイス分布によって誘導される量子古典的推測モーメント分離を評価するための有限サイズ手法を提案する。
本フレームワークは,シードおよびブロック暗号キー上のコールドブートリーク,テンプレートアタック後部,および合成ベルヌーイ後部に適用する。
- 参考スコア（独自算出の注目度）: 1.8224992311090216
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Grover's algorithm gives an optimal quadratic query advantage for black-box search. In cryptanalysis, however, the search often comes with additional probabilistic advice over the candidates, frequently of product form, e.g. from side-channel leakage on independent key coordinates. Classically, guessing in likelihood order is optimal in expectation. In the quantum setting, Montanaro showed how to achieve an optimal expected query complexity, beating plain Grover on every non-uniform advice distribution (up to a constant overhead factor). What has been missing so far is a finite-size method for evaluating the quantum-classical guessing-moment separation induced by a given advice distribution. We provide such a method for product-distribution advice, thereby sharpening the previous entropy-based estimate of Bashiri et al. We reduce the classical and quantum guessing moments to functionals of the one-dimensional surprisal distribution, obtained for product advice by convolving the per-coordinate surprisal laws. When the surprisals lie on a common arithmetic grid (the commensurate case), the logarithmic moments and hence the speedup exponent can be evaluated as finite sums without discretization error; exponential tilting makes this computation numerically stable. For general product advice, we discretize the surprisals onto a common grid and derive an a-posteriori bound on the resulting binning error. We apply the framework to cold-boot leakage on seeds and block-cipher keys, to template-attack posteriors, and to synthetic i.i.d. Bernoulli posteriors calibrated to residual ranks reported for Keccak side-channel attacks on ML-KEM and ML-DSA. The resulting exponents substantially exceed 2 in several skewed-advice settings, reaching up to 3.97 in these synthetic models, and include cases where the previous entropy-based bound did not establish an exponent above 2.
- Abstract（参考訳）: グローバーのアルゴリズムはブラックボックス探索に最適2次クエリの利点を与える。
しかし、暗号解析では、独立鍵座標上のサイドチャネルリークなど、しばしば製品形式の候補に対して、探索にはさらなる確率的アドバイスが伴うことが多い。
古典的には、可能性順序の推測は予想において最適である。
量子設定において、モンタナロは最適なクエリ複雑性を達成する方法を示し、(一定のオーバーヘッド係数まで)一様でないアドバイス分布でGroverを圧倒した。
これまでに欠けているのは、与えられたアドバイス分布によって誘導される量子古典的推測モーメント分離を評価する有限サイズ法である。
そこで本論文では, 製品流通アドバイスの方法として, 従来のエントロピーに基づくバシリ等の推定値の精度向上を図り, 古典的および量子的推定モーメントを1次元の素数分布の関数に還元する手法を提案する。
仮定が共通の算術格子上に置かれる場合(計算の場合)、対数モーメント、従ってスピードアップ指数は離散化誤差なしで有限和として評価できる。
一般的な製品アドバイスとして、仮定を共通格子に識別し、その結果の双対誤差に縛られたa-ポストエロリを導出する。
本フレームワークは,シードおよびブロック暗号キーのコールドブートリーク,テンプレートアタック後部,およびケッカック側チャネル攻撃およびML-DSAに対するケッカック側チャネル攻撃で報告された残留ランクに調整されたBernolli後部合成に適用した。
結果として得られる指数は、複数のスキュード・アドレッシング・セッティングにおいて2よりも大きく、これらの合成モデルでは最大3.97まで到達し、前のエントロピーベース境界が2以上の指数を確立しなかった場合を含む。
関連論文リスト
- A Sum-of-Squares Hierarchy with Quadratic Convergence for Quantum Channel Coding [0.8594140167290097]
対称拡張に基づく既存のプログラミング階層は、拡張レベルの逆二乗根として崩壊する先行誤差推定を伴う収束上界を提供する。
我々は任意の数のメッセージに対してエルミート的な2乗和階層を構築し、そのレベルで2次収束を証明した。
バイナリメッセージの場合、得られた境界は、トレース-ノルム-ノルム係数の上から乗法近似を与える。
論文 参考訳（メタデータ） (2026-09-09T02:40:37Z) - Unified High-Probability Analysis of Stochastic Variance-Reduced Estimation [15.37118525209153]
本稿では,メモリ保持,リセット確率,反復運動の補正項という3つの要素からなる再帰に基づく分散推定のための統一的フレームワークを開発する。
我々の主な結果は、ベクトルマーチンガレットのランダム和を含む滑らかなノルム空間に対して有効である新しい次元自由ベクトル値フリードマンを用いて証明された統一された高確率境界である。
応用として、ミラー降下による非拘束最適化のための高確率オラクル複素数を求め、信頼度に対数的依存を確立する。
論文 参考訳（メタデータ） (2026-05-14T20:17:10Z) - Characterizing Trainability of Instantaneous Quantum Polynomial Circuit Born Machines [7.716642023459826]
瞬時量子回路Born Machine (IQP-QCBM) は量子生成モデルとして提案されている。
我々は、バレン高原が選択されたカーネルのジェネレータセットとスペクトルに依存することを示す。
低重バイアスのカーネルが構造的トポロジの指数的抑制を回避する機構を同定する。
論文 参考訳（メタデータ） (2026-02-11T17:12:56Z) - Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation [4.479120626873489]
本研究では, 量子コンピューティングを用いて, 一定の水平線(ネスト数)で繰り返しネスト予測(RNE)を推定する。
本稿では、対数係数まで、コスト$tilde O(varepsilon-1)$で$varepsilon$-errorを実現する量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-02-08T20:55:12Z) - Quantum algorithm for approximating the expected value of a random-exist quantified oracle [0.0]
量子振幅増幅と推定は、非構造化探索と推定タスクに二次的なスピードアップを示す。
これらの量子アルゴリズムのコヒーレントな組み合わせは、ランダムに存在する量子化されたオラクルの期待値を計算するための二次的なスピードアップも提供することを示す。
論文 参考訳（メタデータ） (2024-11-30T19:42:08Z) - Cloning Games, Black Holes and Cryptography [50.022147589030304]
クローンゲーム解析のための新しいツールキットを提案する。
このフレームワークにより、バイナリフェーズ状態に基づいて新しいクローンゲームを分析することができる。
連成位相の変分最適境界は、ブラックホールの理想化されたモデルで衝突する情報について定量的な洞察を与えることを示す。
論文 参考訳（メタデータ） (2024-11-07T14:09:32Z) - Testing randomness of series generated in Bell's experiment [62.997667081978825]
おもちゃの光ファイバーをベースとしたセットアップを用いてバイナリシリーズを生成し、そのランダム度をVilleの原理に従って評価する。
標準統計指標の電池、ハースト、コルモゴロフ複雑性、最小エントロピー、埋め込みのTakensarity次元、および拡張ディッキー・フラーとクワイアトコフスキー・フィリップス・シュミット・シン(英語版)でテストされ、ステーション指数をチェックする。
Toeplitz 抽出器を不規則級数に適用することにより得られる系列のランダム性のレベルは、非還元原料のレベルと区別できない。
論文 参考訳（メタデータ） (2022-08-31T17:39:29Z) - Average-case Speedup for Product Formulas [69.68937033275746]
製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。
我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。
我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
論文 参考訳（メタデータ） (2021-11-09T18:49:48Z) - Tight Exponential Analysis for Smoothing the Max-Relative Entropy and
for Quantum Privacy Amplification [56.61325554836984]
最大相対エントロピーとその滑らかなバージョンは、量子情報理論の基本的な道具である。
我々は、精製された距離に基づいて最大相対エントロピーを滑らかにする量子状態の小さな変化の崩壊の正確な指数を導出する。
論文 参考訳（メタデータ） (2021-11-01T16:35:41Z) - Best Arm Identification for Cascading Bandits in the Fixed Confidence
Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。
CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。
その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文 参考訳（メタデータ） (2020-01-23T16:47:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。