View Single Post
Oct30-11, 11:35 AM
P: 424
Quantum computers and modelling a quantum computer on a classical computer

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.