論文の概要: Rigorous Statements and Proofs of the Lemmas in Simon's Algorithm for the Dihedral Coset Problem and Their Underlying Hypothesis

• arxiv url: http://arxiv.org/abs/2608.16598v1
• Date: Mon, 17 Aug 2026 13:53:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-18 19:59:03.736098
• Title: Rigorous Statements and Proofs of the Lemmas in Simon's Algorithm for the Dihedral Coset Problem and Their Underlying Hypothesis
• Title（参考訳）: 双面コセット問題に対するシモンのアルゴリズムとそれに基づく仮説の厳密な記述と証明
• Abstract要約: シモンはディヘドラルコセット問題に対する計算時間量子アルゴリズムを提案し、4つの補題について解析を行った。 それらのうち3つは、証明スケッチのみを持ち、この論文は、それぞれの3人に、完全な証明とともに1つの読書を認める声明を与える。
• 参考スコア（独自算出の注目度）: 16.364682124857485
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In a recent preprint, Simon proposed a polynomial-time quantum algorithm for the Dihedral Coset Problem and rested the analysis on four lemmas. Three of them carry only proof sketches, and this paper gives each of those three a statement that admits a single reading together with a complete proof. Lemma 1 follows from an exact second-moment computation for the subset-sum counts, and it holds with probability tending to one in place of the constant originally claimed. The amplitude bound of Lemma 3 follows from an exact Parseval identity on the cube of measurement outcomes and holds at every threshold with no well-behavedness hypothesis, so that predicate leaves the argument entirely. For Lemma 4, we compute both balls-in-bins covariances exactly and find that the second carries a term a fixed ball count leaves out. The assumption that the distinguished group contains no faulty samples can also be dropped. The two branch amplitudes share a signed prefactor, so the counting estimates control their difference and not the ratio the lemma states. We prove the additive form and show that the closing argument consumes nothing more than that. A single hypothesis survives all of this. It asks that the partition into the two sides be fixed independently of the measured string, and the rule the algorithm gives for choosing that partition does not supply it. Establishing these four lemmas therefore does not by itself establish the correctness of the algorithm.
• Abstract（参考訳）: 最近のプレプリントで、サイモンはディヘドラルコセット問題に対する多項式時間量子アルゴリズムを提案し、4つの補題について解析を行った。 それらのうち3つは、証明スケッチのみを持ち、この論文は、それぞれの3人に、完全な証明とともに1つの読書を認める声明を与える。 Lemma 1 は、サブセットサム数に対する正確な第2モーメント計算から従い、もともと主張されていた定数の代わりに 1 の確率で成り立つ。 Lemma 3 の振幅境界は、測定結果の立方体上の正確なParseval恒等式から導かれ、十分な振る舞いの仮説を持たない全てのしきい値に保持されるため、述語は議論を完全に残す。 Lemma 4 に対して、両球-双対共分散を正確に計算し、第二項が固定球数という項を持つことを確かめる。 卓越した群が欠陥のあるサンプルを含まないという仮定も取り除くことができる。 2つの分岐振幅は符号付きプレファクタを共有するため、カウント推定はその差をレマ状態の比ではなく制御する。 我々は加法形式を証明し、閉引数がそれ以外何も消費しないことを示す。 一つの仮説がこれら全てを生き残る。 二つの辺への分割は測定された文字列とは独立に固定されることを要求し、アルゴリズムが与えるルールはパーティションがそれを供給していないことを判断する。 したがって、これらの4つの補題を確立することは、アルゴリズムの正確性そのものを確立するものではない。

関連論文リスト

• A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving [0.0]
  Huang, Lou, and XiaoはDynamic Mixture-of-Experts Servingを導入し、その積分原始問題に対してO(sqrt(log k))競合ランダム化アルゴリズムを与えた。 ランダム化された原始競合比は、実際には、任意の数の専門家に対して Theta(1) であることを示す。
  論文  参考訳（メタデータ） (2026-08-15T03:51:27Z)
• Split the Labor: Separating Evidence Interpretation from Decision Aggregation [0.0]
  言語モデルに多くの情報源から結論に達するよう要求するシステムは通常、それらを1つのプロンプトに分割する。 提案する4分野のエビデンス(仮説,信頼性バケット,合理性,証明)は,両半減期を決定することを示す。 この修正はアーキテクチャよりも算術的であり、言語モデル以外のルールのクラスに適用される。
  論文  参考訳（メタデータ） (2026-08-14T17:24:55Z)
• Exact minimum measurement dependence for faithful local deterministic models of multipartite GHZ-Mermin correlations [0.0]
  ベルの派生は、局所性、決定性、および測定独立に依存する。 本稿では,メルミン状態そのものに対する最適モデルの忠実バージョンを解く。
  論文  参考訳（メタデータ） (2026-07-31T12:12:03Z)
• The Resolution of Causal Heterogeneity [5.222979968110479]
  因果部分群分析はしばしば、その数がよく定義された推定値であるかのように、治療効果の不均一性を要約する少数の群を報告する。 我々はこれを新しい人口推定法、解像度プロファイル、因果的特徴法の機能に置き換える。 推論は、1つの構造化モーメントプロセスのために、1つのクロスフィットベイズ・ブートストラップ後部を中心に構成される。
  論文  参考訳（メタデータ） (2026-07-19T14:56:06Z)
• Two Calls, Two Moments, and the Vote-Accuracy Curve of Repeated LLM Inference [4.28787537081191]
  条件-i.d.呼び出しの繰り返しLLM推論における二項正当性層について検討した。 固定された多数決投票の予算は、鋭い分布のない2つの呼び出し間隔を持つ。 QNLI と QQP に対する LLM の呼出実験により, 投射した2発呼領域に3発と5発の発声アキュラシーが含まれていることが示された。
  論文  参考訳（メタデータ） (2026-05-05T05:40:09Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Generalization Bounds for Inductive Matrix Completion in Low-noise Settings [46.82705757568271]
  I.d.サブガウス雑音仮定の下で帰納的行列補完(側情報付き行列完備化)について検討する。 初めて、次の3つの性質で有界な一般化が得られる。
  論文  参考訳（メタデータ） (2022-12-16T08:30:41Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。 また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
  論文  参考訳（メタデータ） (2022-09-16T13:59:42Z)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。 ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。 我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-27T11:23:57Z)
• Leveraged Matrix Completion with Noise [84.20092979053119]
  未知の$ntimes n$ matrix of rank $r$ from just $mathcalO(nrlog2 (n))$ entry. 我々の証明は、ゴルフスキームに基づく十分な最適条件を記述する新しいアプローチによって支持されている。
  論文  参考訳（メタデータ） (2020-11-11T16:25:45Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  より弱い仮定として, 2$-adjacency faithfulness を提案します。 より弱い仮定の下で適用可能な因果発見のための音方向規則を提案する。
  論文  参考訳（メタデータ） (2020-10-27T13:04:08Z)

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

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