論文の概要: Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups
- arxiv url: http://arxiv.org/abs/2508.01231v1
- Date: Sat, 02 Aug 2025 06:58:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-05 18:25:21.77482
- Title: Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups
- Title（参考訳）: 有限アベリア群上のガウワーノルム推定, 多項式検定, 算数化のための量子アルゴリズム
- Authors: En-Jui Kuo,
- Abstract要約: 有限アーベル群上のゴワーズノルム$Uk$を推定するための量子アルゴリズム群を提案する。
これらのアルゴリズムは、ガウワーズノルムに対する最近の逆定理と振幅推定を利用して高次相関を明らかにする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a family of quantum algorithms for estimating Gowers uniformity norms $ U^k $ over finite abelian groups and demonstrate their applications to testing polynomial structure and counting arithmetic progressions. Building on recent work for estimating the $ U^2 $-norm over $ \mathbb{F}_2^n $, we generalize the construction to arbitrary finite fields and abelian groups for higher values of $ k $. Our algorithms prepare quantum states encoding finite differences and apply Fourier sampling to estimate uniformity norms, enabling efficient detection of structural correlations. As a key application, we show that for certain degrees $ d = 4, 5, 6 $ and under appropriate conditions on the underlying field, there exist quasipolynomial-time quantum algorithms that distinguish whether a bounded function $ f(x) $ is a degree-$ d $ phase polynomial or far from any such structure. These algorithms leverage recent inverse theorems for Gowers norms, together with amplitude estimation, to reveal higher-order algebraic correlations. We also develop a quantum method for estimating the number of 3-term arithmetic progressions in Boolean functions $ f : \mathbb{F}_p^n \to \{0,1\} $, based on estimating the $ U^2 $-norm. Though not as query-efficient as Grover-based counting, our approach provides a structure-sensitive alternative aligned with additive combinatorics. Finally, we demonstrate that our techniques remain valid under certain quantum noise models, due to the shift-invariance of Gowers norms. This enables noise-resilient implementations within the NISQ regime and suggests that Gowers-norm-based quantum algorithms may serve as robust primitives for quantum property testing, learning, and pseudorandomness.
- Abstract（参考訳）: 有限アーベル群上のガウワーの一様性ノルムを推定するための量子アルゴリズムのファミリーを提案し、それらの多項式構造のテストや算術的進行の数え上げへの応用を実証する。
U^2 $-norm over $ \mathbb{F}_2^n $ を推定する最近の研究に基づいて、任意の有限体と k のより高い値のアーベル群への構成を一般化する。
我々のアルゴリズムは、有限差分を符号化した量子状態を作成し、一様性ノルムを推定するためにフーリエサンプリングを適用し、構造相関の効率的な検出を可能にする。
重要な応用として、ある次数 $ d = 4, 5, 6 $ および基礎体上の適切な条件下では、有界関数 $ f(x) $ が次数-$ d $ 位相多項式であるか、あるいはそのような構造から遠く離れているかを区別する準ポリリノミカル時間量子アルゴリズムが存在することを示す。
これらのアルゴリズムは、ガウワーズノルムに対する最近の逆定理と振幅推定を利用して高階代数的相関を明らかにする。
ブール関数 $ f : \mathbb{F}_p^n \to \{0,1\} $ の 3 項算術進行数を推定する量子的手法も開発し、U^2 $-norm を推定する。
Grover-based countingほどクエリ効率は良くないが、我々の手法は加法コンビネータと整合した構造に敏感な代替手段を提供する。
最後に、ゴワーズノルムのシフト不変性のため、特定の量子ノイズモデルの下では、我々の手法が有効であることを示す。
これにより、NISQシステム内でのノイズ耐性の実装が可能となり、Gowers-normベースの量子アルゴリズムが量子特性テスト、学習、擬似ランダムネスの堅牢なプリミティブとして機能することを示唆している。
関連論文リスト
- Generalized tensor transforms and their applications in classical and quantum computing [0.0]
一般化変換(GTT)のための新しいフレームワークを導入し、任意の$b倍の単位行列$W$のテンソル積を$n$フォールドで構築する。
量子アプリケーションの場合、GTTベースのアルゴリズムはゲートの複雑さと回路深さが$O(log_b N)$であり、$N = bn$はベクトル入力の長さを表す。
本稿では,量子状態圧縮と伝送,関数符号化,量子ディジタル信号処理など,量子コンピューティングにおけるGTTの多様な応用について検討する。
論文 参考訳（メタデータ） (2025-07-03T08:28:00Z) - Quantum oracles for the finite element method [45.200826131319815]
本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。
本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
論文 参考訳（メタデータ） (2025-04-28T14:28:31Z) - Simulation of Shor algorithm for discrete logarithm problems with comprehensive pairs of modulo p and order q [0.0]
量子回路をシミュレートし、モジュロ$pの一般的なペアで動作させ、$qをオーダーする。
p$ が等しければ、セーフプライム群とシュノール群の強みがどの程度同じかを示す。
特に、加算回路で搬送器を用いる場合、ショアのアルゴリズムの下では$p=$48$ビットのシュノーラー群の暗号強度は$p=$48$ビットの安全プリム群のそれとほぼ同値であることが実験的に理論的に示された。
論文 参考訳（メタデータ） (2025-03-31T10:39:10Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Non-Linear Transformations of Quantum Amplitudes: Exponential
Improvement, Generalization, and Applications [0.0]
量子アルゴリズムは量子状態の振幅を操作して計算問題の解を求める。
量子状態の振幅に非線形関数の一般クラスを適用するための枠組みを提案する。
我々の研究は、最適化、状態準備、量子化学、機械学習といった分野において、潜在的に多くの応用が可能な重要かつ効率的なビルディングブロックを提供する。
論文 参考訳（メタデータ） (2023-09-18T14:57:21Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Infinite quantum signal processing [0.6808803980072229]
量子信号処理(QSP)は、次数$d$の真のスカラーを表す。
QSPは多種多様なポリノミカル関数を表現できることを示す。
解析の結果,対象関数の正則性と因子の減衰特性との間には,驚くべき関連性があることが判明した。
論文 参考訳（メタデータ） (2022-09-21T07:50:26Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Speeding up Learning Quantum States through Group Equivariant
Convolutional Quantum Ans\"atze [13.651587339535961]
我々はSU$(d)$対称性を持つ畳み込み量子回路の枠組みを開発する。
我々は、$nameSU(d)$と$S_n$ irrepbasesの同値性に関するHarrowの主張を証明する。
論文 参考訳（メタデータ） (2021-12-14T18:03:43Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。