search

Qiskit / rustworkx

A high performance Python graph library implemented in Rust.
https://www.rustworkx.org
Apache License 2.0
1.02k stars 145 forks source link

Add implementation of approximate token swapper to rustworkx and rustworkx-core #701

Closed mtreinish closed 1 year ago

mtreinish commented 1 year ago

What is the expected enhancement?

In qiskit-terra we're using an implementation of https://arxiv.org/abs/1602.05150 to handle transforming circuit layouts. This implementation for qiskit-terra is here: https://github.com/Qiskit/qiskit-terra/blob/main/qiskit/transpiler/passes/routing/algorithms/token_swapper.py which is built around a rustworkx graph object implemented in Python.

However, it would be great it retworkx had a native implementation of this algorithm and had it exposed in both rustworkx and rustworkx-core (to expose it to rust consumers of the library too) especially since it's generic and strictly structural.

enavarro51 commented 1 year ago

I can work on this.

enavarro51 commented 1 year ago

One question. What subdirectory should this go in rustworkx-core?

mtreinish commented 1 year ago

We can probably create a standalone module for this since it doesn't really fit into category with anything else we have in the library.

enavarro51 commented 1 year ago

@mtreinish Since I believe this is to be a generic token swapping algorithm, should this rust version in any way reference DAGCircuit and QuantumRegister as it does in permutation_circuit? Should this function remain part of qiskit-terra?

enavarro51 commented 1 year ago

As a follow-up, it looks like in transpiler/passes/routing/algorithms, types.py and util.py would remain unchanged, and token_swapper would remain with functions map, _trial_map, add_token_edges and _swap moved to rustworkx-core with appropriate imports adjiusted. Correct?

mtreinish commented 1 year ago

Yeah, it should be free of anything qiskit or quantum specific. The pure algorithm implementation of ApproximateTokenSwapper we should try to add to rustworkx-core (and have a python interface for too). We shouldn't try to implement things like the PermutationCircuit or anything that is expecting a quantum circuit or other thigns from qiskit-terra. Just concentrate on computing the swaps and having an API to perform that.

Once we have this rustworkx we can update the qiskit-terra usage to compute the swaps using that function and pass that to build the permutation circuits in qiskit-terra.

enavarro51 commented 1 year ago

Ok. Good. Basically it's just implementing map, which might be called token_swap, and its direct calls in rustworkx-core and creating a python interface in rustworkx. Then permutation_circuit will call the python version of token_swap from qiskit-terra.