Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm currently reading a book (and alot of wikipedia) about quantum physics and I'm yet to understand how is a quantum computer can be faster than the computers we have today? what causes the possibility of a quantum computer to solve a problem of exponential time in sub-exp time?

share|cite|improve this question
I found this video from Veritasium, with help from A/Prof Andrea Morello be extremely helpful in explaining this. After explaining how quantum computing works, he gives a good explanation on why quantum computing will never replace modern computing and in what cases quantum computing is slower/faster. – Gunnar Feb 17 '14 at 17:05
what book? plz cite it. see also how to measure processing power of a qm cpu – vzn Feb 18 '14 at 18:12
up vote 19 down vote accepted

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.

share|cite|improve this answer
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. – babou Mar 14 at 21:41

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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