論文の概要: An efficient quantum algorithm for computing $S$-units and its applications

• arxiv url: http://arxiv.org/abs/2510.02280v1
• Date: Thu, 02 Oct 2025 17:54:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 16:59:21.274232
• Title: An efficient quantum algorithm for computing $S$-units and its applications
• Title（参考訳）: S$単位計算のための効率的な量子アルゴリズムとその応用
• Authors: Jean-Francois Biasse, Fang Song,
• Abstract要約: 我々は、数群の$S$単位群を計算するために、Biasse and Song(SODA 16)の量子時間アルゴリズムの証明について詳しく述べる。
• 参考スコア（独自算出の注目度）: 0.3867363075280543
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we provide details on the proofs of the quantum polynomial time algorithm of Biasse and Song (SODA 16) for computing the $S$-unit group of a number field. This algorithm directly implies polynomial time methods to calculate class groups, S-class groups, relative class group and the unit group, ray class groups, solve the principal ideal problem, solve certain norm equations, and decompose ideal classes in the ideal class group. Additionally, combined with a result of Cramer, Ducas, Peikert and Regev (Eurocrypt 2016), the resolution of the principal ideal problem allows one to find short generators of a principal ideal. Likewise, methods due to Cramer, Ducas and Wesolowski (Eurocrypt 2017) use the resolution of the principal ideal problem and the decomposition of ideal classes to find so-called ``mildly short vectors'' in ideal lattices of cyclotomic fields.
• Abstract（参考訳）: 本稿では,Biasse and Song(SODA)の量子多項式時間アルゴリズムの証明について述べる。 16) 数値場の$S$単位群を計算する。 このアルゴリズムは、類群、Sクラス群、相対類群および単位群、レイ類群を計算し、主イデアル問題を解き、あるノルム方程式を解き、イデアル類群でイデアル類を分解する多項式時間法を直接意味する。 さらに、クレーマー、デュカス、ピーカルト、レゼフ(Eurocrypt 2016)の結果と組み合わせて、主イデアル問題の解決により、主イデアルの短い生成元を見つけることができる。 同様に、 Cramer, Ducas and Wesolowski (Eurocrypt 2017) による手法は、主イデアル問題の解法とイデアルクラスの分解を用いて、シクロトミック場のイデアル格子においていわゆる 'mildly short vectors'' を見つける。

関連論文リスト

• Upper bounding the quantum space complexity for computing class group and principal ideal problem [0.0]
  Biasse と Song が提唱した量子アルゴリズムの量子空間複雑性の上限を計算する。 私たちはBarbulescuとPoulalionのアプローチと、De Boer、Ducas、Fehrのフレームワークに従います。
  論文  参考訳（メタデータ） (2024-05-21T05:37:04Z)
• 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)
• Embedding Integer Lattices as Ideals into Polynomial Rings [29.240943119083678]
  さらに、イデアル格子の付加構造を研究し、その係数を埋め込むことで、与えられたイデアル格子をイデアルとして無限に多くの異なる環に埋め込むことができる。 Ding と Lindner のアルゴリズムには、ある理想的な格子をそれらのアルゴリズムで特定できない欠陥がある。
  論文  参考訳（メタデータ） (2023-07-24T03:06:49Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• An efficient quantum algorithm for lattice problems achieving subexponential approximation factor [2.3351527694849574]
  整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。 量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。 この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
  論文  参考訳（メタデータ） (2022-01-31T18:58:33Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Generation and frame characteristics of predefined evenly-distributed class centroids for pattern classification [4.129225533930966]
  本稿では高次元空間における正則多面体とn次元超球面上の点の均等分布を利用してPEDCCを数学的に生成する。 実験により、新しいアルゴリズムは反復法よりも高速であるだけでなく、位置の精度も高いことが示された。
  論文  参考訳（メタデータ） (2021-05-02T06:35:51Z)
• Certifying clusters from sum-of-norms clustering [13.747619681451875]
  本稿では,近似解から正しいクラスタ割り当てを同定し,証明するクラスタリングテストを提案する。 提案手法では, クラスタ割り当てが, 十分に多くの繰り返しを経て, 原始二重経路追従アルゴリズムによって保証されることが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-06-19T20:26:26Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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