An excellent post

What Can We Do with a Quantum Computer? - Andris Ambainis, 2014

Some excerpts

“The full description of quantum physics has so many variables that we cannot keep track of all of them on a computer. If one particle can be described by two variables, then to describe the most general state of n particles, we need 2n variables. If we have 100 particles, we need 2100 variables, which is roughly 1 with 30 zeros. This number is so big that computers will never have so much memory.”

There are several tasks for which a quantum computer will be useful.

• Encryption/Decryption
• Quantum Simulation : modeling quantum systems
• Modeling chemical reactions
• Searching huge amounts of data

All of these achievements of quantum computing are based on the same effects of quantum mechanics : Quantum parallelism and Quantum interference.

Quantum parallelism

A conventional computer processes information by encoding it into 0s and 1s. If we have a sequence of thirty 0s and 1s, it has about one billion of possible values. A classical computer can only be in one of these one billion states at the same time, or it could process them simultaneously, with one billion parallel processors.

A quantum computer can be in a quantum combination of all of those states, called superposition, performing one billion or more copies of a computation at the same time, on the same hardware. This is known as quantum parallelism.

Quantum interference

The result of this process is a quantum state that encodes the results of one billion computations. If we measured this quantum state, we would get just one of the results. All of the other 999,999,999 results would disappear.

In the non-quantum world, if there are two possible paths toward one result and each path is taken with a probability ¼, the overall probability of obtaining this result is ¼+¼= ½. Quantumly, the two paths can interfere, increasing the probability of success to 1.

Quantum algorithms combine these two effects. Quantum parallelism is used to perform a large number of computations at the same time, and quantum interference is used to combine their results into something that is both meaningful and can be measured according to the laws of quantum mechanics.