18
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Some tasks can be solved faster using quantum computers. See some pointers in cs.stackexchange.com/a/751/157 $\endgroup$
    – Ran G.
    Oct 9, 2015 at 0:41
  • $\begingroup$ 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 (: $\endgroup$
    – Alan Wolfe
    Oct 9, 2015 at 0:51
  • 4
    $\begingroup$ 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. $\endgroup$
    – Ran G.
    Oct 9, 2015 at 2:02
  • $\begingroup$ 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? $\endgroup$
    – Alan Wolfe
    Oct 9, 2015 at 3:44
  • 1
    $\begingroup$ "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.) $\endgroup$
    – David Richerby
    Oct 10, 2015 at 11:05

3 Answers 3

Reset to default
16
$\begingroup$

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:

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

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – vzn
    Oct 16, 2015 at 15:41
5
$\begingroup$

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:

  1. Is there a formal proof that quantum computing is or will be faster than classical computing?
  2. Quantum computer emulated by a classical system (IOP paper)
  3. First 'Quantum Computer' No Faster Than Classic PC
  4. Can quantum measurements beat classical computers?
  5. Beating a quantum computer by simulating quantum mechanics
Improve this answer
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – Alan Wolfe
    Oct 14, 2015 at 23:01
  • $\begingroup$ @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 $\endgroup$
    – Nikos M.
    Oct 14, 2015 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.