Design and Analysis of a Scalable and Efficient Quantum Circuit for LWE Matrix Arithmetic

Quantum computing furnishes exponential speed up over classical computing in specific areas. For example, Shor’s algorithm can factor two numbers in a polynomial time complexity. Thus, many encryption algorithms that rely on large number factorization are potentially vulnerable to quantum computers. In order to address this, the National Institute of Standard and Test (NIST) has organized a competition to evaluate several post quantum cryptography (PQC) algorithms, that are secure from the attacks from quantum computers. Several of these lattice-based PQC encryption algorithms are based on Learning With Errors (LWE) computation. Conversely, LWE is the heaviest computation in a classical computer, which incurs significant portion of the latency overhead for the entire encryption algorithm. In this paper, we design an optimized quantum circuit for LWE computation. The proposed quantum circuit does not need any ancillary qubits and scales efficiently and easily if there are more qubits available on a higher qubit quantum computer.