Functional Specification

Colm O hEigeartaigh, 99387212, CASE4. <coheig-case4@computing.dcu.ie>


1. Introduction

1.1 Scope and purpose of document

The scope of this document is to describe the project of porting the Quantum Computing Language to run on a cluster. In the Background section, Quantum Computing is described and its potential benefits are outlined. The background to the problem of simulating quantum algorithms on a parallel surface is also addressed. The Overview of Project section gives a general overview of what this project will entail, as well as listing the objectives and constraints. In the Functional and Data Description section, the System Architecture of the project is comprehensively addressed.

The Subsystem Description section outlines the various subsystems of the project, such as the MPI libraries, the QCL language and the Quantum Fourier Transform. It also outlines the hardware and software resources that will be required. The Projected Schedule section gives a detailed timetable for completing the project. The Appendix section contains references relating to the area of this project, as well as various keywords that are used in this document.


1.2 Background

What is Quantum Computing?

Modern classical computers are fundamentally no different from their ancestors in the 1940s, despite being vastly smaller and speedier. They store and manipulate a unit of information called the bit, which takes either 0 or 1 as its value. A Quantum Computer uses a different fundamental unit of information, called the Qubit. A Qubit has a property called superposition, which enables it to exist in multiple states at the same time. This means it can exist in an infinite number of states between 0 and 1, with each state being assigned a probability, all of which must add up to 1.

If a quantum operation is performed on a qubit in multiple states, then the operation is performed on all states simultaneously. When the qubit is observed, it will collapse back into a single state stochastically, according to the squares of the probabilities. Combined with another quantum property called Entanglement, superposition can be used to dramatically speed up solutions to hard problems.

Quantum Algorithms are difficult to design, because of the difficulty in engineering the quantum system to collapse into the "correct" state when it is observed. Two famous algorithms are the Grover Algorithm, which searches an unsorted database in quadratic time, and the Shor Algorithm, which factors a large prime number in polynomial time. It is the fact that an NP problem such as factoring can be solved in polynomial time on a Quantum Computer, that gives Quantum Computing its promise.


General Number Field Sieve Shor's Algorithm
Θ(exp((64/9)1/3N1/3(lnN)2/3)) O((log N)3)

Fig 1. The promise of Quantum Computing. Running time of fastest known classical factoring algorithm, versus that of Shor's Algorithm.


A Quantum Computer is for now only a dream, due to the engineering difficulties in isolating a quantum state from the outside world. It is likely though that a prototype will be constructed some time in the near future. Shor's algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.


Why parallel?

Simulating a quantum computer on a classical computer is a computationally hard problem. Each state in the quantum system is represented by a matrix. Simulating a system with a large number of qubits on a classical computer means manipulating exponentially large matrices. Therefore, the bigger the quantum system being simulated, the longer it will take to simulate it on a classical computer.

A lot of computational power is needed to simulate a large quantum system. Most serious scientific simulation now occurs on huge clusters of ordinary workstations, rather than supercomputers, due to cost effectiveness and easy maintainability. Simulating a large quantum system on a parallel cluster has never been fully achieved before, to my knowledge.


1.3 Overview of project

Description

The Quantum Computing Language is a programming language designed to approach quantum computing programming, using the syntax of a procedural language like "C". This project will rewrite the source code of the QCL to run over the CA Linux cluster using the MPI parallel library. Quantum Computing simulations can be very time consuming, hence the main objective of this project is to make the code run on parallel machines, thus speeding up the simulations.

This extension to the QCL will be designed separately from the underlying language itself; only the numerical simulation section of the QCL will be parallelised. This project is designed to be applied as a UNIX patch to the QCL, such that the patch can be easily applied to the language if it is to be run over a cluster of workstations.

This project will also look at implementing various quantum algorithms in parallel, such as Shor's factoring algorithm or Grover's search algorithm. Implementing Shor's Algorithm in parallel will require implementing the Quantum Fast Fourier Transform in parallel. Simulating Quantum Cryptography might also be attempted.

This project will also analyse performance issues relating to simulating these algorithms in parallel. Achieving a significant speedup is not a major goal of this project, due to the slow nature of the computing surface. Nevertheless, some speedup is expected when computing large quantum states.

A graphical user interface to the cluster will also be written in Java. The user interface to the Computer Applications Linux cluster is a UNIX terminal, which does not give a graphical representation of what the nodes of the cluster are doing. I have written a java program which runs on a remote desktop, connects into the head node of the cluster and displays the names of all the nodes on the cluster, as well as their status and their load. This program will be further developed, and possibly combined with open-source cluster/mpi monitoring tools, such as xmpi and netpipe-mpich, to give a full graphical display.

The Kalman filter is a set of mathematical equations that provides an efficient recursive method of extracting data from inaccurate observations. The filter can provide estimations of future states, and it can do so even when the precise nature of the modelled system is unknown. Kalman filtering would appear to be ideally suited to modeling a quantum system, because it does not require the exact state of the system to be known. I have been unable to find any information on applying Kalman Filtering to Quantum Computing. I will research whether it is indeed possible to apply Kalman Filtering to Quantum Computing, and if so, I will model it in the Quantum Computing Language.


