[Feature Request] Speed up simulation by removing patches that are not on the lattice from the state vector

[gwwatkin]

Issue Description

Simulation is a critical bottleneck right now and it is because of simulating useless patches.

Right now simulation of longer circuits happens at a much slower speed because every patch that is ever on the lattice contributes to one big state vector. In particular state vector size grows exponentially with y-depth and t-depth, because each of these operations is associated with an new patch that contributes an extra qubit in the logical lattice computation, doubling it's size.

Even these patches aren't contributing to the computation for nearly the whole length of the computation. This makes simulating circuits of just a couple lines infeasible without y operator removal.

Addressing this issue will greatly expand the set of circuits we can test.

Proposed Solution

Here are some possible solutions:

• Exclude patches not on the lattice from the state vector
  • Might be the easiest to implement
• Break the global state into smaller vectors based on separability
  • We already have a separability algorithm
  • Can cache what was not entangled from previous operations
  • Speeds up all not entangled computations (E.g. different modules running in parallel)
• Leverage an existing simulator to simulate one operation at a time

[alexnguyenn]

@isolatedinformation I think your opinion would be helpful here

[isolatedinformation]

• Excluding Patches If I understand what you mean correctly, I think we would run into problems similar to ops.pop(). If only the correctness of the smaller statevector, this would be alright I think.

• Seperability and Caching

  1. Do you mean, there is already a separability algorithm implemented in the package, or do we know which algorithm to implement?
  2. I like the idea of caching better. Because we are not really getting rid of the state vector. Just caring about the parts we need.
  3. The only disadvantage I see, if it turns out the state vector is not seperable we would not get any speedup
  4. This would also be more scalable, imo.

• External Simulators This choice depends more on how we want to depend on existing simulators. I remember @alexnguyenn he wants to reduce the dependency on Qiskit. Relying on other simulators would prevent us from reinventing the wheel again.