Tangible Quantum Speedup in Learning-With-Errors Problem
Wooyeong Song, Youngrong Lim, Kabgyun Jeong, Yun-Seong Ji, Jinhyoung Lee, Jaewan Kim, Jeongho Bang · arXiv (Cornell University) · 2019
Very recently, one of the most biggest agenda issues is to provide the proof of quantum computational speedup, particularly with a prospect for near-term uses. However, many quantum algorithms are beyond the reach of noisy intermediate-scale quantum (NISQ) realization. This is mainly because of the requirement of excessively large superposition and massive quantum circuit. Hence, we propose a (say) ``NISQ-compatible'' algorithm for one of the crucial problems in computation and modern cryptography, the learning-with-errors (LWE) problem. We base an approach on the divide-and-conquer, wherein a large core process is subdivided into smaller subprocesses. For a specific error distribution and problem condition, it is shown that the proposed quantum LWE algorithm allows the use of exponentially less-superposed quantum samples and operation overheads are reduced, while achieving polynomial sample complexity.