Using Variational Quantum Algorithm to Solve the LWE Problem.

Area of Science:

• Quantum Computing
• Cryptography
• Algorithm Development

Background:

• The Variational Quantum Algorithm (VQA) is a hybrid approach suitable for noisy intermediate-scale quantum (NISQ) devices.
• The Learning With Errors (LWE) problem is a fundamental challenge in cryptography and quantum computing.
• Current classical methods for LWE are computationally intensive, motivating the exploration of quantum solutions.

Purpose of the Study:

• To propose and evaluate two novel VQA-based methods for solving the LWE problem.
• To demonstrate the potential of VQA in enhancing classical approaches for LWE.
• To assess the feasibility of VQA for LWE on NISQ devices.

Main Methods:

• Reduction of the LWE problem to the Bounded Distance Decoding (BDD) problem, solved using the Quantum Approximate Optimization Algorithm (QAOA).
• Reduction of the LWE problem to the Unique Shortest Vector Problem (uSVP), solved using the Variational Quantum Eigensolver (VQE).
• Detailed calculation of qubit requirements for the VQE-based approach.
• Conducting small-scale experimental validations for both proposed VQA methods.

Main Results:

• Both proposed VQA strategies successfully addressed the LWE problem in small-scale experiments.
• The VQA approach demonstrated an improvement in the quality of solutions compared to purely classical methods.
• The study provides detailed insights into the qubit resource requirements for VQE applied to LWE.

Conclusions:

• Variational Quantum Algorithms offer a promising avenue for tackling the Learning With Errors problem on NISQ hardware.
• The integration of QAOA and VQE within VQA frameworks can enhance classical LWE solving capabilities.
• VQA represents a viable and effective strategy for advancing cryptographic solutions in the era of intermediate-scale quantum computing.