# What specifically makes quantum computers useful?

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?

• Some tasks can be solved faster using quantum computers. See some pointers in cs.stackexchange.com/a/751/157 – Ran G. Oct 9 '15 at 0:41
• Thanks for the link I'll check it out. I know that they are faster at some things but I'm trying to understand how and why if you can help with that (: – Alan Wolfe Oct 9 '15 at 0:51
• The crux of it, is interference. Scott Aaronson has written several popular essays about it; try to search them online. Also see his book "Quantum Computing Since Democritus", based on the lecture notes that can be found here. Somewhere around chapter 10 should be the place to look at, as a starting point. – Ran G. Oct 9 '15 at 2:02
• i've been reading some of this stuff and following some links. interesting! I like how Scott flat out says it's BS that quantum computers can evaluate all possibilities and find the correct answer in one step. Can I take a guess as to what interference does? Is it that it destroys (or collapses or gets rid of) possible states of the superposition that are not valid solutions? – Alan Wolfe Oct 9 '15 at 3:44
• "I also know that it isn't (currently?) possible to clone the superpositional state" The no-cloning theorem says that this is an absolute impossibility, rather than a limit of current technology. ("Absolute" in the sense that, if quantum systems really are about unitary transformations of Hilbert spaces, you cannot do it; if unitary transformations of Hilbert spaces turn out just to be approximations, then I guess maybe you can do it, after all.) – David Richerby Oct 10 '15 at 11:05

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.

(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.)

Some of your questions are open theoretical questions. There are several ways to answer your question. A general way to think about QM computing is that it harnesses spintronics ie quantum property of spin for computation. So it is a logical next step in the miniaturization of electronics/logic, and computation in general. There are theoretical limits on gate width that are being brushed up against in current fabrication technology, a consequent plateauing of Moores law and spintronics represents the "next frontier".

Spintronics represents a different computing paradigm than binary logic. So it has interesting theoretical properties worthy of exploration even without implementations. However there is a general hope in the field that QM computing is extremely scalable and that once the principles are figured out for a few qubits, the systems could be scaled to many qubits "without too much trouble". Theoretically it is shown to scale in processing complexity in a much different/more dramatic way than classical computing, ie roughly there is $2^x$ processing capability where $x$ is the number of qubits, ie exponential rise in computational capability for linear increase in qubits. This sounds almost like out of science fiction but is an apparently "real/intrinsic" property as far as anyone knows.

A key breakthrough in 1996 is Shor's algorithm, that showed factoring can be solved in "quantum polynmomial time" and it is credited as inciting major interest in quantum computing. Factoring is of course at the heart of modern cryptographic systems in the widely used RSA algorithm.

It is an open theoretical question if quantum computers can solve other major problems in "faster" time. This is known as the BPP=? BQP question.

A controversial QM computer is built by DWave which has been proven to be "useful" in solving some problems, and they have successfully demonstrated a form of quantum scaling on a "somewhat weaker" type of QM system known as adiabatic computing. It is an open question whether it can/ will ever demonstrate unequivocal speed increases, actively under research eg by Google, Nasa, Lockheed etc.

In short quantum computers are not exactly "useful" in the same sense as classical computers, that exact nature of their usefulness is being actively researched, and only limited/ experimental/prototype systems are current in existence. They are conjectured to be "at least as useful" as conventional computation upon their realization, and possibly/hopefully "more useful" in certain not-exactly-foreseeable ways.

• ps no classical algorithm is known to factor numbers in polynomial time and its a major open complexity theory problem whether it is possible, it is conjectured to be impossible and RSA security ("nearly") depends on it. – vzn Oct 16 '15 at 15:41

A rather controversial answer, but keep it in mind nevertheless.

i would say nothing makes quantum computers more useful (at least currently)!

Sure, the standard theoretical treatment of quantum mechanics into computing, with respect to a classical theoretical treatment, indeed offers new possibilities (as other answers have noted). So what is the catch here?

The catch is this: It is not certain quantum computers are indeed more powerful than ordinary / classical computers (a fact related to the $P$ vs $NP$ problem as well) and that classical computers cannot simulate quantum computers. Sure "quantum theory" will tell you so. Why quotes in "quantum theory"? Because it is not quantum theory, actualy it is just a specific "interpretation of quantum theory". Hope all these are understood and clear.

Related references:

• Yeah, thanks for the answer. It's a good perspective to keep in mind. If we were able to do L2 norm computation, or superpositional computation on a computer that allowed for destructive interference, or the like, we may be able to get what we want algorithmically, without having to make a quantum computer. Good points! – Alan Wolfe Oct 14 '15 at 23:01
• @AlanWolfe, yeap, search around for "classical quantum computer" and/or "classical emulation quantum" and see what you get. Updated answer with some references to the point – Nikos M. Oct 14 '15 at 23:26