(英) |
This paper introduces a quantum-inspired algorithm, called interpolation, that reduces an LWE problem to another problem similar to an LWE problem (called an LWE-like problem in this paper). The interpolation algorithm can change a modulus of an LWE problem, which makes it easier to solve an LWE problem by a quantum (or quantum-inspired) computer. In addition, we propose a quantum-classical hybrid algorithm that solves an LWE problem by using the interpolation algorithm and a quantum annealing machine recursively. The sizes of graphs of maximum independent set (MIS) problems reduced from an LWE problem are calculated. The number of qubits necessary to solve an LWE problem by using a quantum annealing machine is then estimated. For example, a 40-dimensional LWE problem, which is the smallest-dimensional open problem of Darmstadt LWE Challenge, can be reduced to MIS problems of graphs with about several tens of thousands of vertices and small weights. This suggests that open problems of Darmstadt LWE Challenge will be in the scope of the target of quantum annealing machines in the near future.
We implemented the interpolation algorithm and confirmed that the smallest challenge problem (dimension $=40$ and relative error $=0.05$) of Darmstadt LWE Challenge
can be reduced to a graph with about 40,000 vertices. |