論文の概要: Exact quantum splitting and the structure of finite algebras
- arxiv url: http://arxiv.org/abs/2608.30340v1
- Date: Mon, 31 Aug 2026 06:56:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:31.272972
- Title: Exact quantum splitting and the structure of finite algebras
- Title（参考訳）: 厳密な量子分割と有限代数の構造
- Abstract要約: ベルカンプのアルゴリズムは、決定論的線型代数により、平方自由の$finmathbbF_q[x]$を分解する。
我々は、効率よく計算可能な角度で1量子ビットの回転を許す回路モデルに、無条件の正確な量子的実装を与える。
- 参考スコア（独自算出の注目度）: 1.7277199466514768
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Berlekamp's algorithm factors a squarefree polynomial $f\in\mathbb{F}_q[x]$ by deterministic linear algebra, reducing the problem to splitting an explicit commutative algebra $B\cong\mathbb{F}_q^r$ into its $r$ simple factors. For large odd $q$, the standard efficient splitting step is randomized, while known derandomizations are conditional on the Extended Riemann Hypothesis. We give an unconditional exact quantum implementation in a circuit model permitting single-qubit rotations through efficiently computable angles. The construction uses an unconditional counting argument. For a block containing $s\ge2$ irreducible factors, a quadratic-character test in odd characteristic and an absolute-trace test in characteristic $2$ yield a nonconstant test element with probability $p_{q,s}\ge\tfrac12$, known exactly in advance and depending only on $q$ and $s$, not on the unknown factorization. Exact amplitude amplification therefore converts each randomized test into a procedure succeeding with certainty after one amplification iteration. The resulting algorithm uses exactly $r-1$ quantum splitting rounds and $O(n^3\log q)$ quantum $\mathbb{F}_q$-operations and $O(n^3)$ classical operations, requiring no primitive root, quadratic non-residue, or distinct-degree preprocessing. The method also splits arbitrary finite-dimensional separable commutative $\\mathbb{F}_q$-algebras given by structure constants. Combined with R'onyai's classical structure theory, which computes the radical deterministically and reduces the remaining tasks deterministically to polynomial factorization, it yields the radical and the Wedderburn decomposition of $A/\mathrm{Rad}(A)$ into minimal two-sided ideals, with certainty, for any $n$-dimensional associative $\mathbb{F}_q$-algebra given by structure constants, using $O(n^4\log q)$ quantum $\mathbb{F}_q$-operations.
- Abstract（参考訳）: ベルカンプのアルゴリズムは、決定論的線型代数により平方自由多項式 $f\in\mathbb{F}_q[x]$ を分解し、明示的可換代数 $B\cong\mathbb{F}_q^r$ を $r$ 単純因子に分解する問題を減らす。
大きな奇数$q$の場合、標準的な効率的な分割ステップはランダム化され、既知のデランドミゼーションは拡張リーマン仮説の条件付きである。
我々は、効率よく計算可能な角度で1量子ビットの回転を許す回路モデルに、無条件の正確な量子的実装を与える。
構成は無条件カウント引数を使用する。
$s\ge2$ 既約因子を含むブロックに対して、奇標数の二次文字検定と標数の絶対トレース検定は、確率 $p_{q,s}\ge\tfrac12$ の非定常検定要素を、正確には予め知られており、未知の因子化に依存しない$q$ と $s$ にのみ依存する。
したがって、振幅増幅は、各ランダム化テストが1回の増幅を繰り返した後、確実に成功する手順に変換する。
得られたアルゴリズムは、正確に$r-1$の量子分割ラウンドと$O(n^3\log q)$の量子$\mathbb{F}_q$演算と$O(n^3)$の古典演算を使い、プリミティブ根、二次的非残差、または別段の事前処理を必要としない。
この方法はまた、任意の有限次元分離可換可換$\\mathbb{F}_q$-代数を構造定数で割る。
根基を決定論的に計算し、残りのタスクを多項式分解に決定的に還元するR'onyaiの古典的構造理論と組み合わさって、$A/\mathrm{Rad}(A)$の根基とウェダーバーン分解を最小二辺イデアルに、任意の$n$次元連想型$\mathbb{F}_q$-algebraに対して$O(n^4\log q)$の量子$\mathbb{F}_q$-operationsに対して確実に生成する。
関連論文リスト
- Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳（メタデータ） (2026-07-08T17:49:40Z) - Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing [0.0]
H_mathrmeff = H_R + iH_I$, where $H_R$ is Hermitian and $H_I succeq 0$。
論文 参考訳（メタデータ） (2026-05-12T17:40:56Z) - Quantum Mechanics from Finite Graded Equality [0.40611352512781856]
我々は、量子力学が一つの仮説から従うことを提案する:等式は有限分解能を持つ。
最初の2つの公理を公理として形式化し、飽和公理内の構造的ライプニッツ条件は基底要素の置換不変量である。
局所トモグラフィーは、テンソル積合成を持つ$mathbbF = mathbbC$から従う。
論文 参考訳（メタデータ） (2026-03-12T13:14:48Z) - Diffusion Computation versus Quantum Computation: A Comparative Model for Order Finding and Factoring [0.0]
本稿では,有限グラフ上の拡散過程にのみアクセス可能な,整数分解のハイブリッド計算モデルについて検討する。
Shor のアルゴリズムとの比較は,概念的およびモデルベースである。
デジタルステップと拡散ステップの2つのコスト尺度で複雑性を報告する。
論文 参考訳（メタデータ） (2026-01-05T19:45:38Z) - Quantum oracles for the finite element method [45.200826131319815]
本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。
本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
論文 参考訳（メタデータ） (2025-04-28T14:28:31Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Average-Case Complexity of Tensor Decomposition for Low-Degree
Polynomials [93.59919600451487]
多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。
1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。
テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
論文 参考訳（メタデータ） (2022-11-10T00:40:37Z) - Infinite quantum signal processing [0.6808803980072229]
量子信号処理(QSP)は、次数$d$の真のスカラーを表す。
QSPは多種多様なポリノミカル関数を表現できることを示す。
解析の結果,対象関数の正則性と因子の減衰特性との間には,驚くべき関連性があることが判明した。
論文 参考訳（メタデータ） (2022-09-21T07:50:26Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。
我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
論文 参考訳（メタデータ） (2021-04-26T15:03:08Z) - Learning sums of powers of low-degree polynomials in the non-degenerate
case [2.6109033135086777]
我々は、ある非退化条件が成立すれば、同じモデルに対する下界から算術回路モデルの学習アルゴリズムを与える。
本アルゴリズムは,同じモデルに対する下界から算術回路モデルの学習アルゴリズムを得るためのスキームに基づいている。
論文 参考訳（メタデータ） (2020-04-15T06:18:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。