Quantum algorithms for the discrete logarithm problem

Abstract

Shor’s Algorithmen für die Primfaktorzerlegung und für das Problem des diskreten Logarithmus zählen zu den bahnbrechendsten Entwicklungen im Bereich der Quanteninformatik. Sie lösen Probleme in polynomieller Zeit mithilfe eines Quantencomputers, für welche keine effizienten klassischen Algorithmen bekannt sind. Diese Tatsache unterstreicht den Nutzen von Quantencomputern im Allgemeinen. Heutzutage existieren Bibliotheken und Simulatoren, die es ermöglichen, Quantenalgorithmen zu implementieren und zu analysieren. Eine dieser Bibliotheken, welche außerdem noch die Möglichkeit bietet, die Algorithmen auf echten Maschinen auszuführen, ist Qiskit. Qiskit beinhaltet zurzeit jedoch keine Referenzimplementierung für Shor’s Algorithmus für den diskreten Logarithmus. Für eine Implementierung müssen zusätzlich zur allgemeinen Beschreibung des Algorithmus noch Prozeduren für modulare Arithmetik bereitgestellt werden. Für diese Berechnungen gibt es viele unterschiedliche Algorithmen, wobei manche sehr klassischen Prozeduren ähneln und andere wiederum die Eigenheiten von Quantencomputern ausnutzen. Diese Arbeit liefert eine Referenzimplementierung von Shor’s Algorithmus für das Problem des diskreten Logarithmus. Dabei werden drei verschiedene Versionen der benötigten Routinen für modulare Arithmetik verwendet. Da aktuelle Quantencomputer immer noch relativ wenige Quantenbits, oder Qubits, für die Berechnung zur Verfügung stellen, liegt der Hauptfokus der Arbeit auf Möglichkeiten der Implementierung, die eine minimale Anzahl an Qubits benötigen. Mithilfe der Simulationsfunktionen von Qiskit wird zusätzlich zum Vergleich der Implementierungen bezüglich der asymptotischen Zeitkomplexität ein Vergleich der verschiedenen Versionen anhand der konkreten Anzahl an elementaren Operationen für kleine Probleminstanzen vorgenommen. Außerdem wird diese Analyse um eine genaue Untersuchung der Erfolgswahrscheinlichkeit ergänzt, da diese für die Laufzeit insgesamt ausschlaggebend ist.

One of the groundbreaking results in the field of quantum computing is Shor’s work describing algorithms for prime factorization and for the discrete logarithm problem. These algorithms solve problems in polynomial time on a quantum computer, for which no efficient solution is known on a classical computer, which highlights the utility of quantum computers. Today there are libraries and simulators available that enable the implementation and analysis of quantum algorithms. One of these development environments is Qiskit, which furthermore enables its users to execute quantum algorithms on real devices. However, this library currently does not contain a reference implementation of Shor’s algorithm for the discrete logarithm problem. For such an implementation, not only the structure of the overall algorithm but also procedures for performing modular arithmetic on a quantum computer have to be provided. There are various ways of performing these calculations. Some are very similar to classical procedures and some utilize the peculiarities of quantum systems. This work provides a reference implementation of Shor’s algorithm for the discrete logarithm problem. This quantum program makes use of three different implementations of the required modular arithmetic procedures. Since current quantum computers are still small in the number of qubits available for computation, this thesis focuses on implementation proposals that optimize the space complexity of the algorithm for the discrete logarithm problem. The presented implementations are compared using their asymptotic complexity bounds. Additionally, using Qiskit’s simulation capabilities, a comparison of the different versions using concrete values for the number of elementary instructions for small problem instances is presented. Furthermore, this analysis is extended to also investigate the actual success probability of the algorithm as this value is crucial for the overall runtime.