cirq.RouteCQC

Transformer class that implements a circuit routing algorithm.

cirq.RouteCQC(
    device_graph: nx.Graph
)

Used in the notebooks

Used in the tutorials

The algorithm proceeds as follows:

  1. Computes the timesteps (two_qubit_ops) of the circuit: considering operations in the given circuit from beginning to end, the next timestep is a maximal set of 2-qubit operations that act on disjoint qubits. It is 'maximal' because any 2-qubit gate's qubits in the next timestep must intersect with the qubits that are acted on in the current timestep.

  2. Places the logical qubits in the input circuit onto some input device graph by using an initial mapper (cirq.LineInitialMapper by default).

  3. Insert necessary swaps to ensure all 2-qubit gates are between adjacent qubits on the device graph by traversing the timesteps from left to right and for each timestep: 1. Remove any single qubit gate and executable 2-qubit gate in the current timestep and add it to the output routed circuit. 2. If there aren't any gates left in the current timestep, move on to the next. 3. If there are gates remaining in the current timestep, consider a set of candidate swaps on them and rank them based on a heuristic cost function. Pick the swap that minimises the cost and use it to update our logical to physical mapping. Repeat from 3.1.

>>> import cirq_google as cg
>>> circuit = cirq.testing.random_circuit(5, 10, 0.6)
>>> device = cg.Sycamore
>>> router = cirq.RouteCQC(device.metadata.nx_graph)
>>> rcirc, initial_map, swap_map = router.route_circuit(circuit)
>>> fcirc = cirq.optimize_for_target_gateset(rcirc, gateset = cg.SycamoreTargetGateset())
>>> device.validate_circuit(fcirc)
>>> cirq.testing.assert_circuits_have_same_unitary_given_final_permutation(
...     rcirc, circuit.transform_qubits(initial_map), swap_map
... )

device_graph The connectivity graph of physical qubits.

ValueError if device_graph is a directed graph.

Methods

route_circuit

View source

route_circuit(
    circuit: 'cirq.AbstractCircuit',
    *,
    lookahead_radius: int = 8,
    tag_inserted_swaps: bool = False,
    initial_mapper: Optional['cirq.AbstractInitialMapper'] = None,
    context: Optional['cirq.TransformerContext'] = None
) -> Tuple['cirq.AbstractCircuit', Dict['cirq.Qid', 'cirq.Qid'], Dict['cirq.Qid',
    'cirq.Qid']]

Transforms the given circuit to make it executable on the device.

This transformer assumes that all multi-qubit operations have been decomposed into 2-qubit operations and will raise an error if circuit a n-qubit operation where n > 2. If circuit contains cirq.CircuitOperations and context.deep is True then they are first unrolled before proceeding. If context.deep is False or context is None then any cirq.CircuitOperation that acts on more than 2-qubits will also raise an error.

The algorithm tries to find the best swap at each timestep by ranking a set of candidate swaps against operations starting from the current timestep (say s) to the timestep at index s + lookahead_radius to prune the set of candidate swaps. If it fails to converge to a to a single swap because of highly symmetrical device or circuit connectivity, then symmetry breaking strategies are used.

Since routing doesn't necessarily modify any specific operation and only adds swaps before / after operations to ensure the circuit can be executed, tagging operations with tags from context.tags_to_ignore will have no impact on the routing procedure.

Args
circuit the input circuit to be transformed.
lookahead_radius the maximum number of succeeding timesteps the algorithm will consider for ranking candidate swaps with the cost cost function.
tag_inserted_swaps whether or not a RoutingSwapTag should be attched to inserted swap operations.
initial_mapper an initial mapping strategy (placement) of logical qubits in the circuit onto physical qubits on the device.
context transformer context storing common configurable options for transformers.

Returns
The routed circuit, which is equivalent to original circuit up to a final qubit permutation and where each 2-qubit operation is between adjacent qubits in the device_graph. The initial mapping from logical to physical qubits used as part of the routing procedure. The mapping from physical qubits before inserting swaps to physical qubits after inserting swaps.

Raises
ValueError if circuit has operations that act on 3 or more qubits, except measurements.

__call__

View source

__call__(
    circuit: 'cirq.AbstractCircuit',
    *,
    lookahead_radius: int = 8,
    tag_inserted_swaps: bool = False,
    initial_mapper: Optional['cirq.AbstractInitialMapper'] = None,
    context: Optional['cirq.TransformerContext'] = None
) -> 'cirq.AbstractCircuit'

Transforms the given circuit to make it executable on the device.

This method calls self.route_circuit and returns the routed circuit. See docstring of RouteCQC.route_circuit for more details on routing.

Args
circuit the input circuit to be transformed.
lookahead_radius the maximum number of succeeding timesteps the algorithm will consider for ranking candidate swaps with the cost cost function.
tag_inserted_swaps whether or not a cirq.RoutingSwapTag should be attached to inserted swap operations.
initial_mapper an initial mapping strategy (placement) of logical qubits in the circuit onto physical qubits on the device. If not provided, defaults to an instance of cirq.LineInitialMapper.
context transformer context storing common configurable options for transformers.

Returns
The routed circuit, which is equivalent to original circuit up to a final qubit permutation and where each 2-qubit operation is between adjacent qubits in the device_graph.

Raises
ValueError if circuit has operations that act on 3 or more qubits, except measurements.

__eq__

View source

__eq__(
    other
) -> bool

Return self==value.