Software simulation of a quantum computer

0 votes
asked Jan 4, 2011 by geog

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.

8 Answers

0 votes
answered Jan 4, 2011 by clinton-pierce

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.

0 votes
answered Jan 4, 2011 by codesinchaos

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.

0 votes
answered Jan 1, 2013 by wybiral

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.

0 votes
answered Jan 16, 2014 by sigrlami

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.

0 votes
answered Jan 27, 2014 by charles-chow

My answer is yes:

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:

1.Quantum annealing

2.Simulated annealing

3.Optimization by simulated annealing: Quantitative studies

0 votes
answered Jan 27, 2014 by aayush-rohatgi

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.

0 votes
answered Jan 22, 2016 by hans-stricker

Another reason why classical simulation of quantum computation is hard: to keep track you may want to know after each action of a n-qubit gate (n>1) whether the outgoing qubits are entangled or not. This must be calculated classically but is known to be NP-hard.

See here: https://stackoverflow.com/a/23327816/363429

0 votes
answered Jan 22, 2016 by hans-stricker

Yet another reason why classical simulation of quantum computing is hard: you need almost perfect - i.e. as perfect as possible - random number generators to simulate measurement.

Welcome to Q&A, where you can ask questions and receive answers from other members of the community.
Website Online Counter

...