Map input circuit onto a backend topology via insertion of SWAPs.
Implementation of Sven Jandura’s swap mapper submission for the 2018 Qiskit Developer Challenge, adapted to integrate into the transpiler architecture.
The role of the swapper pass is to modify the starting circuit to be compatible with the target device’s topology (the set of two-qubit gates available on the hardware.) To do this, the pass will insert SWAP gates to relocate the virtual qubits for each upcoming gate onto a set of coupled physical qubits. However, as SWAP gates are particularly lossy, the goal is to accomplish this remapping while introducing the fewest possible additional SWAPs.
This algorithm searches through the available combinations of SWAP gates by means of a narrowed best first/beam search, described as follows:
- Start with a layout of virtual qubits onto physical qubits.
- Find any gates in the input circuit which can be performed with the current layout and mark them as mapped.
- For all possible SWAP gates, calculate the layout that would result from their application and rank them according to the distance of the resulting layout over upcoming gates (see _calc_layout_distance.)
- For the four (search_width) highest-ranking SWAPs, repeat the above process on the layout that would be generated if they were applied.
- Repeat this process down to a depth of four (search_depth) SWAPs away from the initial layout, for a total of 256 (search_width^search_depth) prospective layouts.
- Choose the layout which maximizes the number of two-qubit which could be performed. Add its mapped gates, including the SWAPs generated, to the output circuit.
- Repeat the above until all gates from the initial circuit are mapped.
For more details on the algorithm, see Sven’s blog post: https://medium.com/qiskit/improving-a-quantum-compiler-48410d7a7084 (opens in a new tab)
- coupling_map (Union[CouplingMap, Target]) – CouplingMap of the target backend.
- search_depth (int (opens in a new tab)) – lookahead tree depth when ranking best SWAP options.
- search_width (int (opens in a new tab)) – lookahead tree width when ranking best SWAP options.
- fake_run (bool (opens in a new tab)) – if true, it only pretend to do routing, i.e., no swap is effectively added.
Check if the pass is an analysis pass.
If the pass is an AnalysisPass, that means that the pass can analyze the DAG and write the results of that analysis in the property set. Modifications on the DAG are not allowed by this kind of pass.
Check if the pass is a transformation pass.
If the pass is a TransformationPass, that means that the pass can manipulate the DAG, but cannot modify the property set (but it can be read).
execute(passmanager_ir, state, callback=None)
Execute optimization task for input Qiskit IR.
- passmanager_ir (Any (opens in a new tab)) – Qiskit IR to optimize.
- state (PassManagerState) – State associated with workflow execution by the pass manager itself.
- callback (Callable (opens in a new tab) | None) – A callback function which is caller per execution of optimization task.
Optimized Qiskit IR and state of the workflow.
Name of the pass.
Run the LookaheadSwap pass on dag.
dag (DAGCircuit) – the directed acyclic graph to be mapped
A dag mapped to be compatible with the coupling_map in
- TranspilerError – if the coupling map or the layout are not
- compatible with the DAG**, or **if the coupling_map=None –
Update workflow status.
- state (PassManagerState) – Pass manager state to update.
- run_state (RunState) – Completion status of current task.
Updated pass manager state.