The Assignment:

You will use a version of a class that you previously wrote (the matrix class) in a small application program!

Before Starting:

Read Sections 6.1-6.3

Files that you must write:

1. matrix.h: The header file for a matrix template class. You may modify your matrix class from earlier in the semester, or you may use the version that Michael Main sent to you on Oct 18.
2. matrix.template: The implementation file for the new template matrix class. Once again, you may modify your matrix class from the earlier assignment or you may use the version that Michael sent.
3. qt.cxx: This is the application program described below. It uses matrixes in which the components are complex numbers rather than double numbers!

Discussion of the Assignment

Verifying the Quantum Pseudotelepathy Solution

On Oct 18, Michael will send you a paper that describes a problem that can be solved using a quantum computer. Your assignment is to write a small application program that verifies that the proposed quantum program correctly solves the problem for all possible situations (regardless of whether the students get red stones or blues stones or some combination thereof).

We will take some time in class to discuss different approaches to the verification, but all approaches will use the matrix class in which the components are complex numbers.

Frequently Asked Questions

How Does My Program Represent a Superposition of Triplets?

By a 1x8 matrix of complex numbers. For example, if the first entry in the superposition matrix is the number 0.5, then that means that the triplet |000> has a probability of 0.5² (i.e., 25%) of occurring.

Is There Some Shorter Phrase than "Superposition of Triplets"?

Yes. You can call this the "state" of the quantum computer.

How Does My Program Represent a Quantum Program That Alice and Her Friends Run?

By an 8x8 matrix of complex numbers.

How Do I Compute the Result of Running a Quantum Program?

If the quantum computer is in a state s (a 1x8 matrix) and the program P (an 8x8 matrix) is run, then the resulting new state is Ps (a matrix multiplication that gives a new 1x8 state matrix).

Exactly What Does My Program Verify?

Alice and her friends create a quantum computer that starts in a particular state. Let's call that state s. There are four possible tests that the aliens might give us. For example, one test is when Alice gets a blue stone and the others get red stones. In this case, the program that they run is:

    (blue % red % red)

using the Kronecker product on the blue and red matrixes from the paper you were given to read. For this particular case, you must compute the result state with the matrix multiplicaion:

    (blue % red % red)s

Within this result state, you must check that any losing triplets (such as |001>>) have a zero scalar.

How Do I Check Whether a Complex Number Is Zero?

This is a better question than it sounds. Let's call our number x. You should not run a simple boolean test (e.g. x==0) because computations with non-integers have round-off errors that make an exact equality unlikely. Instead, you should check to see whether x is very close to zero. With a complex number, you can do this by checking whether the norm of x is quite close to zero. (For a complex number x=ai+b, the norm is the a²+b² in C++, it is computed by norm(x). I would suggest that you write a boolean function (with one complex parameter) to determine whether a the norm of a complex number is quite close to zero. For our purposes, "close to zero" can mean that the value is less than 0.00001.)

How do I tell the quantum computer scientists about my program?

You should include a small file called readme.txt (just create it in emacs). This file tells the scientist how to compile your program and how to use the program (and interpret its output).

Just what is my program's output?

That's a little bit up to you. But, in the end, your program should provide the scientist with a definite yes or no answer about whether the approach works for all four possible stone combinations. The scientist should not have to examine any matrixes to figure this out.

Anything else?

Part of your grade will be based on your program's organizaition. Did you design and use sensible functions to do subtasks such as determining whether a number is close to zero? Did you use functions to avoid repeating code in several different places?