論文の概要: Quantum Advantage via Solving Multivariate Polynomials
- arxiv url: http://arxiv.org/abs/2509.07276v1
- Date: Mon, 08 Sep 2025 23:19:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-10 14:38:27.141075
- Title: Quantum Advantage via Solving Multivariate Polynomials
- Title（参考訳）: 多変量多項式の解法による量子アドバンテージ
- Authors: Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai,
- Abstract要約: 3次関数はランダムなオラクルをインスタンス化して非相対化量子優位を得るのに十分であることを示す。
p_i(x_ldots,x_n)=y_i_iin [m]$ for $mn$ over $mathbbF$。
- 参考スコア（独自算出の注目度）: 21.099298465042583
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we propose a new way to (non-interactively, verifiably) demonstrate quantum advantage by solving the average-case $\mathsf{NP}$ search problem of finding a solution to a system of (underdetermined) constant degree multivariate equations over the finite field $\mathbb{F}_2$ drawn from a specified distribution. In particular, for any $d \geq 2$, we design a distribution of degree up to $d$ polynomials $\{p_i(x_1,\ldots,x_n)\}_{i\in [m]}$ for $m<n$ over $\mathbb{F}_2$ for which we show that there is a expected polynomial-time quantum algorithm that provably simultaneously solves $\{p_i(x_1,\ldots,x_n)=y_i\}_{i\in [m]}$ for a random vector $(y_1,\ldots,y_m)$. On the other hand, while solutions exist with high probability, we conjecture that for constant $d > 2$, it is classically hard to find one based on a thorough review of existing classical cryptanalysis. Our work thus posits that degree three functions are enough to instantiate the random oracle to obtain non-relativized quantum advantage. Our approach begins with the breakthrough Yamakawa-Zhandry (FOCS 2022) quantum algorithmic framework. In our work, we demonstrate that this quantum algorithmic framework extends to the setting of multivariate polynomial systems. Our key technical contribution is a new analysis on the Fourier spectra of distributions induced by a general family of distributions over $\mathbb{F}_2$ multivariate polynomials -- those that satisfy $2$-wise independence and shift-invariance. This family of distributions includes the distribution of uniform random degree at most $d$ polynomials for any constant $d \geq 2$. Our analysis opens up potentially new directions for quantum cryptanalysis of other multivariate systems.
- Abstract（参考訳）: 本研究では,与えられた分布から引き出された有限体 $\mathbb{F}_2$ 上の定数次数多変量方程式系に対する解を求める平均ケース $\mathsf{NP}$ 探索問題を解くことにより,量子的優位性を(非インタラクティブ,検証可能)証明する新しい方法を提案する。
特に、任意の$d \geq 2$に対して、$d$多項式$\{p_i(x_1,\ldots,x_n)\}_{i\in [m]}$ for $m<n$ over $\mathbb{F}_2$に対して、$\{p_i(x_1,\ldots,x_n)=y_i\}_{i\in [m]}$を確率的に同時に解く多項式時間量子アルゴリズムが存在することを示す。
一方、解は高い確率で存在するが、定数$d > 2$の場合、既存の古典的暗号解析の徹底的なレビューに基づいて解を見つけることは古典的に困難である。
したがって、我々の研究は、3次関数がランダムなオラクルをインスタンス化して非相対化量子優位を得るのに十分であると仮定する。
提案手法は, 高速な量子アルゴリズムフレームワークである山川Zhandry (FOCS 2022) から始まっている。
本研究では,この量子アルゴリズムの枠組みが多変量多項式系の設定にまで拡張されることを実証する。
我々の重要な技術的貢献は、$\mathbb{F}_2$ multivariate polynomial -- 2$の独立性とシフト不変性を満たす分布の一般族によって誘導される分布のフーリエスペクトルに関する新しい分析である。
この分布の族は、任意の定数$d \geq 2$に対して、最大$d$多項式における一様ランダム次数の分布を含む。
我々の分析は、他の多変量系の量子暗号解析の新しい方向性を開く。
関連論文リスト
- Two exact quantum signal processing results [0.0]
量子信号処理(QSP)は、量子回路を介して特定の機能を実装するためのフレームワークである。
QSP 回路を構成するには、ターゲット $P(z)$ が必要であるが、これは複素単位円 $mathbb$ 上で $lvert P(z)rvertleq 1 を満たす必要がある。
論文 参考訳（メタデータ） (2025-05-15T21:13:23Z) - Quantum Advantage via Solving Multivariate Quadratics [12.62849227946452]
p_i(x_n)=y_i_iin [m]$ over $mathbbF$。
解は高い確率で存在するが、古典的暗号解析に基づく解を見つけることは困難である。
論文 参考訳（メタデータ） (2024-11-22T03:10:10Z) - An in-depth study of the power function $x^{q+2}$ over the finite field $\mathbb{F}_{q^2}$: the differential, boomerang, and Walsh spectra, with an application to coding theory [28.489574654566677]
有限体 $mathbbF_q2$ は$q2$ 要素からなる。
まず、いくつかの重要な単純化を取り入れた電力関数 $f(x) = xq+2$ on $mathbbF_q2$ の微分スペクトルを決定する方法を提案する。
論文 参考訳（メタデータ） (2024-07-08T14:01:06Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。
我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
論文 参考訳（メタデータ） (2021-04-26T15:03: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) - Quasi-polynomial time algorithms for free quantum games in bounded
dimension [11.56707165033]
2プレイヤフリーゲームの値に対する加法$epsilon$-approximationsを計算するために、$exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big))という半定値プログラムを与える。
量子分離性問題と接続し、線形制約を伴う改良された多部量子デ・フィネッティ定理を用いる。
論文 参考訳（メタデータ） (2020-05-18T16:55:08Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。