Design and implementation of the recursive Bernstein-Vazirani quantum algorithm

Abstract

Der Quantenalgorithmus von Bernstein und Vazirani stellt einen Meilenstein in der Komplexitaetsforschung von Quantencomputern dar. Es konnte gezeigt werden dass Quantencomputer das Bernstein-Vazirani-Problem, auch bekannt als diskretes Fourier Sampling, schneller lösen können, als es mit klassischen Rechnern moeglich ist. In der nicht-rekursiven Basisvariante konnte eine lineare Verbesserung durch Quantencomputer gegenueber klassischen Algorithmen beschrieben werden. Darüber hinaus konnte mittels Rekursion eine superpolynomielle Verbesserung gezeigt werden, die Quantenalgorithmen eine maechtigere Komplexitaetsklasse als klassischer Programmierung zuordnet. Die rekursive Variante des Bernstein-Vazirani-Problems wird in dieser Arbeit neu formuliert und nach Problemgröße und Rekursionstiefe parametrisiert. Danach wird der Algorithmus sowohl in der stark typisierten Quantenprogrammiersprache Silq als auch in Qiskit, einer zeitgemäßen Bibliothek zur Quantenprogrammierung, implementiert. DasProgramm kann in maschinenlesbarer Form für einen Quantencomputer exportiert oder auf klassischen Rechnern emuliert werden. Damit können die Ergebnisse von Bernstein und Vazirani bezueglich der Komplexitaet prinzipiell auch auf Quantencomputern ueberprueft werden. In dieser Arbeit wird ein neuer Ansatz praesentiert, das rekursive Bernstein-Vazirani-Problem mit einem Kontrollargument zu formulieren. Mit dieser Formulierung wird die Implementierbarkeit des Algorithmus wesentlich verbessert.

The Bernstein–Vazirani quantum algorithm serves as an important milestone in the assessment of the computational power of quantum computers. Bernstein and Vazirani showed that the Bernstein–Vazirani problem, alias discrete Fourier sampling, could be solved faster by a quantum algorithm than by any classical formulation. While the non-recursive, base variant shows a linear improvement of the quantum algorithm over classical ones, a superpolynomial improvement could be achieved by applying recursion to the problem. This recursive Bernstein–Vazirani problem separates the complexity classes of quantum and classical computation. The recursive variation of theBernstein–Vazirani problem is reformulated and parametrised by problem size and recursion depth. It is then designed in the strongly typed quantum programming language Silq and also implemented in the state-of-the-art quantum library Qiskit. This program can be exported into machine-readable quantum assembly suitable for a quantum computeror emulated on classical computers. Using these results, the complexity results of Bernstein and Vazirani can in principle be verified on quantum hardware. We present a new variant of formulating the recursive problem using a control argument that greatly simplifies actual implementations.