LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling

• URL: http://arxiv.org/abs/2310.00644v2
• Date: Sun, 06 Oct 2024 09:01:44 GMT
• Title: LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling
• Authors: Yilei Chen, Zihan Hu, Qipeng Liu, Han Luo, Yaxin Tu,
• Abstract summary: We show new algorithms, hardness results and applications for $sfS|LWErangle$ and $sfC|LWErangle$ with real Gaussian, Gaussian with linear or quadratic phase terms, and other related amplitudes.
• Score: 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}$.

Related papers

• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
  arXiv  Detail & Related papers  (2024-08-10T04:26:19Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
  arXiv  Detail & Related papers  (2023-07-13T18:59:28Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants. We exploit quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
  arXiv  Detail & Related papers  (2022-10-12T19:10:43Z)
• Optimal algorithms for learning quantum phase states [8.736370689844682]
  We show that the sample complexity of learning an unknown degree-$d$ phase state is $Theta(nd)$ if we allow separable measurements. We also consider learning phase states when $f$ has sparsity-$s$, degree-$d$ in its $mathbbF$ representation.
  arXiv  Detail & Related papers  (2022-08-16T17:15:06Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
  arXiv  Detail & Related papers  (2021-12-15T21:44:05Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions [0.0]
  We show that $1D$ random quantum circuits have a spectral gap scaling as $Omega(n-1)$, provided that $t$ is small compared to the local dimension: $t2leq O(q)$. Our second result is an unconditional spectral gap bounded below by $Omega(n-1log-1(n) t-alpha(q))$ for random quantum circuits with all-to-all interactions.
  arXiv  Detail & Related papers  (2020-12-09T19:00:50Z)
• Multi-reference alignment in high dimensions: sample complexity and phase transition [31.841289319809814]
  Multi-reference alignment entails estimating a signal in $mathbbRL$ from its circularly-shifted and noisy copies. Motivated by single-particle cryo-electron microscopy, we analyze the sample complexity of the problem in the high-dimensional regime. Our analysis uncovers a phase transition phenomenon governed by the parameter $alpha = L/(sigma2log L)$, where $sigma2$ is the variance of the noise.
  arXiv  Detail & Related papers  (2020-07-22T15:04:47Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.