What makes a quantum computer so different (and so much faster) than a conventional computer?

Answer 1

It is easy to think of computation as something abstract that takes place in the realm of ideas, rather than in the physical world. After all, a computer program makes reference to the laws of mathematics, not to the laws of physics. But in the final analysis, any actual computation must be done by a physical system, exploiting the laws of physics to manipulate information that is represented by the state of some device, such as the directions of magnetization at some particular spots on a hard drive or the conductivity of a specific set of transistors inside a computer's memory chip. Because each bit of information can take on two values, different physical states are chosen to correspond to "0" or "1" respectively.

in a quantum computer, the information is represented by physical states that are sufficiently microscopic and isolated so that they obey the laws of quantum mechanics. The spin of a single electron or the configuration of an individual ion, for example, are two among many possible candidates for storing such a quantum bit (or qubit) of information. The jury is still out on which system is optimal, so for the sake of this discussion imagine a computer in which the information is stored in the form of coins placed on a tabletop, with heads ("1") and tails ("0") being the two possible states of each bit. Then convert the tabletop into a quantum computer by substituting quantum coins for which heads and tails are quantum mechanical states.

Answer 2

To cut to the chase, in an ordinary computer, we have a specified algorithm such that given an input (comprising of a sequence of bits 001010....) we get an output (sequence of bits as well).

On a quantum computer, the state of the qubits is not just a sequence of bits, but a _superposition_ of a sequence of bits.

E.g. it can be "quarterway" between 00, 01, 10, 11. Physicists write this as (1/2)( |00> + |01> + |10> + |11> ). Don't be puzzled by the 1/2 - we have to take the square in order to compute the probability of each state.

So a state can be a superposition of all possible m bits! After running through the computer, we also get all possible outputs. And so, we've effectively computed f(s) for ALL strings s of m bits at the same time. On a classical computer, this would have taken 2^m computations, but only 1 computation on a quantum machine.

Sounds too good to be true? Yup it is. The problem is that there is no quick way of searching through the list of 2^m results to get the one we want. The best algorithm we have is Grover's algo: given an unsorted list of n elements, a quantum computer can find a particular element in about sqrt(n) time. So in our case, it still takes 2^(m/2) time to search through all outputs.

However, for some tasks, the quantum machine provides exponential speedups. Prime factoring is one example (see Shor's algorithm on wikipedia or anywhere else).

Finally, a quantum computer does NOT solve an NP-complete problem in polynomial time (at least, no one found a way to do it yet), despite what some news reports might say.

Answer 3

The essential difference between a quantum computer and a regular computer is that a quantum computer actually relies on quantum physics to function. In particular, the part of quantum physics it relies upon is superposition of states. In regular computers, a single bit in a single register can hold exactly one value, either a zero or a one. In a quantum computer, the key part of the computer is a register made up of qubits, literally quantum bits than can hold a zero and a one at the same time.

If you're interested in the basic physics involved, find some material on quantum mechanics in general, and on the subject of "Schrodinger's cat" in particular. Basically, by using registers made up of qubits you can actually store many values at once and when that register is used in computations you can actually perform many computations at once. Some of the most promising application areas for quantum computing include searching and pattern recognition, Where a traditional computer would have to retry candidate solutions in series. A quantum computer can arrange the computation so that many solutions are superposed probabilistically as different quantum states in the same physical register and try them all in a single iteration.

If you're curious about how one writes programs for a quantum computer check out Shor's algorithm for factoring numbers, which was actually demonstrated in 2001.