論文の概要: On the Hardness of $\sf{S|LWE\rangle}$ with Gaussian and Other Amplitudes

• arxiv url: http://arxiv.org/abs/2310.00644v1
• Date: Sun, 1 Oct 2023 11:53:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-05 02:48:34.824569
• Title: On the Hardness of $\sf{S|LWE\rangle}$ with Gaussian and Other Amplitudes
• Title（参考訳）: ガウスおよびその他の振幅を持つ$\sf{S|LWE\rangle}$の硬さについて
• Authors: Yilei Chen, Zihan Hu, Qipeng Liu, Han Luo and Yaxin Tu
• Abstract要約: ガウスおよびその他の振幅を持つ$sfS|LWErangle$に対する新しい硬さとアルゴリズムを示す。 我々の結果を解釈する1つの方法は、標準LWEのサブ指数時間量子アルゴリズムを示すために、$sfS|LWErangle$振幅の位相を扱うことだけが必要である。
• 参考スコア（独自算出の注目度）: 6.672877891213174
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The learning with errors problem (LWE) is one of the most important building blocks for post-quantum cryptography. To better understand the quantum hardness of LWE, it is crucial to explore quantum variants of LWE, show quantum algorithms for those variants, or prove they are as hard as standard LWE. To this end, Chen, Liu, and Zhandry [Eurocrypt 2022] define the $\sf{S|LWE\rangle}$ problem, which encodes the error of LWE samples into quantum amplitudes. They then show efficient quantum algorithms for $\sf{S|LWE\rangle}$ with a few interesting amplitudes. However, the hardness of the most interesting amplitude, Gaussian, was not addressed by Chen et al., or only known for some restricted settings (for example, when the number of $\sf{S|LWE\rangle}$ samples is very small, it is well known that $\sf{S|LWE\rangle}$ is as hard as standard LWE). In this paper, we show new hardness and algorithms for $\sf{S|LWE\rangle}$ with Gaussian and other amplitudes. Our main results are 1. There exist quantum reductions from standard LWE or worst-case GapSVP to $\sf{S|LWE\rangle}$ with Gaussian amplitude with unknown phase, and arbitrarily many $\sf{S|LWE\rangle}$ samples. 2. There is a $2^{\widetilde{O}(\sqrt{n})}$-time algorithm for $\sf{S|LWE\rangle}$ with Gaussian amplitude with known phase, given $2^{\widetilde{O}(\sqrt{n})}$ many quantum samples. The algorithm is modified from Kuperberg's sieve, and in fact works for more general amplitudes as long as the amplitudes and phases are completely known. One way of interpreting our result is: to show a sub-exponential time quantum algorithm for standard LWE, all we need is to handle phases in $\sf{S|LWE\rangle}$ amplitudes better, either in the algorithm or the reduction.
• Abstract（参考訳）: LWE(Learning with error problem)は、量子後暗号における最も重要なビルディングブロックの1つである。 LWEの量子硬度をよりよく理解するためには、LWEの量子変種を探索し、それらの変種に対する量子アルゴリズムを示し、標準LWEと同じくらい難しいことを証明することが重要である。 この目的のために、Chen, Liu, and Zhandry [Eurocrypt 2022] は$\sf{S|LWE\rangle}$問題を定義し、LWEサンプルの誤差を量子振幅にエンコードする。 そして、いくつかの興味深い振幅を持つ$\sf{s|lwe\rangle}$の効率的な量子アルゴリズムを示す。 しかし、最も興味深い振幅の硬さは、Chenらによって解決されなかったり、制限された設定でのみ知られている(例えば、$\sf{S|LWE\rangle}$サンプルの数が非常に小さい場合、$\sf{S|LWE\rangle}$が標準LWEと同じくらい硬いことが知られている)。 本稿では,ガウスおよび他の振幅を持つ$\sf{S|LWE\rangle}$に対する新しい硬さとアルゴリズムを示す。 主な結果は、標準LWEまたは最悪のGapSVPから未知位相を持つガウス振幅を持つ$\sf{S|LWE\rangle}$への量子還元が存在し、任意の数の$\sf{S|LWE\rangle}$サンプルが存在する。 2. 既知の位相を持つガウス振幅を持つ$\sf{s|lwe\rangle}$に対する2^{\widetilde{o}(\sqrt{n})}$-timeアルゴリズムがあり、2^{\widetilde{o}(\sqrt{n})}$多くの量子サンプルが与えられる。 このアルゴリズムはクパーベルクのシーブから修正され、振幅と位相が完全に知られている限り、より一般的な振幅で機能する。 我々の結果を解釈する1つの方法は、標準LWEのサブ指数時間量子アルゴリズムを示すためには、$\sf{S|LWE\rangle}$の振幅の位相をアルゴリズムまたは還元のいずれにおいてもより良く扱う必要がある。

関連論文リスト

• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)
• Optimal algorithms for learning quantum phase states [8.736370689844682]
  未知の次数$d$相状態を学ぶ際のサンプルの複雑さは、分離可能な測定を許せば$Theta(nd)$であることを示す。 また、f$がsparsity-$s$, degree-$d$を持つ場合の学習フェーズ状態も検討する。
  論文  参考訳（メタデータ） (2022-08-16T17:15:06Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。 我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
  論文  参考訳（メタデータ） (2021-12-15T21:44:05Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions [0.0]
  我々は、$D$のランダム量子回路がスペクトルギャップスケーリングを$Omega(n-1)$とすることを示し、$t$が局所次元と比較して小さいことを仮定する:$t2leq O(q)$。 2つ目の結果は、全ての相互作用を持つランダム量子回路に対して、以下に$Omega(n-1log-1(n) t-alpha(q))$で有界な非条件スペクトルギャップである。
  論文  参考訳（メタデータ） (2020-12-09T19:00:50Z)
• Multi-reference alignment in high dimensions: sample complexity and phase transition [31.841289319809814]
  マルチ参照アライメントは、円形にシフトしたノイズの多いコピーから$mathbbRL$のシグナルを推定する。 単一粒子の低温電子顕微鏡により、高次元状態における問題のサンプルの複雑さを解析した。 我々の分析では、パラメータ $alpha = L/(sigma2log L)$ で制御される相転移現象を発見し、$sigma2$ はノイズの分散である。
  論文  参考訳（メタデータ） (2020-07-22T15:04:47Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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