Add post selection gates and update simulators to support these gates

[Strilanc]

As a sort of post-selection. The recent change to simulator broke this test. Not sure how to fix it given the new interface. @dabacon ideas?

        result = simulator.simulate(
            circuit,
            qubit_order=[ancilla_qubit] + list(system_qubits),
            initial_state=current_state,
            repetitions=reps)

        # Determine the bit by majority vote
        num_ones = numpy.count_nonzero(result.measurements['ancilla_qubit'])
        num_zeros = reps - num_ones
        last_measured_bit = num_ones > num_zeros

        # Get one of the resulting states with the correct bit measured
        current_state = result.final_states[
                numpy.where(result.measurements['ancilla_qubit'] ==
                            last_measured_bit)[0][0]]

[Strilanc]

@kevinsung Is the code supposed to be doing this post-selection stuff? It seems very unnatural w.r.t. the actual computation model.

[kevinsung]

Yes, it is. It does seem unnatural, but I wasn't sure how else to implement it using Cirq. I guess you could just continue repeating the circuit until you get the bit you want, and then continue.

[Strilanc]

Is the goal of the code to do a phase estimation of applying some operation to a state? It seems like having access to the wavefunction would make that a lot more efficient than this.

[kevinsung]

It's an implementation of "iterative phase estimation" from https://arxiv.org/abs/quant-ph/0610214. The thing is that the complete algorithm consists of multiple stages, where each stage ends with a measurement. Furthermore, you want to repeat, for example, the first stage multiple times, and only continue on to the next stage when the measurement result is equal to the one that happened a majority of the time.

The one reservation I have about this implementation is that it does not clearly convert to a quantum circuit like the rest of the functions in the library do. The truth is, I wrote it as "research" code to do numerics for the Trotter error project, so maybe it doesn't really fit in the library in its current form.

[kevinsung]

One way to fix this is to allow post-selection in the Simulator.simulate method. I.e., if the circuit has measurements, then you can specify what you want the outcomes to be.

[dabacon]

We could add post select on the simulate method. As part of doing this we would likely also expose ability to post select when stepping through a circuit.

[Strilanc]

A simple way to do this is with post-selection gates. Might interact poorly with devices, which obviously will reject these operations.

[kevinsung]

I was thinking that Simulator.simulate should just take a dictionary of measurement results.

[dabacon]

The elegant solution is a gate which the simulators understand. Let's make this the issue to track that.

[Strilanc]

It's now possible to specify these gates using the _act_on_ protocol.

[daxfohl]

@kevinsung Is the idea here that we want to specify ahead of time that you only care about when measurement m1 is 1, so retry until that happens?

If that's the case we have the ability to do that very generically now. All simulators support act_on, using their specified subclass of ActOnArgs as the simulator state. (i.e. density matrix simulator uses DensityMatrixActOnArgs, which contains a density matrix and various metadata).

Any class implementing ActOnArgs is required to implement the copy method, which is a deep copy (except for the RNG), so you can think of it as a snapshot of the state that can be used for repetitions etc. All ActOnArgs classes also have to implement the perform_measurement method.

So we could augment MeasurementGate with a new parameter required_value or something, and update MeasurementGate._act_on_ to call c = args.copy(); c.measure() until it gets the desired measurement. We'd then just need one new abstract function on ActOnArgs to read the resulting state from c back into the original. Should be pretty straightforward. This would then light up this feature for all simulators.

(Assuming that's what's wanted here, and if this feature is still desired.)

cc @95-martin-orion @smitsanghavi @balopat

(And the downside being that this is a relatively slow trial and error method. But classes that have a fast way of determining the resulting state after a desired measurement value can be handled specially in that same function).

[95-martin-orion]

In my opinion, the "correct" way to implement post-selection in simulation is with a new gate whose _act_on_ method simply applies the |0)(0| or |1)(1| operator without checking it against the existing state. This requires no trial-and-error, and (assuming we don't normalize the state after) allows us to determine what percentage of runs we "discarded" to get that result. I'd prefer not to use MeasurementGate for this, as it's expected to function on both simulators and hardware.

As Craig notes, it's possible to manually construct these gate types, but I think having built-in versions in Cirq could be worthwhile. For extensibility, I'd suggest having a base type that accepts any set of non-unitary operators as well as an implementation of that base type which performs post-selection in the Z basis (i.e. with |0)(0| or |1)(1|).

(As an aside: the "correct" way to do post-selection in hardware would be a while-loop around the entirety of a circuit up to the post-selected measurement, with the loop conditioned on the result of that measurement. While-loops are part of #3234.)

[daxfohl]

Makes sense. As soon as I posted that I realized there's probably a deterministic operation.

[95-martin-orion]

Bumping this to say this would still be really cool to have for simulator-optimization, but in lieu of that the repeat-until introduced in #5018 can achieve this (albeit at a much slower pace).