Can someone explain quantum computing to me in laymans terms?

Quantum computing as I understand it involves the manipulation of particles to act in such a way that they can be used to compute information. From what I remember from "The age of spiritual machines", it has something to do with particles existing in an undertermined state until the instant they are obvserved, meaning we could calculate anything instantaneously.

Instead of a "bit" which can either be 0 or 1, quantum computers have "qubits" that exist as either 0, 1, or both.

I'm sure a physicist who knows far more than I do will correct me and give you more information, but that's how I understand it.

Have you tried Wikipedia?

Yes, I have :). Some of the things I read on there seemed to be different then what I have read elsewhere, however (i.e. the logic gate thing). Basically, I guess I want to know WHY quantum computers are faster. I couldnt really grasp that from the wikipedia article.

In a regular computer a bit is either 0 or 1. In a quantum computer a qubit can be both simultaneously. Until you examine the value of the bit it is actually some combination of 0 and 1. Furthermore we can determine that when we measure it it will be 0 with some probability and 1 with some probability.

To see why this is useful imagine a qubit register of 32 qubits. When we read the value of the register it will have some clearly defined 32 bit value - but we don't know what value we'll read. Instead we know with what probability it will have any particular value.

Here's where I'll get a bit vague since the formalism is complicated. We can apply transformations to the register without actually measuring it's value that will affect the probabilities. By cleverly designing these transformations we can learn interesting things. For example if we were factoring a large number we could design a transformation that increased the probability the the register contained a factor of that number and corresponding decreased all other probabilities. By repeating this transformation over and over again we can make the probability arbitrarily high that when we read the register it will contain a factor of our large number in it.

This is helpful because the number of transformations needed to accomplish a sufficiently high probability is quite low. Thus we can achieve much better Big-O times than would be possible in a classical computer. This is because each transformation we apply applies to all possible 32 bit values rather than just one as is the case in a classical computer

Just as a subatomic particle can be described as a superposition of states before observed, data theoretically can be as well.

Instead of bits which are either 0's or 1's, you have qubits which are in a superposition of the two states 0 and 1 before observed. When entangled with other qubits you have an entire system/program which is in a superposition of states.

Programs that would normally be solved by brute force by looking at all the possibilities would be solved instantanously by a quantum computer.

It's like having a big hotel with lots of rooms, and you are looking for a lost suitcase in one of them.

Normal computer: Search each of the rooms one by one, before you find the suitcase.

Quantum computer: People enter every room at the same time, and only the one that found the suitcase exists after you look at it.

Quote:

Original post by Platinum314 Just as a subatomic particle can be described as a superposition of states before observed, data theoretically can be as well. Instead of bits which are either 0's or 1's, you have qubits which are in a superposition of the two states 0 and 1 before observed. When entangled with other qubits you have an entire system/program which is in a superposition of states. Programs that would normally be solved by brute force by looking at all the possibilities would be solved instantanously by a quantum computer. It's like having a big hotel with lots of rooms, and you are looking for a lost suitcase in one of them. Normal computer: Search each of the rooms one by one, before you find the suitcase. Quantum computer: People enter every room at the same time, and only the one that found the suitcase exists after you look at it.

Holy shit, I like the prospects of this =)

Note to self: hire team of suitcase rescue experts = profit?

Quote:

Original post by Ceoddyn Quote: Original post by Platinum314 Just as a subatomic particle can be described as a superposition of states before observed, data theoretically can be as well. Instead of bits which are either 0's or 1's, you have qubits which are in a superposition of the two states 0 and 1 before observed. When entangled with other qubits you have an entire system/program which is in a superposition of states. Programs that would normally be solved by brute force by looking at all the possibilities would be solved instantanously by a quantum computer. It's like having a big hotel with lots of rooms, and you are looking for a lost suitcase in one of them. Normal computer: Search each of the rooms one by one, before you find the suitcase. Quantum computer: People enter every room at the same time, and only the one that found the suitcase exists after you look at it. Holy shit, I like the prospects of this =) Note to self: hire team of suitcase rescue experts = profit?

It's a bit more complicated than that. Extending that same analogy, sometimes a person that didn't find it will exist after you look at it. So you need to run the program and observe its results multiple times to find the most probable answer.

I think I understand it better now. Thanks for the replies guys.

I think I explained it to ScottC a few weeks ago, I'll have to collect that data together and make a wiki page or something on it.