Paper 2021/527

Solving discrete logarithm problem over prime fields using quantum annealing and $\frac{n^3}{2}$ logical qubits

Michał Wroński

Abstract

Shor's quantum algorithm for integer factorization and discrete logarithm is one of the fundamental approaches in modern cryptology. The application of Shor's algorithm requires a general-purpose quantum computer. On the other hand, there are known methods of transformation of factorization problem to the QUBO problem and then solving it using quantum annealing computing with approximately $\frac{n^2}{4}$ logical qubits, for example, using D-Wave computer. It is believed that this approach also may be helpful, primarily until large general-purpose quantum computers will exist. Until now algorithm of similar efficiency for computing discrete logarithm over prime fields was unknown. In this paper, we present a method of reducing discrete logarithm problem to the QUBO problem, which requires approximately $\frac{n^3}{2}$ logical qubits. We also show how to apply quantum annealing to compute discrete logarithm modulo composite numbers, where a quantum annealing factorization algorithm may be used to reduce discrete logarithm modulo composite to several discrete logarithm problems modulo prime number.