On quantum learning algorithms for noisy linear problems

arXiv:2404.03932v1 Announce Type: cross
Abstract: Quantum algorithms have shown successful results in solving noisy linear problems with quantum samples in which cryptographic hard problems are relevant. In this paper the previous results are investigated in detail, leading to new quantum and classical algorithms under the same assumptions as in the earlier works. To be specific, we present a polynomial-time quantum algorithm for solving the ring learning with errors problem with quantum samples which was deemed to be infeasible in [12], …

algorithms arxiv cryptographic cs.cr hard linear noisy problems quant-ph quantum quantum algorithms relevant results under