Recursive transformer / iterator

[daxfohl]

Is your feature request related to a use case or problem? Please describe.

Would be great if there was built in support for mapping operations to automatically run in subcircuits. Otherwise all simple transformers have to do that themselves.

Describe the solution you'd like

Probably just a "run_inside_subcircuits" option in Cirq.map_operations. We should also have one for running inside tagged ops, running inside classically controlled ops, etc.

Additionally it would be nice if we had a Cirq.iterate that had the same options, so you could do something like Cirq.iterate(isinstance(cirq.X), op, run_inside_tags) and we could stop all the special handling for tagged ops. (Or maybe we make a special Cirq.isinstance specifically for this).

[optional] Describe alternatives/workarounds you've considered

[optional] Additional context (e.g. screenshots)

What is the urgency from your perspective for this issue? Is it blocking important work?

P2 - we should do it in the next couple of quarters

[tanujkhattar]

• Adding run_inside_subcircuits and tags_to_ignore to merge_* and map_* transformer primitives sounds like a good idea.
• Supporting this across all transformer by default can be more nuanced and would need modifications in individual transformers, mainly because not every transformer can be written as a composition of map*/merge* primitives.

• We should also have one for running inside tagged ops, running inside classically controlled ops, etc.

  • What do you mean by this? Can you give an example?

• so you could do something like Cirq.iterate(isinstance(cirq.X), op, run_inside_tags) and we could stop all the special handling for tagged ops.

  • There are some transformers which are inherently local, for example: applying a map to individual operations. In this case, adding a tags_to_ignore to cirq.map_operations should be enough to automatically handle tagged operations.
  • While other transformers, like AlignLeft / AlignRight etc, are non local and require additional surrounding context. In these cases, a Cirq.iterate which skips tagged operations would not be sufficient and special handling would be needed in the implementation of the transformer.

[daxfohl]

Like for when changing measurements to dephases, given a change_measure_to_dephase function, it would be great if we could just call

map_operation(
  circuit,
  change_measure_to_dephase,
  run_inside_subcircuits=True,
  run_inside_classically_controlled_operations=True,
  run_inside_tags=True,
  preserve_tags_if_modified=False,
)

or something like that, and map_operations does all the work of looking inside subcircuits, tagged operations, classically controlled ops, etc, and it removes tags on any changed gates. Even just having the arguments is useful because it highlights the things users should consider when implementing their own transformers, that they might otherwise forget about.

There are probably a lot of extra features we could add. However recuring through subcircuits is certainly the top.

(I'm actually not super sure about the iterate functionality. It sounded neat initially but I can't think of a solid use case for it).

[tanujkhattar]

@daxfohl tags_to_ignore and deep flags have been added to the transformer primitives. This should be enough to unblock the deferred measurement PR.

Please let me know if you think anything else needs to be added, for example:

• I'm not sure how run_inside_classically_controlled_operations would behave for any map_func method passed to map_operations.
• change_measure_to_dephase is already being implemented as a separate transformer and I don't think we should add it as a flag to map_operations.

[daxfohl]

@tanujkhattar Here's kind of what I'd expect:

def test_me():
    q = cirq.LineQubit(0)
    circuit = cirq.Circuit(
        cirq.X(q),
        cirq.X(q).with_tags('t'),
        cirq.X(q).with_tags('no_compile'),
        cirq.X(q).with_classical_controls('m'),
        cirq.CircuitOperation(cirq.FrozenCircuit(
            cirq.X(q),
        )),
    )

    def x_to_y(op: 'cirq.Operation', _) -> 'cirq.OP_TREE':
        return cirq.Y(q) if op.gate == cirq.X else op

    result = cirq.map_operations(circuit, x_to_y, deep=True, tags_to_ignore=('no_compile',))

    expected = cirq.Circuit(
        cirq.Y(q),
        cirq.Y(q).with_tags('t'),
        cirq.X(q).with_tags('no_compile'),
        cirq.Y(q).with_classical_controls('m'),
        cirq.CircuitOperation(cirq.FrozenCircuit(
            cirq.Y(q),
        )),
    )

    cirq.testing.assert_same_circuits(result, expected)

But here's what it comes out to

E       Diagram of actual circuit:
E       0: ───Y───Y───X['no_compile']───X───[ 0: ───Y─── ]───
E                                       ║
E       m: ═════════════════════════════^════════════════════
E
E       Diagram of expected circuit:
E       0: ───Y───Y['t']───X['no_compile']───Y───[ 0: ───Y─── ]───
E                                            ║
E       m: ══════════════════════════════════^════════════════════

So, the tag is removed in the 2nd one (which I'm aware is an ongoing discussion in #4956, and probably there should be a flag in map_operations to allow users to choose). And also the classically controlled X does not get transformed, which seems wrong (again we could add a separate flag to let users choose).

Granted this is an artificial example, but something similar like increasing the exponents by 1% or something could be real-world use cases. (Also see #970, it would be nice to be able to have a simple mapping function op ** 'param' if isinstance(gate, XPowGate) or something).

[tanujkhattar]

From cirq sync:

Let's open separate issues to track the two remaining requests, as both of them are nuanced and would need further discussion / evidence. See comments as follows:

• As per discussion on Keeping tags for all TaggedOperation methods. #4956, Tagged operations are supposed to be immutable, so if an operation changes, the tags should get removed. We can potentially add support to preserve tags on map_operations since it's a local transformer, but doing that on merge_operations is not well defined because tags can lose their meaning.
  I'd prefer to see more evidence of use cases where we'd like to preserve tags during a transformation, and if such use cases exist, we can revisit whether a) we'd like to add an option to transformers to preserve tags and b) Whether we'd like to modify the immutability of TaggedOperations.

• run_inside_classically_controlled_operations can also be added to map_operations, but it's more tricky for merge_operations. Another approach could be to wrap classically controlled operations in classically controlled circuit operations and then do a recursive decomposition inside circuit operations. Let's collect evidence of use cases and then decide on an approach.