論文の概要: Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields

• arxiv url: http://arxiv.org/abs/2608.23929v1
• Date: Tue, 25 Aug 2026 00:23:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-26 14:09:34.669292
• Title: Quantum Algorithms and Hardness for Point-Count Approximation over Finite Fields
• Title（参考訳）: 有限場上の点列近似のための量子アルゴリズムと硬さ
• Abstract要約: 有限体上のローレントルムの解数の近似について検討する。 我々の最初の主要な結果は、成功確率1-$で、$widehat(f)$ fulfilling [ |widehatN(f) - N(f)| le varepsilon qn+s/2-]を出力する量子アルゴリズムである。 2つ目の主要な結果として、ランダム時間チューリング還元の下で同じ問題が$#$P-hardになることを示す。
• 参考スコア（独自算出の注目度）: 1.4323566945483497
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the approximation of the number of solutions of Laurent polynomials over finite fields. For a Laurent polynomial \[f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1},\ldots,x_n^{\pm1}], \] let $U$ be its augmented support matrix whose columns are $(1,u_j)$ with rank $ρ$ and $N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\}$ be its torus point count. Our first main result is a quantum algorithm that outputs $\widehat{N}(f)$ satisfying \[ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} \] with success probability $1-δ$. Provided that $ρ$ and $\|U\|_\infty$ are bounded, the algorithm runs in both classical bit and quantum gate complexity $\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))$. It provides finer resolution than relative-error approximations in general settings. To the best of our knowledge, in the explicit finite-field input model considered here, no previous algorithm achieves this additive accuracy with running time polynomial in $\log q$. Van Dam (arXiv:quant-ph/0405081) conjectured the existence of such an algorithm under the assumption of an oracle reflecting the algebraic properties of the polynomial. In contrast, by exploiting a point-counting formula derived from character sums over finite fields, we develop an alternative approach that efficiently approximates the number of points without assuming the existence of such an oracle. As a second main result, we prove that the same approximation problem becomes $\#$P-hard under randomized polynomial-time Turing reductions when the support matrix $U$ varies freely as part of the input. Thus, taken together, our results clarify how the effectiveness of the quantum approach depends on the tradeoff between the accuracy scale and the support parameters of the input polynomial.
• Abstract（参考訳）: 有限体上のローラン多項式の解数の近似について検討する。 ローラン多項式 \[f(x)=\sum_{j=1}^{s}a_jx^{u_j}\in \mathbb{F}_q[x_1^{\pm1}],\ldots,x_n^{\pm1}], \] に対して、$U$ を階数 $ρ$ と $N(f) := \# \{x\in (\mathbb{F}_q^\times)^n \mid f(x)=0\} がトーラス点数である拡張サポート行列とする。 我々の最初の主要な結果は、成功確率が1-δ$の量子アルゴリズムである: $\widehat{N}(f)$ fulfilling \[ |\widehat{N}(f) - N(f)| \le \varepsilon q^{n+s/2-ρ} \]。 ρ$と$\|U\|_\infty$が有界であれば、アルゴリズムは古典的ビットと量子ゲートの複雑さ$\mathrm{poly}(n, s, \log q, 1/\varepsilon, \log(1/δ))$の両方で動作する。 一般的な設定では、相対誤差近似よりも微細な解像度を提供する。 我々の知る限りでは、ここで考慮された明示的な有限場入力モデルでは、以前のアルゴリズムでは、実行時多項式を$\log q$で加算精度を達成できなかった。 ファン・ダム (arXiv:quant-ph/0405081) は多項式の代数的性質を反映するオラクルを仮定してそのようなアルゴリズムの存在を予想した。 対照的に、有限体上の文字和から導出される点数公式を利用して、そのようなオラクルの存在を仮定することなく、効率的に点数を近似する別のアプローチを開発する。 2つ目の主要な結果として、サポート行列$U$が入力の一部として自由に変化するとき、ランダム化多項式時間チューリング還元の下で同じ近似問題が$$#$P-hardとなることを示す。 そこで,本研究では, 量子的手法の有効性が, 精度尺度と入力多項式の支持パラメータとのトレードオフにどのように依存するかを明らかにする。

関連論文リスト

• 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)
• Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms [0.764671395172401]
  完全有界法を用いて量子クエリアルゴリズムのパワーの限界を確立することの問題点を考察する。 我々は、完全有界の異なる概念を含むいくつかの最適機能不等式を証明した。 これらの不等式は、以前の作業を改善する量子クエリアルゴリズムのパワーの制限につながる。
  論文  参考訳（メタデータ） (2026-09-04T14:34:56Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications [13.39372872460586]
  mathbbRn times d$ の行列 $X の 2 つの右幅 q$ノルムは $lVert X rVert_2 rightarrow q = sup_lVert v rVert = 1 lVert Xv rVert_q$ と定義される。 FOCS(Exponential Time hypothesis)を仮定すると、単純なスペクトルアルゴリズムは2sqrtlog n$よりも近似係数がよいことを示す。
  論文  参考訳（メタデータ） (2026-05-24T23:56:06Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Quantum and classical query complexities of functions of matrices [0.0]
  任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
  論文  参考訳（メタデータ） (2023-11-13T00:45:41Z)
• 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)
• 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)
• 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)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)

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

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