Through the use of quantum phenomenon, a significant asymptotic speed up can be achieved over conventional programs for an interesting set of problems. The purpose of this tutorial is to introduce you to the basic concepts of quantum programming using examples that you can try out on the online jsqubits runner. I try to assume as little knowledge of quantum physics as possible and minimize the amount mathematics required.
Like conventional computers, quantum computers typically use a binary encoding of information. However, instead of "bits", quantum computers use "quantum bits" (abbreviated to "qubits"). These are like bits in that they have two states (typically represented as "0" or "1"), but they have the extra properties of being capable of being in a "superposition" of states and being "entangled" with each other (terms that will be explained later). Implementation details will not be covered, but real implementations of qubits do exist using, for example, nuclear spin.
There are several special quantum operators. One of these is called the Hadamard operator (named after the mathematician Jacques Hadamard). At first glance, the Hadamard operator seems to put a qubit into a random state. If we were to print the state of a qubit after applying the Hadamard operator to it, then half the time it would be 0 and the other half it would be 1. But there is much much more to it than that.
For instance, if you apply the Hadamard operator twice to a qubit (without doing anything in between), then the qubit will return to its original state. Other operators are so bizarre that they are best modelled as rotations of a sphere (more on that later). Before going any further, let us first look at the Dirac notation.
This tutorial uses the "Dirac" (or "bra-ket") notation commonly used in quantum mechanics.
The advantages of this notation will not be immediately apparent,
but it helps to use the notation used in most of the quantum programming literature.
Under the Dirac notation, the state of a quantum computer is prefixed by a vertical bar "|"
and ends with a greater-than symbol ">".
For example, a four qubit quantum computer with all its qubits in a zero state
is represented as |0000>.
Although the Hadamard operation seems to result in one of two randomly chosen possible outcomes, it turns out that it is best to think of the system as being in both states at once. This is more formally called a superposition of the two states. Each of the different possible outcomes will have a different associated probability. It turns out that this is best modelled by associating an "amplitude" with each state. Amplitudes can be negative. They can even be complex numbers (i.e. involving the square root of negative one), but fortunately we can avoid complex numbers for most of this tutorial! The only constraint is that they each must have a magnitude less than one, and the sum of the squares of their magnitudes must equal one.
To compute the probability of the system being in a particular state, you need to square the magnitude of its associated amplitude. Hopefully the meaning of this will be more clear with some examples.
After applying the Hadamard operator to a qubit that is originally in a zero state (|0> in the Dirac notation),
it ends up in a superposition of |0> and |1>,
each with an associated amplitude of the square root of one half
(remember, you need to square the amplitude to get the probability).
The Dirac notation for the resulting state is:
√(1/2)|0> + √(1/2)|1>
Note that the '+' symbol here does not really mean that we are adding the two states together.
Adding |0> to |1> does not give you anything besides
|0> and |1>.
It is important to understand that you cannot directly determine the values of the different amplitudes. To extract any information out of a quantum computer, it is necessary to have one or more "measurement" steps where qubits are determined to be either "0" or "1" with the likelihood of either one being dependent on the amplitudes of the quantum states.
Before jumping to the conclusion that dealing with amplitudes seems all a bit pointless,
look at what happens when you
apply the Hadamard operator to a qubit that originally is |1>.
The resulting state is:
√(1/2)|0> - √(1/2)|1>
Notice the minus sign.
The significance of the minus sign becomes apparent when you apply the Hadamard operation twice.
Suppose we start with |0>.
As described above, one application of the Hadamard results in
√(1/2)|0> + √(1/2)|1>.
As already explained, this is called a superposition of both |0> and |1>.
The result of applying an operator to
a superposition of states is the combination of applying that operator
to each of the individual states that make up that superposition.
So, in this case, you are applying the second Hadamard operator to both
√(1/2)|0> and √(1/2)|1>.
Applying the Hadamard to √(1/2)|0> gives:
√(1/2)√(1/2)|0> + √(1/2)√(1/2)|1>
which simplifies to
0.5 |0> + 0.5 |1>
Applying the Hadamard to √(1/2)|1> gives:
√(1/2)√(1/2)|0> - √(1/2)√(1/2)|1>)
which simplifies to
0.5 |0> - 0.5 |1>
Combining these gives:
0.5 |0> + 0.5 |1> + 0.5 |0> - 0.5 |1>
Again, notice that the last term has a minus sign.
The two instances of |0> combine,
and the two instances of |1> cancel each other out,
to give a final state of |0>.
This process of states re-enforcing and cancelling each other out is
known as interference.
It is the same quantum effect behind the interference pattern
that results from Thomas Young's famous two-slit experiment with light.
Similarly, applying the Hadamard twice to |1> brings the
state of the system back to |1>.
jsqubits is a JavaScript library for quantum computation simulation. For this tutorial, I will use examples that you can try out using the online jsqubits runner.
Using jsqubits, the easiest way to create an initial state is using the jsqubits function.
It takes a binary string and returns a QState object representing the state of your quantum computer.
For example,
jsqubits("|0101>") creates a 4 qubit quantum state of |0101>.
QState objects have a number of methods including the hadamard() method.
You must specify the index of the bit to be operated on, with the right most bit being bit 0,
and the left most bit being bit n-1 for an n bit state.
Try entering the following text into the text field of the
jsqubits runner
and pressing the "run" button.
jsqubits('|001>').hadamard(0)
You should find you get 0.7071 |000> - 0.7071 |001>
And if you try jsqubits("|001>").hadamard(0).hadamard(0),
you should find you get back your original state of |001>
As a convenience, you can also specify a range of bits using an object with "from" and "to" properties,
and the operator will be applied to each of the bits in that range (inclusive).
The constant jsqubits.ALL can be used to apply the operator to all the bits.
For most operators (except where indicated), you may also use an array of bit indexes.
Try the following:
jsqubits("|00>").hadamard(jsqubits.ALL)
You will get 0.5 |00> + 0.5 |01> + 0.5 |10> + 0.5 |11>
Superdense coding allows you to communicate two classical bits of data by transmitting only a a single qubit. Note that, as this technique can only be applied to classical bits, it can not be used on the resulting qubits to do any further compression.
There is an important catch to superdense coding. The communicating parties need to have pre-arranged for the data exchange by obtaining qubits that have been specially prepared together in what is called an "entangled" state. So superdense coding would only be useful if the two parties know that they will be communicating well in advance of the time at which the communication is to occur.
Say Alice wishes to transmit two classical bits to Bob. The outline of the process is as follows: a) A pair of qubits are entangled, one given to Alice and one to Bob. b) Alice encodes the two bits of information into her single qubit an sends it to Bob. c) Bob manipulates both his own qubit and the qubit sent by Alice to extract the two bits.
As mentioned, superdense coding requires two qubits to be prepared in an entangled state. This means that the two qubits are in a superposition of states and that their states are correlated in some way. For this example we require that the qubits are in the state:
√(1/2)|00> + √(1/2)|11>
When in this state,
the two qubits are either both 0 or both 1.
The easiest way to simulate this in jsqubits is to
start with the two qubits in the state |00>,
apply a Hadamard operation to one of them,
and then apply what is called a "controlled-not" (or cnot) operator
on the pair of them.
So, before we can progress further,
we need to explore the "not" and "cnot" operators.
The "not" operator simply flips a qubit (just like its classical equivalent).
In jsqubits, QState objects have a "not" method that takes the index of the bit to be flipped.
For, example, jsqubits('|00>').not(1) results in |10>.
The controlled-not or "cnot" operator requires both a target bit and a control bit.
It will flip the target bit if, and only if, the control bit has a value of 1.
In jsqubits, the cnot operator takes the control bit as its first argument
and the targit bit as its second.
For example, jsqubits('|00>').cnot(1,0) leaves the state unchanged as |00>,
but jsqubits('|10>').cnot(1,0) results in |11>
So, to prepare two qubits in the state
√(1/2)|00> + √(1/2)|11>,
you can do the following in jsqubits:
jsqubits('|00>').hadamard(1).cnot(1,0)
To encode two bits into one qubit,
we need to introduce the Pauli operators (named after the physicist Wolfgang Pauli).
There are three Pauli operators, X, Y and Z.
The X operator is just another name for the "not" operator.
i.e. it just flips the bit of the qubit to which it is applied.
In jsqubits, the x() and controlledX() methods
are aliases for not() and cnot() respectively.
Instead of flipping the qubit to which it is applied,
the Z operator flips the sign of the amplitude of the |1> component of the qubit,
and leaves the amplitude of the |0> component untouched.
So, in jsqubits, jsqubits('|0>').z(0)
leaves the state as |0>,
and jsqubits('|1>').z(0)
results in the state -1 |1>
(i.e. it is still in a |1> state, but its amplitude is -1).
As an illustrative example,
consider the effect of combining the Hadamard and Z operators.
If a qubit is initially in a state of |0>,
then applying a Hadamard will result in
√(1/2)|0> + √(1/2)|1>.
If you apply the Z operator this this you get
√(1/2)|0> - √(1/2)|1> and,
finally, after applying a Hadamard again, you will get:
|1>.
i.e. jsqubits('|0>').hadamard(0).z(0).hadamard(0) gives |1>.
The controlledZ() method, like the cnot method, requires
both a target bit and a control bit.
It only applies the Z operator if the control bit is 1.
The only remaining Pauli operator is the Y operator.
We do not actually require this operator for the algorithms covered in this tutorial,
but it is mentioned here for completeness.
The Y operator is quite tricky to describe.
It is equivalent to applying the Z operator, then the X operator, and then multiplying the amplitudes
by the imaginary number i.
So, in jsqubits, jsqubits('|0>').y(0)
leaves the state as i |1>,
and jsqubits('|1>').y(0)
results in the state -i |0>.
We can now describe how to encode two classical bits into one qubit. Recall that Alice has two classical bits, a and b, and has one of a pair of entangled qubits, and Bob has the other member of the pair.
If both a and b are 1's, then Alice applies both the Z and the X operator to her qubit.
This can be simulated in jsqubits with the following code:
// The bits to be sent to Alice are set in the string called input:
var input = "10";
// First, create a pair of entangled qubits
var state = jsqubits('|00>').hadamard(0).cnot(0,1);
// Assume that qubit 0 is sent to Bob, and that qubit 1 is sent to Alice.
// Alice prepares her qubit (qubit 1)
var alice = 1;
if (input.charAt(0) === '1') {
state = state.z(alice);
}
if (input.charAt(1) === '1') {
state = state.x(alice);
}
// Alice sends her qubit to Bob.
Once Alice has encoded her two classical bits into her one qubit, she can send that qubit to Bob, and Bob can proceed to decode the qubit as follows.
At the end of these steps, the value measured for Alice's qubit will be the original value of "a", and the value measured for Bob's qubit will be the original value of "b".
Here is the full algorithm in jsqubits (try it out in the jsqubits runner):
// The bits to be sent to Alice are set in the string called input:
var input = "10";
// First, create a pair of entangled qubits
var state = jsqubits('|00>').hadamard(0).cnot(0,1);
// Assume that qubit 0 is sent to Bob, and that qubit 1 is sent to Alice.
// Alice prepares her qubit (qubit 1)
var alice = 1;
if (input.charAt(0) === '1') {
state = state.z(alice);
}
if (input.charAt(1) === '1') {
state = state.x(alice);
}
// Alice sends her qubit to Bob.
// Bob recovers the input bit values.
var bob = 0; // Bob's qubit
state = state.cnot(alice, bob).hadamard(alice);
state.measure(ALL).asBitString();
I highly recommend reading John Watrous' lecture notes