[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.