Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why are quantum computers faster than classical computers?

  1. Jun 30, 2015 #1
    I was recently reading about quantum computers because I once asked a teacher with more experience in the field "What was the origin of the quantum speedup" with his answer being quantum parallelism, which I kinda understood at that time, but I forgot about it. So, the other day I was thinking about it and I decided to study it again after seeing a presentation (about quantum contextuality in which the lecturer said that quantum contextuality could be an essential tool to explain why quantum computers worked) and the following article:

    Contextuality supplies the ‘magic’ for quantum computation
    Mark Howard, Joel Wallman, Victor Veitch & Joseph Emerson
    1 9 J U N E 2 0 1 4 | VO L 5 1 0 | N AT U R E | 3 5 1
    (yeah I copypasted, but I'm lazy to make it easier for others to find the article... sorry about that...)

    So, now I was not only embarassed myself, but I was "embarassed for the people in the field". For myself because I couldn't remember what was quantum parallelism (which I promptly read about again)... But for the field because I'm not really sure we know why quantum computers are (believed to be generally) faster than classical computers...

    Here are some references (within the article above) that shed some light over the matter. I don't know if contextuality solves the problem, because I couldn't read all the article arguments still - but I'd really appreciate if somebody could give me a clearer exposition.

    PHYSICAL REVIEW A 88, 022307 (2013)
    Discord and quantum computational resources
    Aharon Brodutch

    Found Phys (2010) 40: 1141–1154
    DOI 10.1007/s10701-010-9452-0
    The Elusive Source of Quantum Speedup
    Vlatko Vedral

    PRL 110, 060504 (2013)
    Universal Quantum Computation with Little Entanglement
    Maarten Van den Nest

    There are other two interesting references...

    A quantum computer only needs one universe
    A. M. Steane
    arXiv:quant-ph/0003084

    PRL 102, 190501 (2009)
    Most Quantum States Are Too Entangled To Be Useful As Computational Resources
    D. Gross, S.T. Flammia, and J. Eisert

    Why are quantum computers faster than classical computers? Is this a good question?

    (I might also add that I still do not feel like I do get what contextuality mean in its whole and that I'm not embarassed for being ignorant, as I'm ignorant about a whole lot of stuff, but more embarassed because to me it seemed to be the premise of why we wanted to research this in the first place, and it seems we were talking bs about it)
     
  2. jcsd
  3. Jun 30, 2015 #2

    phinds

    User Avatar
    Gold Member
    2016 Award

    They are not, in all cases. For some algorithms they are slower than classical computers, for some they are much faster, so as a blanket statement, it's not correct to say they are faster. Surely the articles you quoted must go into that.
     
  4. Jun 30, 2015 #3
    Could you give me a reference stating exactly this, because to me this seems to say that quantum computers can't always simulate classical computers efficiently, and I took that for granted.
     
  5. Jun 30, 2015 #4

    phinds

    User Avatar
    Gold Member
    2016 Award

    Then it seems we are saying the same thing. I have no references. I'm re-stating what I've seen on this forum several times and which I have read in weekly magazines.
     
  6. Jun 30, 2015 #5
    The point of the quantum computer is that if one looks how to compute the quantum probabilities one has to compute a path integral. To compute this path integral on a classical computer one would need a lot of time - it is an integral over all possible paths.

    The first idea is that, if one has to compute such a path integral, one could, instead of doing it on a classical computer, which would need a lot of ressources, simply using the real world as an analog computer. All one needs for this is a real experiment with a real device which, according to quantum theory, gives the same result as the path integral which we want to compute. In this case, Nature simply "computes" its own path integral microscopically and the result is what QT predicts - the path integral. And now the designer has to modify this construction, in such a way, that we can use the computions of the QT path integrals to compute something useful for us.

    For many operations this will give nothing new - a classical computer can be understood as doing the similar thing in classical mechanics. So one would expect some improvement only for such special problems which are somehow similar to path integrals.
     
  7. Jun 30, 2015 #6
    Quantum computers are slower than classical computers. It's one of the biggest misconceptions that QM can speed up computation. Actually, QM sets the limit on the speed of computation while in Newtonian dynamics computers don't have such limit.

    First thing first, all computers are quantum. We live in a world ruled by quantum dynamics, so "classical" computers don't exist. It is only a conceptual model.

    When we say about a "classical" computers we may think of two things:
    1. Computer running by the rules of Newtonian dynamics.
    2. Computer running by the rules of quantum dynamics, but not using any qubits.

    When we think of "quantum" computer, we mean a computer with qubits. In that case:
    "Classical" computers in the sense 1 are always faster than any quantum computer.
    "Classical" computers in the sense 2 are slower than quantum computers on certain algorithms and equal on others.

    Please remember one thing: quantum mechanics sets a limit on the speed of any physical process, including computations. This limit is similar to the Bekenstein bound. While the Bekenstein bound sets the maximal space resolution, there is also a maximal time resolution of the universe.
     
  8. Jun 30, 2015 #7

    phinds

    User Avatar
    Gold Member
    2016 Award

    haael, your post directly contradicts experimental results where quantum computers are faster than classical computers for some algorithms. I suggest you Google "quantum computer experimental results"
     
  9. Jun 30, 2015 #8

    JK423

    User Avatar
    Gold Member

    Short answer: nobody knows yet!
    It's a really interesting question. People are trying to find what the minimal quantum resources are (like; entanglement, contextuality, discord, etc) such that the quantum algorithm will still give advantage over classical computing.
    The usual algorithms, like the famous one of Shor etc, use pure entangled quantum states for the computation. Then you might say; "Ah! Entanglement is responsible for the speed up!". Not really though. The fact that you built a fast quantum computer with lots of entanglement doesn't mean that you cannot create a fast quantum computer with very little or no entanglement. So the problem becomes; What are the minimal quantum resources that i can have in a quantum computer that would still allow for an advantage (polynomial or exponential) over classical computing? This is still a very interesting open question.
     
    Last edited: Jun 30, 2015
  10. Jun 30, 2015 #9

    JK423

    User Avatar
    Gold Member

    Maybe you should change your notion of 'classical' computer, and your problem is solved. Classical computers, defined as computers that do not take advantage of genuine quantum effects in the computation, are still constrained by the laws of physics when it comes to how fast a computation can be implemented. Taking this into account, it's straightforward to conclude that the speed of classical processes is always smaller than the speed of quantum processes, since the former is created from the latter in the microphysics involved. Therefore, the speed of computation in a quantum computer is -in principle- larger or equal to any classical computation (/process).
     
  11. Jun 30, 2015 #10
    Haael is technically right. To add to JK423's clarification, we can modify Haael's definition 1 of classical computers a little bit:

    Classical computers are computer running by the rules of Newtonian dynamics when it applies.

    There are various formulation of computation that we might think of as "classical," based on classical mechanics but e.g. assumes we can manipulate real numbers to infinite precision. Such machines can be faster than quantum computers or any computer that we may hope to build. Mathematically, classical mechanics doesn't forbid this, but physically this implies going into the domain where classical mechanics is not correct anymore. Hence this is not what scientists think when they say "classical computers."
     
  12. Jun 30, 2015 #11
    This is a bit subtle. Quantum computers can always simulate classical computers efficiently. How? Just restrict the computation to one basis only. So when people say quantum computers are slower, I expect that they are comparing different problems. For example, Scott Aaronson has written a very nice article (published in Nature Physics) exposing this point that often got lost in the translation in the news in the case of the quantum algorithm to "solve" linear equations.
     
    Last edited: Jun 30, 2015
  13. Jun 30, 2015 #12
    Quantum computing is only 'faster' than convention computing for resolving problems that require parallel computation of a large number of variables.
    A good example would be calculating orbits in multiple body systems.
    Most everyday computing needs, such as reading a website, accessing a database, printing a document, etc are simple linear routines, and for those a conventional cpu is as good, and maybe better.
    If Qubits became cheap enough Q computers might be useful for applications such as air traffic control.
    Anything remotely capable of being an 'AI' in the sci-fi sense would probably need quantum computing.
     
    Last edited: Jun 30, 2015
  14. Jun 30, 2015 #13
    It's worth noting that there are types of computational parallelisation that quantum computers are not more suitable for. For example, the screen you're looking at now, is rendered by a highly parallelised graphics card. A quantum computer wouldn't be suitable for this at all. I'd phrase it differently and say that quantum computers are well suited to optimisation problems, rather than parallelisation.
     
  15. Jun 30, 2015 #14
    Actually when I typed "can't" i meant "can". Sorry about that.

    But if there are no references, then I don't think I clearly know what you mean.

    Even still, this post is giving me some good ideas, even if some people are getting my question differently from what I wanted to know (JK423 got what I wanted to know almost exactly) - I thought my question was clear, maybe the fact that I HAVE to give a summarized question is what makes it a little less precise than I imagined.

    I intend summarizing people's opinions (and 'understandings') later. I think asking imprecise questions maybe leads to better (or more complete) answers :).
     
  16. Jun 30, 2015 #15

    cgk

    User Avatar
    Science Advisor

    People also tend to forget about the No Cloning Theorem (google it). Its consequence is that almost all(!) of the algorithms we know from "algorithms & data structures" are not applicable in quantum computation, because even the simplest algorithm "a := b" (i.e., copying the value of one variable into another variable) does not work on such machines.

    There are efficient quantum algorithms for factoring numbers (look up Shor's algorithm), which have the potential of invalidating the foundations of current asymmetric cryptographic algorithms (which is where the majority of the interest stems from---i.e., if real efficient quantum become a reality, cryptographic key exchange will become much more annoying). Will quantum computers actually be useful for anything else? That remains to be seen. It is not even clear if they would be more efficient (than classical computers) for the simulation of actual quantum systems.
     
  17. Jul 1, 2015 #16
    It might not be clear, but quantum simulation is a very active field of research. In fact, people in the field are touching some very cool physics, even if it is just in simulation... Even for phenomena for which we do not have experimental implementations done. I could give some examples upon request - but I won't because there are lots of them.
     
  18. Jul 1, 2015 #17

    phinds

    User Avatar
    Gold Member
    2016 Award

    I didn't say there are no references, I said *I* don't have any at hand, but the other threads I remember reading did have some.
     
  19. Jul 1, 2015 #18
    I don't see why not. CNOT can copy a state in the computational basis and that's enough to embed those algorithms into quantum computation.

    Could you please elaborate on that? It seems pretty clear to me that quantum systems can simulate themselves efficiently.
     
  20. Jul 1, 2015 #19

    Strilanc

    User Avatar
    Science Advisor

    Giving a succinct summary of how quantum computers are faster is hard. You can get the speedups from different subsets of quantum behavior. For example, cluster state quantum computation is based almost entirely on measurement, whereas your more typical quantum logic circuits basically don't need measurement at all.

    Ultimately, it always comes down to being able to hold and manipulate exponentially-huge superpositions without collapsing them. But that's more of a definition of a quantum computation than an explanation of why it helps. You'll probably understand better at first by reading concrete examples, like a beginner-level explanations of Grover's algorithm, than you will by trying to see the big picture.
     
  21. Jul 1, 2015 #20
    Which is why I asked it.

    ;)

    I will still learn how to put hypertext in my comments, though.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook