論文の概要: LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling

• arxiv url: http://arxiv.org/abs/2310.00644v2
• Date: Sun, 06 Oct 2024 09:01:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-08 13:40:07.157326
• Title: LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling
• Title（参考訳）: 量子振幅を用いたLWE:アルゴリズム,硬度,および希薄サンプリング
• Authors: Yilei Chen, Zihan Hu, Qipeng Liu, Han Luo, Yaxin Tu,
• Abstract要約: 実ガウス項を持つ $sfS|LWErangle$ および $sfC|LWErangle$ に対する新しいアルゴリズム、硬度結果、およびその他の関連する振幅を示す。
• 参考スコア（独自算出の注目度）: 6.219791262322396
• License:
• Abstract: In this paper, we show new algorithms, hardness results and applications for $\sf{S|LWE\rangle}$ and $\sf{C|LWE\rangle}$ with real Gaussian, Gaussian with linear or quadratic phase terms, and other related amplitudes. Let $n$ be the dimension of LWE samples. Our main results are 1. There is a $2^{\tilde{O}(\sqrt{n})}$-time algorithm for $\sf{S|LWE\rangle}$ with Gaussian amplitude with \emph{known} phase, given $2^{\tilde{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 \emph{known}. 2. There is a polynomial time quantum algorithm for solving $\sf{S|LWE\rangle}$ and $\sf{C|LWE\rangle}$ for Gaussian with quadratic phase amplitudes, where the sample complexity is as small as $\tilde{O}(n)$. As an application, we give a quantum oblivious LWE sampler where the core quantum sampler requires only quasi-linear sample complexity. This improves upon the previous oblivious LWE sampler given by Debris-Alazard, Fallahpour, Stehl\'{e} [STOC 2024], whose core quantum sampler requires $\tilde{O}(nr)$ sample complexity, where $r$ is the standard deviation of the error. 3. There exist polynomial time quantum reductions from standard LWE or worst-case GapSVP to $\sf{S|LWE\rangle}$ with Gaussian amplitude with small \emph{unknown} phase, and arbitrarily many samples. Compared to the first two items, the appearance of the unknown phase term places a barrier in designing efficient quantum algorithm for solving standard LWE via $\sf{S|LWE\rangle}$.
• Abstract（参考訳）: 本稿では,実ガウス,2次位相項を持つガウス,その他の関連する振幅を持つ$\sf{S|LWE\rangle}$および$\sf{C|LWE\rangle}$に対する新しいアルゴリズム,硬度結果,および応用について述べる。 n$ を LWE サンプルの次元とする。 主な結果として、$\sf{S|LWE\rangle}$に対する2.^{\tilde{O}(\sqrt{n})}$-timeアルゴリズムがあり、多くの量子サンプルに対して2.^{\tilde{O}(\sqrt{n})}$が与えられる。 このアルゴリズムはクパーベルグのシーブから修正され、実際に振幅と位相が完全に \emph{known} である限り、より一般的な振幅で機能する。 2. 二次位相振幅を持つガウスに対して$\sf{S|LWE\rangle}$と$\sf{C|LWE\rangle}$を解く多項式時間量子アルゴリズムがあり、サンプルの複雑性は$\tilde{O}(n)$である。 応用として、核となる量子サンプリング器が準線形サンプルの複雑さのみを必要とする量子オブリビングなLWEサンプリング器を与える。 このことは、Debris-Alazard, Fallahpour, Stehl\'{e} [STOC 2024] が与えた以前の暗黙の LWE サンプリングよりも改善され、そのコア量子サンプリングは$\tilde{O}(nr)$サンプル複雑性を必要とし、$r$ はエラーの標準偏差である。 3. 標準の LWE や最悪の GapSVP から $\sf{S|LWE\rangle}$ への多項式時間量子還元があり、小さな \emph{unknown} 位相を持つガウス振幅を持ち、任意に多くのサンプルが存在する。 最初の2つの項目と比較して、未知位相項の出現は、$\sf{S|LWE\rangle}$を介して標準LWEを解くための効率的な量子アルゴリズムを設計する上で障壁となる。

関連論文リスト

• 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)

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

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