Analysis of learning with errors problems with variational quantum algorithms

¹ Beijing Academy of Quantum Information Sciences - Beijing 100193, China
² State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University Beijing 100084, China
³ Frontier Science Center for Quantum Information - Beijing 100084, China
⁴ Beijing National Research Center for Information Science and Technology - Beijing 100084, China

Received: 28 November 2024
Accepted: 15 May 2025

Abstract

Variational Quantum Algorithms (VQAs) offer a promising approach to solving optimization problems on quantum computers. In this paper, we investigate the use of VQAs to solve the Learning With Errors (LWE) problem, a crucial challenge in post-quantum cryptography. We propose a VQA-based algorithm and a Quantum Approximate Optimization Algorithm (QAOA) for solving the Learning Parity with Noise (LPN) problem, a special case of LWE. We examine the sample complexity of combinatorial optimization methods for LPN and analyze the performance of these two variational quantum algorithms in terms of quantum resources. For the VQA algorithm, both the number of qubits and the circuit depth scale polynomially with the secret key length n. In the case of QAOA, the number of qubits matches the secret key length n, but the CNOT gate count increases exponentially with n. However, numerical simulations of the VQA-based algorithm show that choosing optimal ansatzes and optimization methods can significantly enhance success rates.