論文の概要: Quantum Advantage via Solving Multivariate Quadratics

• arxiv url: http://arxiv.org/abs/2411.14697v2
• Date: Wed, 27 Nov 2024 22:29:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-02 15:16:55.144429
• Title: Quantum Advantage via Solving Multivariate Quadratics
• Title（参考訳）: 多変量四元数解法による量子アドバンテージ
• Authors: Pierre Briaud, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai,
• Abstract要約: p_i(x_n)=y_i_iin [m]$ over $mathbbF$。 解は高い確率で存在するが、古典的暗号解析に基づく解を見つけることは困難である。
• 参考スコア（独自算出の注目度）: 12.62849227946452
• License:
• 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) multivariate quadratic equations over the finite field $\mathbb{F}_2$ drawn from a specified distribution. In particular, we design a distribution of degree-2 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 quantum polynomial-time algorithm that 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 a solution exists with high probability, we conjecture that it is classically hard to find one based on classical cryptanalysis that we provide, including a comprehensive review of all known relevant classical algorithms for solving multivariate quadratics. Our approach proceeds by examining the Yamakawa-Zhandry (FOCS 2022) quantum advantage scheme and replacing the role of the random oracle with our multivariate quadratic equations. Our work therefore gives several new perspectives: First, our algorithm gives a counterexample to the conventional belief that generic classically hard multivariate quadratic systems are also quantumly hard. Second, based on cryptanalytic evidence, our work gives an explicit simple replacement for the random oracle from the work of Yamakawa and Zhandry. We show how to instantiate the random oracle with families of just degree two multivariate polynomials over $\mathbb{F}_2$.
• Abstract（参考訳）: 本研究では,与えられた分布から引き出される有限体$\mathbb{F}_2$上の(決定的でない)多変量二次方程式系に対する解を求める平均ケース$\mathsf{NP}$探索問題を解くことによって,量子アドバンテージを(非対話的に,検証的に)証明する新しい方法を提案する。 特に、次数 2 の多項式の分布 $\{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]}$ をランダムなベクトル $(y_1,\ldots,y_m)$ に対して解く量子多項式時間アルゴリズムが存在することを示す。 一方、解は高い確率で存在するが、古典的な暗号解析に基づく解を見つけることは古典的に難しいと推測する。 提案手法は, 山川-Zhandry (FOCS 2022) 量子アドバンストスキームを検証し, ランダムオラクルの役割を多変量二次方程式に置き換えることによって進行する。 第一に、我々のアルゴリズムは、一般的な古典的にハードな多変量二次系も量子的に難しいという従来の信念に反例を与える。 第二に、暗号解析の証拠に基づいて、我々の研究は、山川とZhandryの業績からランダムなオラクルを明示的に置き換えるものである。 ランダムなオラクルを、$\mathbb{F}_2$ 上のちょうど次数 2 個の多変数多項式の族でインスタンスする方法を示す。

関連論文リスト

• Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
  古典的なオラクルを構築し、$mathsfP = MathsfNP$, but quantum-computable quantum-secure trapdoor one-way function が存在する。 この結果から,複数コピーの擬似乱数状態と擬似乱数ユニタリー,古典通信の公開鍵暗号,シグネチャ,暗黙の転送方式が示唆された。
  論文  参考訳（メタデータ） (2024-11-04T19:40:01Z)
• 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)
• Efficient Unitary T-designs from Random Sums [0.6640968473398456]
  Unitary $T$-Designsは、量子アルゴリズム、ベンチマーク、トモグラフィ、通信における様々な応用において、量子情報において重要な役割を果たす。 我々は、$tildeO(T2 n2)$量子ゲートを用いたランダム行列理論による$T$-designsの新たな構成を提供する。
  論文  参考訳（メタデータ） (2024-02-14T17:32:30Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Quadratic Speed-up in Infinite Variance Quantum Monte Carlo [1.2891210250935148]
  我々はモンタナロのarXiv/archive:1504.06987量子モンテカルロ法の拡張を与える。 無限分散を示す確率変数の期待値を計算するために調整されている。
  論文  参考訳（メタデータ） (2024-01-15T06:31:36Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• The complexity of solving a random polynomial system [3.420117005350141]
  本稿では,多変量系の解法に用いる一般アルゴリズムの概要について述べる。 次に、ランダムなシステム、特に"ランダム"が私たちにとって何を意味するかについて話します。 このようなランダムシステムの正則度と解度の両方に上限を与える。
  論文  参考訳（メタデータ） (2023-09-07T17:14:59Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
  量子アルゴリズムの設計と回路下界の一般接続を確立する。 我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
  論文  参考訳（メタデータ） (2020-12-03T14:03:20Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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