Skip to main content
Login | Suomeksi | På svenska | In English

Program Equivalence Checking for Automatic Recognition of Quantum-Compatible Code

Show full item record

Title: Program Equivalence Checking for Automatic Recognition of Quantum-Compatible Code
Author(s): Speer, Jon
Contributor: University of Helsinki, Faculty of Science, none
Discipline: none
Degree program: Master's Programme in Computer Science
Specialisation: Software systems
Language: English
Acceptance year: 2020
Abstract:
The techniques used to program quantum computers are somewhat crude. As quantum computing progresses and becomes mainstream, a more efficient method of programming these devices would be beneficial. We propose a method that applies today’s programming techniques to quantum computing, with program equivalence checking used to discern between code suited for execution on a conventional computer and a quantum computer. This process involves determining a quantum algorithm’s implementation using a programming language. This so-called benchmark implementation can be checked against code written by a programmer, with semantic equivalence between the two implying the programmer’s code should be executed on a quantum computer instead of a conventional computer. Using a novel compiler optimization verification tool named CORK, we test for semantic equivalence between a portion of Shor’s algorithm (representing the benchmark implementation) and various modified versions of this code (representing the arbitrary code written by a programmer). Some of the modified versions are intended to be semantically equivalent to the benchmark while others semantically inequivalent. Our testing shows that CORK is able to correctly determine semantic equivalence or semantic inequivalence in a majority of cases.
Keyword(s): Quantum Computing Program Equivalence Checking Shor’s Algorithm


Files in this item

Files Size Format View
Speer_Jon_thesis_2020.pdf 790.9Kb PDF

This item appears in the following Collection(s)

Show full item record