[cohomologo]

Could you help us understand what the limiting factor in these simulations are?

By memory considerations alone, a N-qubit wavefunction (using 64-bit floats) uses 2^(N+4) bytes, and a N-qubit unitary operator uses 2^(2N+4) bytes. If you use 1 GB of RAM, that allows you to store full unitary operators up to 13 qubits.

If you use sparse operators to store the gates (which have a size in memory that is a constant times the wavefunction size) you can imagine doing 24 qubits.

Of course fighting exponential scaling is always hard, but I'm not sure if I understand why the limit (for a hobby-level project) is closer to 10 than 24.

[Strilanc]

Quirk was hitting a limit before 10 due to time costs, not space costs. Avoiding the matrices also saves you a lot of time because you can apply M 2-qubit gates to N qubits in O(M 2^N) time. Usually M is much smaller than 2^N (e.g. for the Fourier transform M is O(N^2)), so this is huge savings over the naive matrix multiplication.

(Also keep in mind that Quirk's nature applies a lot of time pressure. It animates and reacts as you drag circuit elements around, so I only have ~100ms to simulate a whole circuit from start to finish and draw the results before the experience starts to really suck. Having minutes or hours instead of centiseconds is a big help when it comes to having more qubits.)

Another side note: there are ways to simulate millions of qubits using a GiB of RAM. BQP is in PSPACE. The problem is it requires doing the equivalent of path integrals, and there will be lots and lots and lots of paths. All of the space costs get turned into time costs that are exponential in the number of operations... so not actually viable for more than a handful of extra qubits.

[cohomologo]

Cool, thanks for the info. I enjoyed playing with Quirk, it's very nice.