Quantum computers and modelling a quantum computer on a classical computer

[Georgepowell]

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 :)

note:
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.

 

[Simon Bridge]

Just imagine trying to model, accurately, a modern laptop on the first IBM mainframe.
Now what was your question?

 

[Georgepowell]

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 modeled by a classic computer.

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

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

 

[haael]

My question is: Can classical computers be used to model quantum physics accurately (in a reasonable time)?

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.

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.

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.

 

[Simon Bridge]

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

A simple quantum computer could be modeled 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.

 

[Georgepowell]

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

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 modeled 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 modeled, would also mean that no quantum system would be able to be modeled 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?

 

[PatrickPowers]

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.

 

[Simon Bridge]

Therefore there's something about this system, and the quantum phenomena being taken advantage of, that can't be modeled in reasonable time.

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 modeled 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.

 

[Georgepowell]

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.

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.

Quantum processes can be and are modeled on computers.

This is what I don't understand, I am not doubting that quantum processes are modeled 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:

No, they cannot, by the very definition of the term "reasonable time".

 

[Joseph14]

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

 

[Simon Bridge]

<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 modeled 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.

 

[Georgepowell]

Okay cool. I think we can leave this discussion, thanks for the help everyone :)

 

[Physics Monkey]

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

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.

 

[Simon Bridge]

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.