A reference implementation for the extended version of Simon's problem

Abstract

Simons Problem und Simons Algorithmus sind fundamentale Ergebnisse aus dem Bereich Quantum Computing. Im Jahr 1997 publizierten Brassard und Høyer eine Erweiterung der Arbeit von Simon, welche als die erweiterte Version von Simons Problem und Algorithmus bekannt ist, und welche schließlich zur Entwicklung zusätzlicher wichtiger Konzepte wie dem Problem der verborgenen Untergruppe und dem Amplitudenverstärkungsverfahren führte. Trotz ihres Einflusses existierte die Arbeit von Brassard und Høyer bis jetzt nur auf dem Papier und es gab keine Referenzimplementierung für den erweiterten Algorithmus von Simon. Im Zuge dieser Diplomarbeit führen wir zunächst eine detaillierte mathematische Analyse der Arbeit Brassard- und Høyers durch. Weiters stellen wir eine neuartige Prozedur vor, mit welcher automatisch Testinstanzen für die erweiterte Version von Simons Problem generiert werden können. Bei diesen Testinstanzen handelt es sich um Quantenprogramme, welche gemeinhin Orakel genannt werden. Unsere Orakel sind auf real existierenden Quantencomputern lauffähig. Darüber hinaus präsentieren wir die erste Referenzimplementierung der erweiterten Version von Simons Algorithmus, welche ebenfalls auf echten Quantencomputern lauffähig ist. Abschließend evaluieren wir unsere Implementierung auf einem störungsfreien Quantencomputersimulator, auf mehreren störungsbehafteten Simulatoren echter Geräte und auf einem real existierenden Quantencomputer selbst. Unsere Erkenntnisse sind, dass sich unsere Implementierung sowohl auf dem störungsfreien- als auch auf den störungsbehafteten Simulatoren verhält wie erwartet. Die Ergebnisse auf dem echten Quantencomputer legen jedoch nahe, dass die momentan verfügbare Quantenhardware nicht ausgereift genug ist,um selbst kleinste Instanzen der erweiterten Version von Simons Problem zu lösen.

Simon’s problem and Simon’s algorithm are seminal results in quantum computing. In 1997, Brassard and Høyer published an extension to the work of Simon known as the extended version of Simon’s problem and algorithm, which itself laid the foundations for further important concepts like the hidden subgroup problem framework and the amplitude amplification quantum algorithm paradigm. Despite this, the work of Brassard and Høyer so far existed on paper only and lacked a reference implementation. We first provide a detailed mathematical analysis of the work by Brassard and Høyer. Second, we present a novel procedure that automatically generates test instances for the extended version of Simon’s problem. Those test instances are quantum programs commonly called oracles, and our oracles are runnable on actual quantum hardware. Third, we provide the first reference implementation for the extended version of Simon’s algorithm itself, which is runnable on actual quantum hardware as well. Last, we tested our implementation on a noise-free quantum computer simulator, on noisy simulators for actual quantum processors and on a real quantum device. Our findings are that the extended version of Simon’s algorithm works as expected both on the noise-free and the noisy simulators. The results from the real quantum computer however hint that current-generation devices are still not mature enough to solve even small toy instances of the extended version of Simon’s problem.