論文の概要: A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms

• arxiv url: http://arxiv.org/abs/2609.40062v1
• Date: Wed, 30 Sep 2026 16:21:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.034569
• Title: A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms
• Title（参考訳）: 重み付きコセットアルゴリズムのためのフーリエラベル情報損失バリア
• Abstract要約: 我々は、二面コセット問題(DCP)に対する幅広いクラスの量子アルゴリズムのノーゴー定理を確立する。 本稿では,Regev (SIAM Journal on Computing, 2004) が提案するフーリエサンプリングとサブセットサム測定のテンプレートについて考察する。
• 参考スコア（独自算出の注目度）: 9.824136194395253
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template proposed by Regev (SIAM Journal on Computing, 2004), which is one of the main approaches to solving DCP. Suppose that, after measuring the lower $n-1$ bits of the subset sum, the algorithm discards any $ω(\log n)$ bits from each of the Fourier labels. Then we prove that the algorithm cannot succeed in solving DCP. This shows that any algorithm following this template must make extensive use of the Fourier labels, and thus serves as a useful guide for developing algorithms for DCP. As a main application, we show that the recent algorithm by Simon (IACR ePrint:2026/1591, August 11 2026) does not solve DCP. We show that after the subset-sum measurement, this algorithm can be implemented (up to exponentially-small error) using only the most-significant third of the Fourier labels, and is therefore subject to our general no-go theorem. To help with verifiability, we release Lean 4 code for our results.
• Abstract（参考訳）: 我々は、二面コセット問題(DCP)に対する幅広いクラスの量子アルゴリズムに対して、ノーゴー定理を確立する。 本稿では,Regev (SIAM Journal on Computing, 2004) が提案するフーリエサンプリングとサブセットサム測定のテンプレートについて考察する。 このアルゴリズムは、サブセット和の低い$n-1$ビットを測定した後、フーリエラベルから任意の$ω(\log n)$ビットを廃棄する。 そして,このアルゴリズムは DCP の解法に成功できないことを証明した。 これは、このテンプレートに従うアルゴリズムは、Fourierラベルを広範囲に利用する必要があることを示し、したがって、DCPのアルゴリズムを開発するための有用なガイドとなる。 主な応用として,近年のSimon (IACR ePrint:2026/1591, August 11 2026) によるアルゴリズムは DCP を解くことができないことを示す。 このアルゴリズムは、サブセットサム測定の後、フーリエラベルの3分の1だけを用いて(指数関数的に小さな誤差まで)実装できることを示し、従って一般のno-go定理に従う。 検証性を支援するため、結果のためにLean 4のコードをリリースしています。

関連論文リスト

• Fast and Simple Densest Subgraph with Predictions [0.0]
  学習強化アルゴリズムのレンズを用いて,最も高密度な部分グラフ問題とその変種について検討する。 部分解が与えられた場合、証明可能な$(1-epsilon)$-approximationを達成する非常に単純な線形時間アルゴリズムを設計できることを示す。 また,本手法は有向高密度部分グラフ問題やNP-ハード変種にも自然に適用できる。
  論文  参考訳（メタデータ） (2025-05-19T01:32:03Z)
• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。 このアルゴリズムは古典的および量子速度歪み理論に適用できる。
  論文  参考訳（メタデータ） (2024-08-10T06:16:24Z)
• Private Geometric Median [10.359525525715421]
  データセットの幾何中央値(GM)を計算するための差分プライベート(DP)アルゴリズムについて検討する。 我々の主な貢献は、データポイントの有効直径でスケールする過剰なエラー保証を備えたプライベートGMのタスクのためのDPアルゴリズムのペアである。
  論文  参考訳（メタデータ） (2024-06-11T16:13:09Z)
• Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning [4.10375234787249]
  教師なし学習問題に対する効率的なアルゴリズム設計のための枠組みを提案する。 我々のフレームワークは,雑音の存在下で演算回路を学習するメタアルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2023-11-13T12:26:25Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• A proximal-proximal majorization-minimization algorithm for nonconvex tuning-free robust regression problems [4.261680642170457]
  非回帰問題に対する PMM (proximal-proximal majorization-minimization) アルゴリズムを提案する。 提案アルゴリズムは既存の最先端アルゴリズムよりも優れている。
  論文  参考訳（メタデータ） (2021-06-25T15:07:13Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。 我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
  論文  参考訳（メタデータ） (2020-10-04T22:19:06Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• The Kikuchi Hierarchy and Tensor PCA [50.840260149979265]
  テンソルPCA(主成分分析)問題に対して,ランタイムの増大を伴うアルゴリズムの階層化を提案する。 我々の階層は、SOS(sum-of-squares)階層に似ているが、代わりに統計物理学や関連するアルゴリズムにインスパイアされている。
  論文  参考訳（メタデータ） (2019-04-08T06:26:35Z)

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

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