Software simulation of a quantum computer

Question

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.

Ober

Maybe this is the solution to your problem tph.tuwien.ac.at/~oemer/qcl.html – Constancy

If you're still searching for it, one such simulator made by google engineers the news recently : qcplayground.withgoogle.com/#/home Quantiki also maintains a list quantiki.org/wiki/List_of_QC_simulators – Gilley

Google's simulator uses the GPU to perform the computations (and, of course, to display the results). Pretty neat for a web app IMHO :) – Cerussite

Simulating quantum computer using classical hardware are now available infact for free on the cloud ( I assume at the time of asking this question 8 years ago, they were not ). I can vouch for [IBMQ Aer][1] . Although if you are looking for an image that could be deployed on ec2 or on your own system , there is none available yet in my knowledge [1]: ibm.com/quantum-computing/technology/simulator – Raila

Answer 1

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.

Laissezfaire

Answer 2

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.

Reiner

Answer 3

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

Lane

Answer 4

As Wikipedia state:

A classical computer could in principle (with exponential resources) simulate a quantum algorithm, as quantum computation does not violate the Church–Turing thesis.

Titania

Answer 5

There is a very big list of languages, frameworks and simulators. Some simulate at low level the quantum equations, other just the gates.

• Microsoft Quantum Development Kit (Q#)
• Microsoft LIQUi>IBM Quantum Experience
• Rigetti Forest
• ProjectQ
• QuTiP
• OpenFermion
• Qbsolv
• ScaffCC
• Quantum Computing Playground (Google)
• Raytheon BBN
• Quirk
• Forest

It would be great to know your opinions on their capabilities and easiness of use.

https://quantumcomputingreport.com/resources/tools/ https://github.com/topics/quantum-computing?o=desc&s=stars

Toggle

Great summary - put together a couple examples here: x-team.com/blog/quantum-computation-python-javascript – Monotype

Answer 6

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.

Michel

Answer 7

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.

Fanciful

@SamGinrich: Your comment sounds funny, but I didn't understand it. Could you explain it? – Fanciful

@SamGinrich: What I wanted to say was: Quantum measurement brings into play pure chance. To simulate it, you need simulated "pure chance". And what simulates chance are random number generators, right? – Fanciful

@SamGinrich: I have never heard of "dimensions of white noise"? Google only finds nine hits: www.google.com/search?q="dimensions+of+white+noise". – Fanciful

White Noise is the physical term for true random. Dimension addresses the number of random bits you need as input for measurement simulation. Latter one is important, for it is expensive to get long true random strings. – Gallfly

Answer 8

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.

Jamajamaal

Answer 9

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://mcmap.net/q/500522/-factoring-a-quantum-state

Fanciful