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

Quantum computers and modelling a quantum computer on a classical computer

  1. Oct 30, 2011 #1
    First of all, I haven't the slightest idea how a quantum computer actually works but I understand that it is theoretically possible to make them and they could, in theory, be used to compute things that a classical computer would take too long to compute. (i.e. large combinatorial problems like cracking some code).

    So if this quantum computer exists, and you give it some initial input which represents instructions to solve some massive combinatorial problem that classical computers cannot solve (in a reasonable time), then in this situation you would not be able to model the system (the quantum computer) with a classical computer (i.e. a turing machine) in a reasonable way because if you did then you would solve the combinatorial problem which you can't solve on classical computers!

    My question is: Can classical computers be used to model quantum physics accurately (in a reasonable time)? Or is a quantum computer just a weird case that computers can't be used to model? And I may be jumping ahead of myself here, but presuming classical computers can't model quantum phenomena, could a quantum computer model quantum phenomena?

    I'm reading Roger Penrose's book "The Emperor's new Mind", this is what lead me to ask this question.

    Thanks a lot :)

    I notice the ambiguities of "reasonable time" and "in a reasonable way". I would guess a proper way of asking this questions would involve Big O notation but I'm not experienced enough in maths/physics/computation theory to phrase my question in that way.
    Last edited: Oct 30, 2011
  2. jcsd
  3. Oct 30, 2011 #2

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    Just imagine trying to model, accurately, a modern laptop on the first IBM mainframe.
    Now what was your question?
  4. Oct 30, 2011 #3
    Okay, that's made me think a bit more about my original question. I don't think I really know what I'm asking without a better understanding of how a quantum computer might work, or how quantum mechanics might be modelled by a classic computer.

    So what you're suggesting is that basic quantum phenomena can be modelled with a classical computer but complex systems (like a quantum computer) are just too complex to be modelled.

    I guess the maths/knowledge of QM does exists to model that hypothetical quantum computer, and it's just a case of a lack of computational power. Is this kind of computational problem (modelling quantum phenomena) one in which a quantum computer could do much better than a classical one? (this was my second question).
  5. Oct 30, 2011 #4
    No, they cannot, by the very definition of the term "reasonable time".

    Classical computers cannot solve certain problems in reasonable time.
    Quantum computers can solve some of these problems in reasonable time.

    Therefore, a classical computer cannot emulate a quantum computer in reasonable time, since the emulation would be required to solve in reasonable time some problems outside of the domain possible for classical computers.

    Strictly speaking, the classical computers have bounded number of CPUs and thus can solve problems from the class P in polynomial time.
    There is a mathematical model of a computer with unbounded number of independent CPUs (nondeterministic Turing machine) and it is able to solve problems from the class NP in polynomial time.

    Quantum computers are quite in the middle. When qubits are in quantum superposition of few states, it could be said that some computation is done on each of this states in parallel. This resembles the NTM, but in quantum computers CPUs are not completely independent. States mix with each other and interfere with other term computations. Moreover, the number of CPUs is not unbounded. It is in fact dependent on how long we can sustain quantum entanglement and how big it is. If we could make an infinitely big entangled state for infinite period of time, then the number of CPUs would be infinite.

    We don't know yet what is the exact complexity class of quantum computers, but it is almost certainly bigger than P and lesser than NP.

    It simply exploits some quantum phenomenons that usual computers don't. From a programmer point of view, you would have some functions operating on vectors that would compute very fast, in a unit time. To be more precise: you can do a Fourier transform on a vector of numbers, perform some function on it and reverse-transform it back. The Fourier transforms in quantum computers cost nothing.
  6. Oct 30, 2011 #5

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    I'm saying - you can get accurate, complete, or fast - pick two.

    A simple quantum computer could be modelled in a regular computer ... technically they are doing it, functionally, right now: oh look!

    If you want to model the QM processes that would lead to the components of a quantum computer - again, fine. Provided you keep it simple. It is models like these that lead us to think that quantum computers are possible in the first place and it's probably how we'll design the first ones.

    We don't normally think of using a very small quantum computer as a pocket calculator[1], just like we don't use our ultra-miniaturization to make smaller 8086 processors - so we'd think of quantum computers in terms of their promise. Very big, very fast.

    It will help refine your question if you consider where your line of reasoning was going.

    [1] Mind you, we never thought that the processing power we have now would be used to post pictures of cats at each other either.
  7. Oct 30, 2011 #6
    My line of reasoning was this:

    You can't model a quantum computer that can solve large combinatorial problems on a classical computer in reasonable time. Or else you've just solved the combinatorial problem in reasonable time.
    Therefore there's something about this system, and the quantum phenomena being taken advantage of, that can't be modelled in reasonable time. My next line of reasoning was less clear, hence asking the question.
    I presumed the reason that this system couldn't be modelled, would also mean that no quantum system would be able to be modelled effectively because any quantum system would be subject to the same rules that made the quantum computer not modellable.

    The questions were, Is this conclusion correct? Or is the quantum computer a special case in some way? If the conclusion is correct, could a quantum computer theoretically model a quantum system in reasonable time?
  8. Oct 30, 2011 #7
    I'm no expert. but my impression is this.

    A quantum computer is capable of massively parallel computation. You can in effect get a quadrillion or more computers each calculating a different solution to your problem. You can see how for certain things like factoring prime numbers and simulation of quantum systems this would be a huge improvement. So yes, you could simulate that with an ordinary computer, but it would take a quadrillion times as much time.

    On the other hand, with many problems parallel computation doesn't help you, so it won't solve all of your problems.
    Last edited: Oct 30, 2011
  9. Oct 30, 2011 #8

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    OK - it's more abstract than I thought.
    You want to know if there is anything intrinsic about the way a quantum computer carries out it's calculations that a classical computer cannot do - in principle.

    So - given a quantum computer, would it be possible (in principle) to build a classical computer that could do the same calculations?

    Answer - depends. Turn the question around: would it be possible, in principle, to build a quantum computer so complex that there are not enough atoms in the Universe to build the classical computer that would do the same thing?

    The answer is, in principle, yes. Clearly, since the quantum components are so much smaller than the classical ones.

    It's not something intrinsic to quantum computing itself, just the scale and complexity at which quantum mechanics happens. Just like it is technically possible to build a microprocessor-based computer which is too complex for a valve-based computer to model ... and you can easily build an electronic computer that cannot be modelled as a series of operations on a slide-rule or an abacus.

    Quantum processes can be and are modeled on computers.

    The question of whether we can model the universe to the quantum scale in a computer (of any kind) smaller than the Universe itself is a subject of some debate. To do this would be to discover a grand-unified theory of everything.

    That seems to be the question you are approaching - the short answer is: we don't know.
  10. Oct 31, 2011 #9
    There obviously IS something about a quantum computer that classical computers cannot do in a reasonable time. Otherwise quantum computers would be useless, even in theory. Also don't think I'm talking about what can be computed given infinite time: I understand that given infinite time a classical computer can't do anything less than a quantum one.
    This is what I don't understand, I am not doubting that quantum processes are modelled accurately with classical computers. My understanding is that it is only with classical computers that any of the modern accurate predictions of quantum theory are calculated.

    Can you model every property of a simple quantum mechanical system over time, in reasonable time, on a classical computer? If you can then why is a quantum computer a special case that you can't model in reasonable time, and if you can't then that's interesting and my question is answered and my original conclusion was correct :).

    I seemed to get a very direct answer for this question from haael when he answered:
  11. Oct 31, 2011 #10
    I believe the answer is that a quantum computer can be simulated by a classical computer with polynomial resources and exponential time. The time isn't infinite but still I wouldn't consider it to be reasonable (it could be the life time of universe if you pick the right problem to compare them with).
  12. Nov 1, 2011 #11

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    <sigh> Quantum computers are likely to be more useful that classical computers for the same reason your laptop is more useful than an abacus.

    Haael was probably making an assumption about what is meant by "quantum computer" which is likely the same on that you are making.

    A computer, however it works, can be made very simple if you want. A quantum computer does not have to be hugely complicated. Therefore, it is possible to build a quantum computer that is simple enough to model on your laptop.

    Why anyone would want to do this is a different question. Perhaps it would be a work of art? Though - your laptop simulation would be slower. Right now our computers are hugely powerful but we don't actually use that power much so someone may very well build a simple quantum computer just run run a powerpoint presentation. This is besides the point.

    However - it is, in principle (it's not been done), possible to make a quantum computer that your laptop cannot model "in a reasonable time". In order to design them, we'd probably have to model them on simpler quantum computers.

    The question you seem to be asking is if it is possible to build a quantum computer which cannot, even in principle, be modelled by any classical computer, no matter how good they ever got. And the answer is yes - there are built-in limits to the scale of a classical computer: it has to operate on a scale that is large compared to the quantum domain (by definition of "classical").

    The philosophical limit would be a quantum computer just complex enough that the classical computer needed to do the same job would either take up all the available matter in the Universe or use up all the available time to run it. The practical limit would be hit long before then.

    But that's like noting that there are built in limits to the scale of an abacus that mean you cannot model your laptop on one.
  13. Nov 1, 2011 #12
    Okay cool. I think we can leave this discussion, thanks for the help everyone :)
  14. Nov 1, 2011 #13

    Physics Monkey

    User Avatar
    Science Advisor
    Homework Helper

    I would argue that this a bad analogy. Quantum computers are qualitatively different from classical computers, but a laptop is only quantitatively different from an abacus.

    The difference between these two cases is roughly exponential versus polynomial. One language used to discuss these questions is asymptotic worst case complexity. This means we ask how the resources needed to solve the worst case of a problem scale with the size of the problem.

    For example, we may ask how long it takes to factor numbers in the worst case as a function of n, the number of digits. More digits should take longer, but the important question is how much longer.

    It is widely believed that factoring takes a superpolynomial (faster than any polynomial) amount of time as function of n for a classical computer, but a quantum computer can do it in a time polynomial in n. Thus there is believed to be a qualitative distinction between the class of things a classical computer can do in polynomial time and the class of things a quantum computer can do in polynomial time. This polynomial time distinction is useful because it abstracts away the details of hardware and implementation but seems to retain the core distinction between "hard" and "easy" problems.

    As a note, nothing in this distinction implies that for a given problem instance we cannot do quantum things with a classical computer. Indeed, given sufficient resources we can always simulate a quantum computer using a classical computer. The question of whether this simulation is feasible depends on the details of the problem being considered, the resources available, the particular computational scheme, etc. Certainly it is true that we cannot use more resources than are available in the whole universe, but that is a different question from the formal complexity considerations that distinguish classical and quantum computers. Nevertheless, there are already simple problems that no classical computer will ever solve but which a quantum computer could tackle easily (e.g. simulation of larger quantum systems).

    I would also note that some classical simulations of quantum systems, while requiring exponentially more resources, also provide exponentially more information at the end of the computation. A quantum computer does not automatically give one direct access to all the amplitudes of the computer's wavefunction. However, a simpleminded classical simulation that simply stores and evolves the full wavefunction would have access to this information. So the sense in which quantum computers are exponentially better than classical computers is a subtle one.
  15. Nov 1, 2011 #14

    Simon Bridge

    User Avatar
    Science Advisor
    Homework Helper

    Abacus' scale polynomial - by area iirc (number of beads you can fit on your frame). There was a Dr Who story that featured an entire planet's population acting as components in a supercomputer. This should be quite powerful since it is parallel-AIs so should be able to solve pretty unique problems ... though it is badly hamstrung by the bus speeds (they used sneakernet). For turing-type computing though, we could probably build a digital computer that is more efficient.

    Digital computers are famously exponential - for a long time, the number of transistors that could fit on a microcircuit was doubling every two years (Moore's Law). Digital computers are different from physical computers. This is starting to slow - but still exponential - until we hit QM limits.

    New technology usually has an exponential development phase after a linear one, then it tops out. Quantum computers should also be like this, though the first ones are likely to be quite simple - like the first digital computers: analog computers easily outstripped them.

    All analogies are flawed though. And it does not affect the reply.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook