Hi Nicolaas
First, let me say that i m just an ordinary student of physics. The
people here have a lot more experience than i do.
Anyways, i will give u some pointers.
Quantum Computers do not function like classical computers and so you
cannot program them like classical computers. Things like loops, if
statements, etc do not directly make sense.
Basically, here a description of a Quantum Computer and how it is
supposed to work. The description is a little bit amateurish.
In Quantum mechanics, we talk about ensembles and how things can
exists in superposition of states.
For example. Here's the classical analogy
Imagine the boolean gate OR Function
OR(X,Y) = X' * Y + X * Y + X * Y'
Basically, according to classical boolean theory,
OR(X,Y) will be a 1 if X'*Y is or 1 , that is to say X=0, Y = 1, or
X*Y is a 1, X=1,Y=1, and of if X*Y' is 1, that is X=1, Y=0.
Basically, u also need to notice that X'*Y is orthogonal to X*Y'
that means X'*Y*X*Y' = 0 which is true because X'*X =0 and Y'*Y=0
Now, the above expression can be rewritten as follow
OR = |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|
On a classical computer, at one time X can be either 0 or 1, and so
does Y, so that output is also only allowed to be 1 or 0.
Now, on the otherhand, in Quantum mechanics, particles, can exists in
superposition of states, that means that,
X can be expressed as a combination of 0 or 1.
|X = c_x0 |0 + c_x1|1
Basically, |c_x0|^2 is taken to be the probability of X being a 1.
That means that if you measure the state of a particle |X>, you are
gaurrented to get 0 or 1, not both at the same time. However, you
cannot predict with certainty which state you are going to get.
However, the only certainty is probability of getting 0 at X is
|c_x0|^2 and probability of getting 1 is |c_x1|^2
Moreover, interestingly, c_x0 can also be complex numbers.
So, you may wonder if X what it means to say that X is in
superposition of both 1 and 0. There are many interpretations. One
interesting one is the many world interpretation.
It says that when a particle is prepared in a superposition of states,
like our |X>. the world diverges with X=0 with |c_x0|^2 and X=1 with
|c_x1|^2.
where |c_x0|^2 + |c_x1|^2 = 1
And so, can we expression Y as follows
|Y> = c_y0 |0> + c_y1|1>
Now, if you increase the number of input variables, for example say n
= 128, you have in fact, prepared a system with 2^128 states. However,
if you try to measure the state of |X_1,X_2,...X_n>, you will only get
one of all possible 2^128 states. Because of this dynamics, a Quantum
Computer can try 2^128 states in parallel at the same time.
Now, our expression is still given by
OR(X,Y) = X' * Y + X * Y + X * Y'
However, you need to understand since X and Y are no longer binary,
OR(X,Y) is not gaureented to be 1 or 0. Rather OR(X,Y) has a
probability of being 1 or 0.
Upto now, you will be inclined to say, that well, how is it useful.
After all, you are preparing a system in 2^128 states. And you get
only one answer. So, you may ask, how can i get the answer i am
looking for example.
Now, Quantum Mechanics is not so simple, as the worlds diverging. In
fact, the worlds can interfere and cancel themselves out.
|c_x0|^2 is the probability of getting x=0,however, c_x0 can also be
a complex number. So, it has has phase. c_x0 = p_x0 exp(i theta_x0).
This makes matters a lot of complicated.
The innocent looking presence of phase allows the different worlds
to interfere.
Our expression
OR = |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|
Our OR gate, can be seen as an evolution device. In Quantum Mechanics,the word used to denote an OR like device is operator. Basically, the application of the OR gate to the quantum sytem input system X,Y , evolves it from that state to the state at the output.
After all, this is even classical gates do. Given an input state, they take it to the output state.
Moreover, just as our classical device, |k><i,j| is othogonal to |k'><i',j'|
where k' != k and i' != i and j' != j. Where a != b means a is not equal to b.
In Quantum mechanics, there is a requirment for probability conservation
Basically, it goes something like this
sum_i |c_xi|^2 = 1
This is true of any probability theory. The sum of probabilities is always
1. After all, this is an axiom of probability theory.
There is another equivalent statement called the Unitary requirement that has the same effect as probability conservation.
Our expression
OR = |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|
[Thanks to Kevin Scaledeferri, for pointing out the correct form of the expression]
Suppose we rewrite or OR expression as
OR = a[01->1] |1><0,1| + a[10->1] |1><1,0| + a[11->1] |1><1,1| + a[00->0] |0><0,0|
Comparing the 2 expression above, we can decipher that
a[ij->k] = 1.
However sum_[ij->k] |a_[ij->k]|^2 /= 1. And so it does not converse probability.
However, for example,
OR = (1/sqrt(4)) ( |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|)
does
a_[ij->k] = 1/2
sum_i |a_[ij->k]|^2 = 1
Now, suppose multiply |X> and |Y>, we get
|X>|Y> = c_x0 c_y0 |X=0>|Y=0> + c_x1 c_y0 |X=1>|Y=0> + c_x0c_y1
|X=0>|Y=1> + c_y1 c_x1|X=1>|Y=1>
othewise written as,
|X,Y> = c_x0 c_y0 |0,0> + c_x1 c_y0 |1,0> + c_x0c_y1|0,1> + c_y1 c_x1 |1,1>
Where |c_x0 c_y0|^2 is the probability of getting a X=0,Y=0. It isalso consitent wth |c_x0 c_y0|^2 = |c_x0|^2|c_y0|^2. This expression means that p(X = 0 and Y=0) = p(X=0) p(Y=0). This is a natural expression for the probability of independent events.
Now, back to our OR operator
Now, if i apply the OR operator to our input state |X,Y>
OR|X,Y> = (1/sqrt(4)) ( |1><0,1| + |1><1,0| + |1><1,1| + |0><0,0|)
c_x0 c_y0 |0,0> + c_x1 c_y0 |1,0> + c_x0c_y1|0,1> + c_y1 c_x1 |1,1>
the resulting expression is
= (1/2) |1> ( c_x1 c_y0 + c_x0c_y1 + c_y1 c_x1 ) +
(1/2) |0> ( c_x0 c_y0)
So, the probability of getting a 1, is
|<1|OR|X,Y>|^2 = (1/4) | c_x1 c_y0 + c_x0c_y1 + c_y1 c_x1|^2
= 1/4 |p_x1p_y1 exp(i (theta_x1 + theta_y1) ) + p_x1p_y0 exp(
i(theta_x1 + theta_y0)) + p_x0 p_y1 exp( i(theta_x0 + theta_y1))|^2
In the above expression, it is important to notice that the phases
interfere with each other and cancel each other out. This is what
creates all the difference in the world. The phases are not innocuous
as we had thought them to be.
So, not only do the worlds seperate at each instant, they also interfere
with each other. So, voila, parallel computing.
----
Revisible Computing and answers to NP-completeness
A example of factorization
----
Basically, suppose we take a (2n)-bit multiplier with 2 n-bit
multiplicand with (2n)-bit output. Now, suppose we interested to know
a few things. We take the output of the (2n-bit) multiplier and put a
big AND gate at end. The output of this gate is true, if in fact, an
input combination of mutiplicand produces the the number to be
factored at the output. Suppose We are interested in factoring
[O_0,O_1,O_2...,O_n] = [0,1,1,0...,1] . Let's call this number N . Our
AND gate basically, is O_0'*O_1*O_2*O_0'...*O_n
In normal binary computers, certain operations are not reversible.
For example, back to our OR gate.
Suppose X=0,Y=1. The output of the OR gate is 1. However, based on the
output, we cannot tell if the input was X=0,Y=1, or X=1,Y=1 or
X=1,Y=0. So, you can even say that information is lost from inputs to
the outputs. Suppose, i have a random binary generator at the input.
Based on the output of a classical gate, mostly impossible to tell
what the inputs of the circuit were.
Now, the idea of Quantum Computing, leads to reversible computing. [I
m not an expert on this topic either. I am not sure if Quantum
Computing requires reservsible computing]. However, a Quantum
equivalent of 2-bit AND Gate, has 4 not 3 connections coming in and going
out.
a Quantum 2-qubit AND gate needs to have 2 inputs, one output, and one
revisibility channel.
So, now, suppose, we have the quantum equivalent of this
classical multiplier, because of reversibility of we can propogate the
1 from the output of our AND gate, in our multiplier, and trace them back
to the input combinations that generate the 1 at the output. Notably,
these combinations are also factors or our number N.
Shor's algorithm is different. But, hopefully, this helps.
