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 X0, Y 1, or XY is a 1, X1,Y1, and of if XY' is 1, that is X1, Y0.

Basically, u also need to notice that X'Y is orthogonal to XY'

that means X'YXY' 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 = cx0 ||0 + cx1||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 |- |cx0||^2 and probability of getting 1 is ||cx1||^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 X0 with ||c_x0||^2 and X1 with |- |c_x1||^2.

where ||cx0||^2 + ||cx1||^2 = 1

And so, can we expression Y as follows |- |Y> = cy0 ||0> + cy1||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 ||X1,X2,...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.

|- |cx0||^2 is the probability of getting x=0,however, cx0 can also be a complex number. So, it has has phase. cx0 = px0 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

sumi ||cxi||^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[[ + a[00->0|01->1]] ||1><0,1|| + a[[10->1]] ||1><1,0|| + a[[11->1]] ||1><1,1|] ||0><0,0||

Comparing the 2 expression above, we can decipher that

a[[ij->k]] = 1.

However sum[[a[ij->k|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

sumi ||a[[ij->k]]||^2 = 1

Now, suppose multiply ||X> and ||Y>, we get |- |X>||Y> cx0 cy0 ||X0>||Y0> + cx1 cy0 ||X1>||Y=0> + cx0cy1 |- |X0>||Y1> + cy1 cx1||X1>||Y1>

othewise written as,

|- |X,Y> = cx0 cy0 ||0,0> + cx1 cy0 ||1,0> + cx0cy1||0,1> + cy1 cx1 ||1,1>

Where ||cx0 cy0||^2 is the probability of getting a X0,Y0. It isalso consitent wth ||cx0 cy0||^2 ||cx0||^2||cy0||^2. This expression means that p(X 0 and Y0) p(X0) p(Y0). 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||)

cx0 cy0 ||0,0> + cx1 cy0 ||1,0> + cx0cy1||0,1> + cy1 cx1 ||1,1>

the resulting expression is

       = (1/2) ||1> ( cx1 cy0  +  cx0cy1 + cy1 cx1 ) +
         (1/2) ||0> ( cx0 cy0)

So, the probability of getting a 1, is

|- |<1||OR||X,Y>||^2 = (1/4) || cx1 cy0 + cx0cy1 + cy1 cx1||^2

= 1/4 ||px1py1 exp(i (thetax1 + thetay1) ) + px1py0 exp( i(thetax1 + thetay0)) + px0 py1 exp( i(thetax0 + thetay1))||^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 O0'O1O2O0'...O_n

In normal binary computers, certain operations are not reversible.

For example, back to our OR gate.

Suppose X0,Y1. The output of the OR gate is 1. However, based on the output, we cannot tell if the input was X0,Y1, or X1,Y1 or X1,Y0. 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.