35
$\begingroup$

I'm currently reading a book (and a lot of wikipedia) about quantum physics and I've yet to understand how a quantum computer can be faster than the computers we have today.

How can a quantum computer solve a problem in sub-exponential time that a classic computer can only solve in exponential time?

$\endgroup$
34
$\begingroup$

A quantum computer by itself isn't faster. Instead, it has a different model of computation. In this model, there are algorithms for certain (not all!) problems, which are asymptotically faster than the fastest possible (or fastest known, for some problems) classical algorithms.

I recommend reading The Limits of Quantum by Scott Aaronson: it's a short popular article explaining just what we can expect from quantum computers.

$\endgroup$
  • 3
    $\begingroup$ What do you mean by: "A quantum computer by itself isn't faster.", especially just before saying that, with the right algorithms, this model can solve some problems asymptotycally faster that classical models (and of course always at least as fast)? Or are you just saying that computational speed is a property of an algorithm, not of a computational model. But then I would think the concept can be extended to computational models. Or is there a reason why this is not possible. $\endgroup$ – babou Mar 14 '16 at 21:41
16
$\begingroup$

The basic idea is that quantum devices can be in several states at the same time. Typically, a particle can have its spin up and down at the same time. This is called superposition. If you combine n particle, you can have something that can superpose $2^n$ states. Then, if you manage to extend, say, bolean operations to superposed states (or superposed symbols) you can do several computations at the same time. This has constraints but can speed up some algorithms. One major physical problem is that it is harder to maintain superposition on larger systems.

$\endgroup$
6
$\begingroup$

its an open problem subject to cutting edge research whether quantum algorithms will ever be faster than "classical" algorithms both on the theoretical and applied levels. in complexity theory it is reflected in the question eg BQP =? P ie whether quantum computing "P" class is equivalent or not to the classical P (Polynomial time) class & there are many other related open questions.

there is one very intriguing & significant datapoint: the award-winning Shors algorithm factors numbers in P quantum time, but it is still not known whether there exists a P-time classical factoring algorithm.

a new direction over last few years is work in adiabatic quantum computing which is easier to implement/engineer than other standard methods involving qbit transport (but yet still extremely difficult to implement).

the only quantum computer(s) ever built to date is by Dwave systems and is currently subject to intense scientific scrutiny and controversy regarding its actual quantum effects & performance; it is very expensive and basically does not outperform a desktop computer, when the classical code is fully (human-/hand-) optimized. however it can be fairly stated no other corporate, government, or university research entities appear to be anywhere close to their level of applied/technical/engineering advancement so far.

the scientific outlook is cloudy at the moment & some scientific experts/critics/skeptics eg Dyakonov have long believed/argue strongly that scalable QM computers will never materialize due to insurmountable technical difficulties and/or barriers.

$\endgroup$
1
$\begingroup$

Ive got a proof that says that even quantum power has its limits.

Quantum Computers find it very difficult even to get to a kilobit of qbits. But even if they only get there, it is quite powerful.

16384 qbits would make 128 space dimensions by 128 time steps, full exhaustive search, thats amazing, 100 time step 100 dimension probability tree!!! but dont expect more than that amount for quantum in the near future.

$\endgroup$
  • 1
    $\begingroup$ This seems more a comment than an answer. $\endgroup$ – xskxzr Aug 21 at 19:32
  • $\begingroup$ How this answers the stated question? It got limits, ok, but the question was about sub-exponential time. $\endgroup$ – Evil Aug 22 at 2:20
-1
$\begingroup$

Think of it this way: There are problems that can be solved by solving a whole lot of individual sub-cases [example: factoring by trial division]. These problems take a long time to solve if one has to solve the sub-cases one after another. They can be solved much faster if one can provide enough hardware to solve all of the sub-cases in parallel, but that is not practical because the amount of hardware needed increases with the problem size. Quantum computing exploits the superposition-of-states feature of Quantum Mechanics to simulate providing enough hardware - i.e each state in the superposition is 'the machine' for one of the sub-cases. Note that this simulation is done NOT by software, but by Nature itself.

$\endgroup$
  • 3
    $\begingroup$ Quantum computation is not the same as running exhaustive search in parallel. It's a bit more complicated than that. $\endgroup$ – Yuval Filmus Dec 18 '16 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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