View source for How Quantum Computing/Factoring Works(q)


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<code>0, Y </code> 1, or
X'''Y is a 1, X<code>1,Y</code>1, and of if X'''Y' is 1, that is X<code>1, Y</code>0.

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

that means X''''Y'''X'''Y' <code> 0 which is true because X''''X </code>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<code>0 with ||c_x0||^2 and X</code>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' ====<code> k and i' !</code> i and j' !<code> j. Where a !</code> 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[[ + 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

sum''i  ||a''[[ij->k]]||^2 = 1


Now, suppose multiply ||X> and ||Y>, we get
|-
|X>||Y> <code> c''x0 c''y0 ||X</code>0>||Y<code>0> +  c''x1 c''y0 ||X</code>1>||Y=0> + c''x0c''y1
|-
|X<code>0>||Y</code>1> + c''y1 c''x1||X<code>1>||Y</code>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<code>0,Y</code>0. It isalso consitent wth ||c''x0 c''y0||^2 <code>  ||c''x0||^2||c''y0||^2. This expression means that p(X </code> 0 and Y<code>0) </code> p(X<code>0) p(Y</code>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<code>0,Y</code>1. The output of the OR gate is 1. However, based on the
output, we cannot tell if the input was X<code>0,Y</code>1, or X<code>1,Y</code>1 or
X<code>1,Y</code>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.