# Software simulation of a quantum computer

While we are waiting for our quantum computers, is it possible to write a software simulation of one? I suspect the answer is no, but hope the reasons why not will throw some light on the mystery.

Years ago I attended a talk at a Perl conference where Damian Conway (I believe) was speculating on some of this. A bit later there was a Perl module made available that did some of this stuff. Search CPAN for Quantum::Superpositions.

Implementing it isn't that hard. The problem is that the computational and memory complexity is exponential in the number of quantum bits you want to simulate.

Basically a quantum computer operates on all possible n-bit states at once. And those grow like 2^n.

The size of an operator grows even faster since it's a matrix. So it grows like (2^n)^2 = 2^(2*n) = 4^n

So I expect a good computer to be able to simulate a quantum computer up to about 20 bits, but it will be rather slow.

They do exist. Here's a browser based one. Here's one written in C++. Here's one written in Java. But, as stated by CodesInChaos, a quantum computer operates on all probability amplitudes at once. So imagine a 3 qubit quantum register, a typical state for it to be in looks like this:

a1|000> + a2|001> + a3|010> + a4|011> + a5|100> + a6|101> + a7|110>+ a8|111>

It's a superposition of all the possible combinations. What's worse is that those probability amplitudes are complex numbers. So an n-qubit register would require 2^(2*n) real numbers. So for a 32 qubit register, that's 2^(2*32) = 18446744073709551616 real numbers.

And as CodesInChaos said, the unitary matrices used to transform those states are that number squared. Their application being a dot product... They're computationally costly, to say the least.

Quipper is full blown simulation EDSL for Quantum Computing, implemented in Haskell I have experince to simulate behaviour of several QC algorithms such as Deutsch, Deutschâ€“Jozsa, Simon's, Shor's algorithms and it's very straightforward.

You can simulate the behaviours of a quantum machine by simulating the quantum machine algorithm

D-Wave quantum machine using a technique called `quantum annealing`. This algorithm could be compared to `simulated annealing` algorithm.

References:

WIKIPIDEA STATES IT : (link missing)

Given sufficient computational resources, however, a classical computer could be made to simulate any quantum algorithm; quantum computation does not violate the Churchâ€“Turing thesis.