search

BQSKit / bqskit

Berkeley Quantum Synthesis Toolkit
Other
106 stars 31 forks source link

Subgraph Isomorphism Checks #224

Closed edyounis closed 2 weeks ago

edyounis commented 4 months ago

We can add subgraph isomorphism passes that try to match logical connectivity to a physical topology without performing any swap operations. We can also add these passes to specific spots in the standard workflow to avoid placement + layout + routing.

The main step here is to develop a compiler pass that tries to find a subgraph isomorphism between a Circuit's logical connectivity and a MachineModel's physical topology.

To get the logical topology, you can call Circuit.coupling_graph. This gives you a graph where nodes are the qudits in the circuit and edges exist between qudits that have a gate between them in the circuit.

To get the physical topology of the target MachineModel during compilation, you can use the PassData object in a pass's run function: data.model.coupling_graph. This gives you a graph where nodes are physical qudits in a QPU, and edges exist between qudits that can interact.

Both of these return CouplingGraph objects, which has many helpful methods.

The goal is to attempt to find a map between logical and physical topology without needing any further routing. This will not always be possible. There are many algorithms that will solve this problem, but we should consider that our problem size may vary greatly and that we should have a time-out of some sort before we fall back to traditional layout and routing strategies already implemented in BQSKit.

If we have found a mapping, we can set data.initial_mapping = data.final_mapping = our_answer and skip layout and routing steps in the BQSKit workflows. Integrating this into BQSKit's workflows can be made into a separate issue and doesn't need to be addressed here.

SoshunNaito commented 1 month ago

Hi @edyounis, I am very interested in this topic.

The easiest way to realize that idea is to use networkx.algorithms.isomorphism.GraphMatcher class, which supports the subgraph_is_monomorphic function. I think we should use monomorphism instead of isomorphism because extra physical edges do not affect the compilation result at all. For example, G1=[a-b c-d] can be embedded into G2=[v w-x-y-z], but this mapping is not isomorphic because no edge in G1 is mapped to x-y.

In the PR above, StaticPlacementPass.run attempts to find a monomorphic mapping between logical and physical coupling graphs at first, then returns the placement based on the result. If the search times out or no monomorphic mapping is found, it raises an error so we can fall back to other placement strategies.

I will be happy if you check my PR above and give me suggestions for further improvement, thanks!