Fig 2. Use-case diagram

Objectives

  1. To build a parallel quantum computing simulation library and implement it on a cluster of workstations.
  2. To implement quantum algorithms in parallel, such as Shor's Algorithm, the Quantum Fourier Transform or Grover's Algorithm.
  3. To analyse performance issues relating to simulating quantum computing algorithms in parallel.
  4. To implement a graphical user interface to the cluster.
  5. To investigate whether the Kalman Filter can be used in Quantum Computing, and if so to implement it in the QCL

Constraints

  1. The computing surface which will be used consists of only 23 relatively slow computers, connected by a 100 megabit Ethernet network. This surface pales in comparison to a serious scientific cluster, which would consist of many more, vastly superior computers, connected by a gigabit network. Achieving good speedup on the quantum algorithms might therefore be difficult to accomplish.

2. Functional and Data description

2.1 System Architecture

2.1.1 QCL

The numerical simulation library of the QCL is stored separately from the rest of the code. It consists of four main classes, "bitvec", "operator", "qustates" and "terms". These classes implement all the matrix manipulation in the language. The fundamental unit of Quantum Computing is the Qubit as stated earlier.

Definition: A qubit is a quantum system whose state can be fully described by a superposition of two orthonormal eigenstates labeled |0> and |1>;

|ψ> = α|0> + β|1> with |α|2 + |β|2 = 1

Quantum registers are the fundamental quantum data-type in the QCL. They contain the mapping between the symbolic quantum variables and the actual qubits in the quantum computer.

Definition: An m qubit quantum register s is a sequence of mutually different qubit positions (s0, s1 ... sm-1) of some machine state |ψ> ∈ C2n with n >= m.

The more entangled the qubits are in a Quantum Register, the more computationally difficult it is to apply a quantum gate to them. The two main quantum gates that are used in the QCL are the Hadamard and Controlled-Phase gates.

Definition: The Hadamard Gate is a special case of a generalised qubit rotation and is defined by the transformation matrix;

The diagram below is a simplified UML class diagram for some of the classes in the QCL numerical simulation library. The "bitvec" class represents the vector component of the qubit, which is contained in an "unsigned long" variable in the class. The term class represents a single qubit. It contains a bitvec object as well as the amplitude of the qubit, which is of type "complex". The "opMatrix" class defines a matrix operator. It extends the "opElementary" class, which in turn extends "opOperator". The "opMatrix" class contains a multi-dimensional array of term objects. For a 2-dimensional matrix like a Hadamard gate, the array is a 2-dimensional array of term objects.


Fig 3. Simplified UML description of some of the QCL Numerical Simulation classes


Matrix Decomposition:

The project will entail a good deal of research on decomposition methods and issues relating to parallel processing. I will research standard MPI decomposition techniques, as well as systolic techniques. These techniques will be used to spread the calculations of the quantum registers discussed in the last section over multiple nodes in the cluster. Research will be undertaken as to what MPI commands most suit this task.


2.1.2 User Interface

The Quantum Computing Language only runs on a UNIX command-line. Therefore it will be necessary for the end-user to start the QCL on a terminal. The head node of the cluster(tehran), can only be accessed by a remote ssh(secure shell) client. The user will be able to use any good ssh client to connect in to tehran on any platform, for example "Putty" under Windows, or just "ssh" in any terminal under UNIX.

However, using the command-line does not give the end-user a good indication as to what is happening in the cluster. For example, the fact that the head node of the cluster has decomposed a large matrix, and all the nodes of the cluster are busy performing some operation on their part of the matrix is completely transparent to the user. This is obviously desirable if the end-user does not care about how the job is being done, but it provides no indication as to what each node in the cluster is actually doing.


Fig 4. The QCL seen from the Putty program on Windows

2.1.3 Implementation of User Interface

The server part of the user interface will run on the head node of the cluster(Tehran). The main program will spawn new threads every five seconds which will get the names of all the nodes in the cluster, check their status and get their load. This can be done by using the Runtime.getRuntime.exec("<command>") method in Java, which will execute a UNIX command and return the result, which must be parsed. The status of the nodes can be checked by the UNIX command "pbsnodes -l", which lists all nodes that are not functioning correctly. The load across a particular node can be found by using "rsh". For example, "rsh odie uptime" will log onto the node called "odie", execute the command uptime, and return the result. Another thread will log onto each of the nodes in the cluster, and examine CPU and process activity. This will return information regarding the most active process on the node, as well as the percentage of CPU time being used.

All these threads will extend the Java Observable class. A single "Observer" class will observe all of these threads. This means that whenever any of the Observable classes get updated, the Observer class also gets updated automatically. This observer object will be broadcast by the main server program using Java's Remote Method Invocation, thus allowing multiple clients to connect in to the server and obtain a proxy of the observer object. This architecture is preferable to using a Socket-type TCP/IP connection.

