quil-lang / qvm

The high-performance and featureful Quil simulator.
Other
415 stars 57 forks source link

Allow for disjoint computations within larger programs #258

Open braised-babbage opened 4 years ago

braised-babbage commented 4 years ago

Just an idea, but as larger devices become increasingly common it might be nice to have the memory demands of the QVM depend on the number of entangled qubits rather than just the number of qubits. One option here is to add a mode or a flag to qvm app which would begins evaluation by computing the connected components of the instruction depencency graph (e.g. a NQ gate places all of its qubits in the same component), then simulates these separately, and then combines the simulation results.

So for example, with this enabled,

CNOT 0 1
CNOT 1 2
CNOT 3 4

would reduce to two separate computations on qubits {0,1,2} and {3,4}.

notmgsk commented 4 years ago

I think this was prompted by a discussion about MEASUREs on a bunch of non-computational qubits. This would solve that by seeing that each of those MEASUREs could run as a separate computation, and thus the QVM would not need to allocate a single block of memory for e.g. 32 qubits. Is that right?