[Solved]: What specifically makes quantum computers useful?

Problem Detail: 

I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic.

That seems to be what people point to as being what makes quantum computers special or useful.

However after you have processed the superpositional inputs, you have a superpositional result, of which you can only ask a single question and it collapses into a single value. I also know that it isn't (currently?) possible to clone the superpositional state, so you are stuck with getting an answer to that one question.

In both cases, it looks like that multi processing ability really hasn't gotten you anything since it's effectively as if only one state was processed.

Am i misinterpreting things, or does the real usefulness of quantum computing come from something else?

Can anyone explain what that something else is?

Asked By : Alan Wolfe

Answered By : Craig Gidney

Destructive interference is the primary thing that makes quantum computers more powerful. In a classical probabilistic computation, having two paths to an output always makes that outcome more likely. In a quantum computer, it can make the outcome less likely.

Quantum algorithms are carefully designed so that wrong answers tend to be destructively interfered, leaving only the desired solutions as measurement outcomes. This is tricky to do, and not every problem allows for it. Grover's Search Algorithm is an excellent example of this effect, so here's a beginner-level post about Grover's algorithm.

Other useful properties quantum computers have access to:

• Entanglement for coordination and communication improvements (e.g. symmetry breaking, superdense coding, beating bell tests).
• The uncertainty principle for cryptography (e.g. quantum key distribution, Einstein-certified random numbers).
• Manipulating actual physical states to implement quantum sensors and other lab equipment (who wouldn't want a counterfactual bomb tester?).

(Scott Aaronson likes to say everything interesting about quantum is due to superpositions preserving the 2-norm instead of the 1-norm like probability distributions do. All the more specific useful effects I mentioned do derive from the underlying math.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48045