cirq.Circuit.reachable_frontier_from

Circuit.reachable_frontier_from(start_frontier: Dict[cirq.ops.raw_types.Qid, int], *, is_blocker: Callable[cirq.ops.raw_types.Operation, bool] = <function Circuit.<lambda>>) → Dict[cirq.ops.raw_types.Qid, int][source]

Determines how far can be reached into a circuit under certain rules.

The location L = (qubit, moment_index) is reachable if and only if:

a) L is one of the items in `start_frontier`.

OR

b) There is no operation at L and prev(L) = (qubit, moment_index-1)
    is reachable and L is within the bounds of the circuit.

OR

c) There is an operation P covering L and, for every location
    M = (q', moment_index) that P covers, the location
    prev(M) = (q', moment_index-1) is reachable. Also, P must not be
    classified as a blocker by the given `is_blocker` argument.
In other words, the reachable region extends forward through time along
each qubit until it hits a blocked operation or an operation that
crosses into the set of not-involved-at-the-moment qubits.
For each qubit q in start_frontier, the reachable locations will
correspond to a contiguous range starting at start_frontier[q] and
ending just before some index end_q. The result of this method is a
dictionary, and that dictionary maps each qubit q to its end_q.

Examples

If start_frontier is {
cirq.LineQubit(0): 6,
cirq.LineQubit(1): 2,
cirq.LineQubit(2): 2,
} then the reachable wire locations in the following circuit are
highlighted with ‘█’ characters:
0   1   2   3   4   5   6   7   8   9   10  11  12  13
0: ───H───@─────────────────█████████████████████─@───H───
│ │
1: ───────@─██H███@██████████████████████─@───H───@───────
│ │
2: ─────────██████@███H██─@───────@───H───@───────────────
│ │
3: ───────────────────────@───H───@───────────────────────
And the computed end_frontier is {
cirq.LineQubit(0): 11,
cirq.LineQubit(1): 9,
cirq.LineQubit(2): 6,
}
Note that the frontier indices (shown above the circuit) are
best thought of (and shown) as happening between moment indices.

If we specify a blocker as follows:

is_blocker=lambda: op == cirq.CZ(cirq.LineQubit(1),
                                 cirq.LineQubit(2))

and use this start_frontier:

{
    cirq.LineQubit(0): 0,
    cirq.LineQubit(1): 0,
    cirq.LineQubit(2): 0,
    cirq.LineQubit(3): 0,
}

Then this is the reachable area:

0   1   2   3   4   5   6   7   8   9   10  11  12  13
0: ─██H███@██████████████████████████████████████─@───H───
│ │
1: ─██████@███H██─@───────────────────────@───H───@───────
│ │
2: ─█████████████─@───H───@───────@───H───@───────────────
│ │
3: ─█████████████████████─@───H───@───────────────────────

and the computed end_frontier is:

{
    cirq.LineQubit(0): 11,
    cirq.LineQubit(1): 3,
    cirq.LineQubit(2): 3,
    cirq.LineQubit(3): 5,
}
Parameters:
  • start_frontier – A starting set of reachable locations.
  • is_blocker – A predicate that determines if operations block reachability. Any location covered by an operation that causes is_blocker to return True is considered to be an unreachable location.
Returns:

An end_frontier dictionary, containing an end index for each qubit q mapped to a start index by the given start_frontier dictionary.

To determine if a location (q, i) was reachable, you can use this expression:

q in start_frontier and start_frontier[q] <= i < end_frontier[q]

where i is the moment index, q is the qubit, and end_frontier is the result of this method.