Implement SimulatesIntermediateState Cirq interface

[kevinsung]

This interface allows access to intermediate states as the circuit is simulated moment-by-moment. See https://github.com/quantumlib/Cirq/blob/720ea341b0082dc0cbbfb0142c161f01d8edca3e/cirq/sim/simulator.py#L258.

How difficult would this be?

[95-martin-orion]

As I understand it, a core part of qsim behavior is fusing gates along the time-axis into independent chunks. Simulating step by step in a single execution would require modifying that core behavior, which is likely a significant amount of effort. The alternative is to run each timestep as a separate circuit in sequence, which I suspect would impact the overall performance of the simulator.

@sergeisakov, could you offer your thoughts on this?

[sergeisakov]

In principle, this can be implemented. One doesn't need to modify qsim as it can run gates step by step without fusion. As @95-martin-orion pointed out, this will impact the overall performance of the simulator. The effort would be to implement the interface between Cirq and qsim.

[mpharrigan]

Has there been any development on this? I suspect it will enable big savings for things like XEB where we have one big circuit that we want to know the wavefunction at various steps

[mpharrigan]

on an XEB workload:

• Cirq w/intermediate is 5x faster than Cirq (simulate each truncated circuit separately)
• Speedup increases to 7x using multiprocessing on my laptop for each
• QSim simulating each truncated circuit separately is 3x faster than cirq
• But QSim simulating each truncated circuit separately is 1.75x slower than Cirq w/intermediate
• But when using multiprocessing for both the trend flips and qsim with each circuit separate is 4.5x faster than Cirq w/intermediate sorry, had my numbers transposed
• The difference expands to 4x when using multiprocessing for both

[mpharrigan]

Since we only need the results after each "cycle" (and indeed, only for certain cycle settings) it could be worthwhile to

1. improve the cirq interface to have some notion of "step by this many moments". At a minimum, this could prevent shuttling around some wavefunctions that I'm just going to discard anyways
2. tell qsim what the minimum step I'm going to request is, so it can fuse except respecting those boundaries

[sergeisakov]

I guess there's been no development on this. The core qsim library supports boundaries and can return the wavefunction at various steps. One sample C++ application (qsim_amplitudes.cc) saves intermediate results. The qsimcirq interface doesn't support that.

[95-martin-orion]

I think it would be possible to construct this with a combination of CircuitOperations and existing qsim-core methods. A rough outline for what this would look like:

1. When creating the circuit, the user condenses each "step" into a set of parallel CircuitOperations. Since CircuitOperations exist within a single moment of the outer circuit, this allows us to keep the "step moment-by-moment" behavior of the interface while providing more flexibility over where those steps arrive.
2. This circuit gets passed to a new qsimcirq implementation of simulate_moment_steps. This method would need to:
   a. Decompose the circuit into single gates;
   b. Identify where the moment boundaries in the Cirq circuit occur in the qsim circuit;
   c. Pass the timesteps for these boundaries to qsim's Run method as the times_to_measure_at;
   d. Define a "measurement" function that simply copies the entire state vector. (This "measurement" is not in the "destructive measure" sense, but rather refers to analyzing the state vector without modifying it.)
3. Users can then call a new _base_iterator method which iterates through the results generated in (2).

There are a few key flaws with this format, most notably that qsim would need to store all intermediate states since we have no way of doing "streaming output" from a qsim run. Separately, I don't think we support returning results from MeasurementGates when using the version of Run linked above - though I haven't tried it myself.

Unfortunately, I don't have a lot of bandwidth to look at this right now. @mpharrigan, if you're interested in taking a stab at it I'd be happy to point you to the relevant parts of the code.

[95-martin-orion]

Two updates on this:

Update 1
#499 adds QSimSimulator.simulate_moment_expectation_values, which outputs expectation values for selected observables after each moment or a user-specified set of moments. For experiments which only need EVs, this is significantly faster than simulating each truncated circuit.

Update 2
SimulatesIntermediateStates remains at odds with qsim due to the reasons outlined above (namely gate fusion and state copying), but the existing simulator methods now properly support input states. This means you can define a simulation like:

circuits, ... = [cycle_1, cycle_2, ...]
input_state = 0
for cycle in circuits:
    result = qsimulator.simulate(cycle, input_state=state)
    # ...inspect new_state without modifying it...
    input_state = result._final_simulator_state

which achieves the desired result and allows Python-side management of the resulting state copies.