論文の概要: Quantum Algorithms for Modular Factorials

• arxiv url: http://arxiv.org/abs/2607.29453v1
• Date: Fri, 31 Jul 2026 14:15:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-03 16:35:22.245787
• Title: Quantum Algorithms for Modular Factorials
• Title（参考訳）: モジュラー係数に対する量子アルゴリズム
• Abstract要約: 素数$p$、因子$qmid(p-1)$、整数$0np$を与え、期待時間で$n!bmod p$を計算する。 条件 $qmid(p-1)$ は、固有の障害ではなく、現在の方法の技術的な制限であると推測する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a bounded-error quantum algorithm that, given a prime $p$, a divisor $q\mid(p-1)$, and an integer $0<n<p$, computes $n!\bmod p$ in expected time $\widetilde{O}(q^c+\sqrt{p/q})$ for some absolute constant $c\ge 1$. When $p-1$ has a divisor of size $q\approx p^{1/(2c+1)}$, this gives the exponent $c/(2c+1)<1/2$. To our knowledge, this is the first algorithm to break the exponent $1/2$ barrier for modular factorials under such a divisor promise. The main technical ingredient is a quantum algorithm that reconstructs the relevant Jacobi sum exactly in compact algebraic form, with polynomial dependence on $q$ and $\log p$. We further extend the same asymptotic bound to the computation of $n!\bmod p^2$, uniformly over $0\le n<p^2$. At $n=p-1$, this determines the Wilson quotient $\frac{(p-1)!+1}{p}\pmod p$. We conjecture that the condition $q\mid(p-1)$ is a technical limitation of the present method rather than an inherent obstruction, and that a uniform quantum algorithm exists for all primes.
• Abstract（参考訳）: 素数$p$,因子$q\mid(p-1)$,整数$0<n<p$,計算値$n! a bmod p$ in expected time $\widetilde{O}(q^c+\sqrt{p/q})$ for some absolute constant $c\ge 1$。 p-1$ がサイズ $q\approx p^{1/(2c+1)}$ を持つとき、指数 $c/(2c+1)<1/2$ となる。 我々の知る限り、このアルゴリズムはモジュラー因子の指数1/2$バリアをそのような公約の下で破る最初のアルゴリズムである。 主な技術的要素は、関連するヤコビ和をコンパクト代数形式で正確に再構成する量子アルゴリズムであり、多項式依存は$q$と$\log p$である。 さらに、同じ漸近的境界を$nの計算に拡張します! bmod p^2$, uniformly over $0\le n<p^2$. n=p-1$ とすると、ウィルソン商 $\frac{(p-1)! +1}{p}\pmod p$。 我々は、条件$q\mid(p-1)$は固有の障害ではなく、現在の手法の技術的な制限であり、全ての素数に対して一様量子アルゴリズムが存在すると推測する。

関連論文リスト

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。 我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
  論文  参考訳（メタデータ） (2026-09-09T10:13:43Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• A Fast Multiplication Algorithm and RLWE-PLWE Equivalence for the Maximal Real Subfield of the $2^r p^s$-th Cyclotomic Field [0.0]
  導体$n = 2r ps$ でシクロトミック場の最大実部分体に対する RLWE-PLWE 同値性を証明する。 また、これらの実部分体の整数環における高速乗法アルゴリズムについても述べる。
  論文  参考訳（メタデータ） (2025-04-07T15:01:48Z)
• Decomposition of RSA modulus applying even order elliptic curves [0.0]
  効率的な整数分解アルゴリズムはRSA暗号スキームのすべての変種をゼロにする。 滑らか性に対する一般化されたアプローチの自然な拡張と2ドル進点順序の分離が組み合わさって、ファクタリングアルゴリズムを提案することを実証する。
  論文  参考訳（メタデータ） (2025-03-02T16:09:07Z)
• Some new infinite families of non-$p$-rational real quadratic fields [0.0]
  同時に、$p_j$-有理実体の無限族を構成するための単純な方法論を与え、$p_j$の任意の上を無理化する。 これらの技法の1つの特徴は、素体$K=mathbbQ(sqrtD)$を、極大アーベル群のガロア群のトーション群の$p$パワー巡回成分である$p$を超える非有理な外部素数の$K$が$paであるような体を与えるのに使用できることである。
  論文  参考訳（メタデータ） (2024-06-20T18:00:51Z)
• Computing $\varphi(N)$ for an RSA module with a single quantum query [0.0]
  RSAモジュールの$N$に対して$varphi(N)$を、ランダムに選択された整数の代入として$N$を演算する計算時間アルゴリズムを与える。
  論文  参考訳（メタデータ） (2024-06-06T13:30:18Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。 本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-28T18:12:54Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
  論文  参考訳（メタデータ） (2023-02-20T19:11:44Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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