Research Proposal for a Quantum Computer Programming ... - Cove

Colorado Technical University
Cove: A Practical Quantum Computer Programming Framework
A Research Proposal Submitted to
The Graduate Council
In Partial Fulfillment of
The Requirements for the Degree of
Doctor of Computer Science
Department of Computer Science By
Matthew D. Purkeypile M.S., Computer Science
B.S., Computer Science
Colorado Springs, CO
February 20, 2008 Cove: A Practical Quantum Computer Programming Framework
By
Matthew D. Purkeypile This Research Proposal is Approved __________________________________________________________
Bo I. Sandén, Ph.D., Professor of Computer Science
__________________________________________________________
Robert W. Johnson, Ph.D., DCS, Professor of Computer Science
__________________________________________________________
James A. Crowder, Ph.D., Sr. Principal System Engineer _______________________________________
Date Approved
Table of Contents 1. Introduction 5
2. Background and Related Work 7
2.1. Quantum Computing 7
2.1.1. Basics of Quantum Mechanics 7
2.1.2. Introduction to Quantum Computing and Quantum Information 18
2.1.3. Foundations of Quantum Computing 21
2.1.4. Limitations of Quantum Computing 23
2.1.5. Limitations of Simulating a Quantum Computer on a Classical
Computer 27
2.1.6. Quantum Algorithms 29
2.2. Quantum Computer Programming 31
2.2.1. Survey of Imperative and Object Oriented Quantum Computer
Programming Languages 31
2.2.2. Brief Overview of Select Other Quantum Programming Language
Paradigms 38
2.3. Framework Design 42
2.4. Summary of Related Work 46
3. Hypothesis and Proof Criteria 46
3.1. Hypothesis 46
3.2. Proof Criteria 50
4. Methodology 51
4.1. Continue Scanning Literature 51
4.2. Setup and Deployment of Infrastructure 52
4.3. Gathering Examples 53
4.4. Development of Quantum Computer Programming Properties 53
4.4.1. Ability to use Remote Resources 54
4.5. Design of Interfaces 55
4.6. Implementation of Interfaces via a Classical Simulation 57
4.7. Proof that Framework Satisfies Functional and Usability
Properties 59
4.8. Analysis of Iteration 59
4.9. Proposed Timeline 60
5. Subset of Research Project: the Qubit 62
5.1. Assumptions 62
5.2. Examples of Qubit Use 63
5.3. Qubit Functional Properties 63
5.3.1. Limitations of Qubits 63
5.3.2. Representation of a Qubit 64
5.3.3. Operations on a Qubit 64
5.3.4. Measurement of a Qubit 65
5.3.5. Accessing a Remote Qubit 66
5.4. Qubit Usability Properties 66
5.5. Framework Design for a Qubit 69
5.6. Implementation of a Qubit in C# 72
5.7. Verification that the Design Satisfies the Properties and Design
Rationale 73
5.7.1. How Common Flaws are Avoided 73
5.7.2. Verification of Functional Properties 74
5.7.3. Verification of Usability Properties 75
5.7.4. Design Rationale 76
5.7.5. Examples 78
5.8. Analysis of Qubit Project 80
5.9. Comparison of Cove to Other Proposals 81
5.10. Summary of Qubit Project 82
6. Conclusion 82
7. Appendix A: Source Code of Cove Base Library in C# 83
8. Appendix B: Source Code of Cove Base Library in Python 89
9. Appendix C: Electronic Resources 95
10. References 97 Introduction
While still years away from being commercially viable, quantum computers
hold the power to carry out computations that are not feasible on current
"classical" computers. Quantum computers are different from the classical
computers we are familiar with in very fundamental ways- in some respects
they represent a new computing paradigm. Like any computer though, quantum
computers are of little value if there is not useful software to run on
them. In order to immediately take advantage of quantum computers when they
arrive, practical techniques to program them must be developed. While the idea of quantum computing first appeared in the 1980's,
programming them did not receive much consideration until the 1990's.
Nonetheless, many of the existing proposals for programming quantum
computers suffer from one or more of the following flaws, making them
impractical or expensive for use in a typical commercial software
development environment:
. Foreign techniques - the proposal utilizes techniques that are foreign
to a majority of commercial developers. This includes the use of
functional languages.
. Not scalable- the proposal only works well for small "snippets" of
code, beyond that it becomes difficult to manage and understand.
Visual languages and languages requiring formal proofs fall under this
category.
. Proprietary language- over 8,500 languages have been developed to date
[1], yet only a very select few see use in the commercial domain.
Languages developed for the purpose of quantum computing are unlikely
to be adopted because they lack the features or power of popular
classical languages that are already in use.
. Difficult to integrate with existing software- it is unlikely that
entire code bases will be rewritten solely to take advantage of
quantum computers. Therefore any method to program quantum computers
must integrate well with existing software.
. General usability/unconventional framework design- languages and
libraries that typically see widespread use are as easy to use as
possible and utilize many common conventions. Application Programming
Interfaces (APIs) and frameworks that do not follow established
conventions are thus difficult to work with and prone to being used
incorrectly.
. Runs only on a quantum computer- it is likely that quantum computers
will initially be a resource that is usable by a classical computer
[2]. Consequently the programming techniques must integrate with
classical computers somehow. These various flaws that existing quantum computer programming proposals
exhibit show that developing quantum programming techniques are far beyond
a trivial task. David Deutsch, one of the fathers of quantum computing,
said in his seminal 1985 paper: "Quantum computers raise interesting
problems for the design of programming languages..." [3]. More than twenty
years later, this is a challenge that has still not been adequately solved.
This paper outlines a proposal for the construction of a quantum computing
framework that does not suffer from the flaws outlined. Frameworks give
programmers the tools to solve certain problems [4], in this case the
problem is how to program quantum computers. Specifically the deliverables
for this research project will consist of the following:
. A list of functional and usability properties that a quantum computing
framework should have. A list of this sort has not yet been
encountered in the literature, making it difficult to determine what a
quantum programming technique needs to accomplish.
. An object oriented design of a framework.
. Proofs and illustrations that show that the proposed framework
satisfies the functional and usability properties.
. An implementation of the framework as a proof of concept, although
this implementation may not necessarily be complete. The core challenge lies not only in developing a method capable of
programming a quantum computer, but in developing a method that is usable
for the common commercial programmer. A majority of software is written by
commercial developers, so if the use of quantum programming is going to be
widespread, then this is the audience that must be targeted. The remainder of the paper is organized as follows:
. Section 2, Background and Related Work- Covers the work related to
quantum programming framework design. This generally falls into three
categories: quantum computing and background (section 2.1), quantum
computer programming (section 2.2), and framework design (section
2.3).
. Section 3, Hypothesis and Proof Criteria- Lays out what the research
proposal aims to accomplish, as well as criteria for judging that it
has been successfully completed.
. Section 4, Methodology- Details the steps that will be followed to
carry out the project. This also includes a proposed timeline.
. Section 5, Subset of Research Project: the Qubit- Details a subset of
the project that has been carried out to show that the project is
viable and to give a concrete example of what the final project will
look like.
. Section 6, Conclusion- Summary of this research proposal.
. Appendix A: Source Code of Cove Base Library in C# - The source code
of the base library, which is interfaces and abstract base classes, is
provided in C#- the primary implementation language.
. Appendix B: Source Code of Cove Base Library in Python - The purpose
of providing the base library in two languages is to help illustrate
that the design is not prohibitively tied to one language.
. Appendix C: Electronic Resources - Describes how various electronic
resources which are outside the scope of this pape