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.