Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

Would it be possible to simulate a quantum computer on a normal computer. I was thinking something like have a bunch of GPU's running a set of entangled quantum particles and then produce the results. Would this be feasible or one of those take the lifetime of the universe to run problems?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

It is definitely possible to simulate a quantum computer on a classical one, but as you point out the real question is whether it can be done efficiently.

The calculations a quantum computer is doing are not fancy mathematics: it is all linear algebra in terms of unitary evolution and projective measurement of a finite-dimensional quantum system. However, if you have $n$ qubits the dimension of the state space rises as $2^n$ so that you very soon have unmanageably large matrices, and even efficient linear algebraic algorithms (in terms of matrix size) become exponentially-scaling ones.

There are a number of known quantum-computational algorithms that can be efficiently simulated with a classical computer (take for example the Gottesman-Knill theorem) and it is an ongoing research area as to which calculations can and cannot be thus simulated. If (as appears to be the case) factoring cannot be efficiently done on a classical computer, then Shor's algorithm is an example of the latter.

share|improve this answer
    
Thanks, and thanks for the references - some reading –  daven11 Jun 1 '12 at 3:31
add comment

Your Answer

 
discard

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.