{"id":"arxiv/2605.20133","url":"https://arxiv.org/abs/2605.20133","tags":["quant-ph"],"score":0,"title":"Quantum algorithm for Discrete Gaussian Sampling","domain":"quant-ph","source":"arxiv","authors":["Clémence Chevignard","Yixin Shen","André Schrottenloher"],"reviews":0,"subject":"quant-ph","summary":"Discrete Gaussian Sampling on lattices is a fundamental problem in lattice-based cryptography. It appears both in basic cryptographic primitives such as digital signatures and as an important cryptanalysis building block for solving hard lattice problems. In this paper, we show a quantum algorithm based on the quantum rejection sampling technique whose complexity is asymptotically quadratically faster than its classical counterpart in [Wang & Ling, IEEE Trans. Inf. Theory 2019]. Our sampler outputs a quantum state which can either be measured to get the desired distribution or be used…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-05-19","reactions":{}}