5/24/13

idea for explaining quantum computation..

start with a Turing machine,

cut the infinite tape down to 3 bits,

instead of having 3 bits, list out the 8 possibilities (000, 001, ..., 111), and have a tape with 8 bits which are all 0 except for one 1, to show which 3-bit state we're in,

instead of a state-machine for doing computation, we'll just have an 8x8 matrix where each row represents which state we should go into if our input is the 3-bit sequence for that row (that is, each row is 0's everywhere except for one 1), and we do the computation on our 8 bit vector by multiplying it by this matrix

now, instead of each row being 0's with one 1, let the numbers be anything as long as they sum to 1.

now, to allow for mysterious probability interference (probabilities canceling each other out), we need negative probabilities, so we'll let the numbers in our vectors represent square roots of probabilities (so after we square them all, they should add to 1).

now, for whatever reason, we actually want to allow imaginary numbers, and to make sure they're positive after "squaring" them, we'll actually multiply each number by it's complex conjugate before summing them all up to get 1.

also, for whatever reason, we constrain the matrix to be invertible,

and that's it.. we have a quantum computation, where the vector is our tape, the matrix is our computation, and the result of multiplying the vector by the matrix is our output tape.

No comments:

Post a Comment