The client application will run on a remote machine. It will connect to the server, and obtain a proxy of the object being broadcast by the Server using RMI. This object will contain all the information the client will need. This information will be displayed graphically, and updated dynamically as the client application receives new information from the server. The graphical display will be a Java swing display, which will illustrate the status of all nodes on the cluster, their load, as well as what each node in the cluster is computing. This program might be extended by displaying graphs showing CPU activity across the cluster. The program might also look at illustrating communication between the nodes.

If I have time, I might look at incorporating existing open-source cluster monitoring tools into the graphical user-interface. This would mean running an x-server on a client machine, while instructing the monitoring programs, which would be run on the cluster, to redirect their graphical output to the IP address that the x-server is running on.


Fig 5. Diagram showing data-flow for the user-interface software


2.1.4 The Kalman Filter

Researching whether Kalman Filtering is possible with quantum states will try and address the following problems.

If these questions can be answered, a method will be written for the Quantum Computing Language which will attempt to estimate a changing quantum system using the Kalman Filter.


3. Subsystem Description

3.1 The Quantum Computing Language

The Quantum Computing Language is a programming language designed to approach quantum computing programming, from a traditional "c syntax" area. This means that quantum algorithms, including their classical components, can be implemented and simulated consistently. It is written in C++ and is released under the General Public License, hence the source code is freely available.

The main features of the QCL are:


3.2 MPI

This project will rewrite the source code of QCL to run over the CA Linux cluster using the MPI library. The "Message Passing Interface" library provides a means to communicate with remote machines, using C/C++ or Fortran. It is designed for high performance, portability and flexibility, and is now the standard for message-passing libraries. The MPI specification is widely used for solving significant scientific and engineering problems on parallel computers. MPI-2 will be used for this project. This version contains new extensions to basic MPI, such as parallel I/O, remote memory access operations, and dynamic process management. The MPICH implementation of the MPI library will be used for this project. MPICH is a freely available, portable implementation of the full MPI specification. The C++ implementation in MPICH will be used for this project. The MPI C++ compiler is a wrapper for the GNU C++ compiler, therefore it will compile the QCL C++ code as well as the MPI extensions together.


3.3 Quantum Fourier Transform

The Quantum Discrete Fourier Transform iterates the qubits in a quantum register from the Most Significant Bit to the Least Significant Bit. The qubits are split with the Hadamard transformation and then a conditional phase operation is applied. The transformed state is given in reverse bit order, so the bits have to be flipped.

operator dft(qureg q) {   // input is a quantum register 
    const n=#q;           // set n to length of input
    int i; int j;         // declare loop counters
    for i=0 to n-1 {
        for j=0 to i-1 {    // apply c-phase gates
            CPhase(2*pi/2^(i-j+1),q[n-i-1] & q[n-j-1]);
        }
        Mix(q[n-i-1]);      // Hadamard transformation on qubit
    }    
    flip(q);              // swap bit order of the output
}

Fig 6. QCL code for Quantum Fourier Transform.

The Quantum Fourier Transform can be used to solve the hidden subgroup problem, which has amoung its special cases an efficient quantum algorithm for the discrete logarithm problem. Of course, solving the discrete logarithm problem leads to breaking many forms of encryption currently used, such as RSA.


3.4 The Kalman Filter

A Kalman Filter is a recursive optimal estimator that can extract data from inaccurate or uncertain observations. To use the Kalman Filter, certain conditions must hold. Firstly, the system must be linear and dynamic. The system being modelled must be able to be formulated using the linear equations given in figure 7.Secondly, it must contain measurement and process noise, both of which must be Gaussian. Various extensions to the Kalman Filter also exist, for example for non-linear systems, etc. The Kalman Filter has many uses, such as navigation and missile control.

State Equation xk+1 = Axk + Buk + wk
Output Equation yk = Cxk + zk

Fig 7. Linear System equations. A, B, C are matrices. w and z are noise. u is an input to the system


3.5 Hardware Resources

The primary hardware resource which will be used for this project is the Computing Applications Linux Cluster. This is a 23 node cluster, that consists of 23 Pentium Pro 266mhz machines running Debian GNU/Linux. Each machine has 32 Megabytes of RAM. This cluster is a "Beowulf" cluster, which means that one of the machines is the head node, and all the other nodes simply compute jobs given to them and send back results. The network used is a 100 megabit Ethernet. The cluster was built by a small group from Redbrick, the DCU Networking Society, in August 2001. This cluster was built purely as a proof of concept, and was not built for serious scientific computation.


3.6 Software Resources

The parallel extension to the Quantum Computing Language will be written in C++. The compiler which will be used is the mpiCC compiler, which is the MPI C++ compiler from MPICH. This is simply a wrapper for the gnu C++ compiler. The user-interface will be written using Java SDK1.4.1. This version must be used due to previous bugs with the Runtime class under UNIX. The editor that will be used for writing code will be VIM. Any UML diagrams will be done in the open-source DIA program.


4. Projected Schedule

4.1 Pre-Examinations


4.2 Post-Examinations - Semester 2


5. Appendix

5.1 References

Quantum Computing Applications


Quantum Computing Papers/Books


Parallel processing links


Software Resources


5.2 Glossary