Ok, forgive my ignorance, but why is it that quantum algorithms can ONLY run on quantum computers? Is it the fact that qubits can have three states? If that is the case (which it likely isn't), why is base 3 better for this work than base 2?
Basically: Qubits (sort of) encode all possible states that a standard string of bits can take at the same time as a superposition, such that when you measure them, you have a possibility of observing each possible setting of the bits.
You can manipulate the possibility of observing certain states by performing operations on the bits (which are effectively interference). So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation. In order to be sure of a result, you need to repeat the calculation to get a desired confidence (or just check the answer directly if that would be faster).
> So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation.
Not necessarily, some quantum algorithms give an answer with 100% probability (like the Deutch-Josza algorithm). You're right in that the two most interesting ones (Grover's and Shor's algorithms) are probabilistic, though.
No, they can run on quantum computers, but to properly simulate a quantum computer, you may need exponential space/time. Googling for supporting data brought up http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html which discusses simulating Shor's algorithm on a classical computer.
The reason for the exponential is that the bits are all in a superposition of all possible states (so for a 14-bit register, that's a superposition of 2 to the 14 states), which operations all act on. Or something like that. I'm not really that clear on the details. :(
> Or something like that. I'm not really that clear on the details. :(
Your intuition is correct. Quantum algorithms seem to perform better than classic algorithms because there are certain operations (like fourier transforms) that can be performed exponentially faster (as of today) than classic algorithms.
It is still unknown however whether or not we can simulate quantum computations classically without exponential blowup otherwise it would resolve major open questions in complexity theory.
Quantum computers make use of quantum mechanics. So things like entanglement and decoherence are essential to the algorithms. It has nothing to do with base 2.
It's not so much 3 states, as it is two states and a superposition of both states, meaning that the qubit is effectively both a 0 and a 1 at the same time.
Obviously that isn't the case; if it were we'd simply roll out ternary computers, which have been used before.
I'm no physicist, and my knowledge of quantum is mostly memories of an intro course I took 5 years ago, so I hope someone with a bit more knowledge can come and fill in the gaps here. Nevertheless, the basic principle is that quantum superposition allows us to parallelise things with relatively reasonable space requirements.
Restricting the problem to a fixed size input makes factoring an O(1) operation; so I still don't see what all the fuss is about.
Unless you know a way of extending this to handle an arbitrary amount of I/O then it's just a way of implementing nondeterministic finite state machines; which are no more powerful than deterministic finite state machines.
Rather than downvoting you to oblivion, I'll point out that "Restricting the problem to a fixed size input makes factoring an O(1) operation" makes no sense. Sorting an array of N items using a comparison sort has a lower complexity bound of O(N log(N)) in the worst case. Yes, of course that becomes O(1) if you say N is constant, but that's really not helpful at all.
http://en.wikipedia.org/wiki/Shor%27s_algorithm