add StaticPlacementPass

[SoshunNaito]

This PR adds a new pass named StaticPlacementPass, which attempts to find an embedding of logical qubits into the physical coupling graph so that no SWAPs are needed. Also, it supports a timeout_sec parameter to limit the search time. Please note that additional packages such as timeout_decorator and networkx are required to run this pass.

Original issue: https://github.com/bqskit/bqskit/issues/224

[edyounis]

This is definitely on the right track. Thanks for taking this issue up and putting a PR.

I like the timeout feature, but we should have this interface with the predicate system to simplify workflows containing this. By this I mean, turning this BasePass actually into a PassPredicate, or have it work with a predicate. This should also remove the RuntimeErrors. We can then have a workflow that looks like:

workflow = [
    StaticPlacementPass(...)
    IfThenElsePass(
        FoundPlacement(),
        NOOPPass(),
        normal_mapping_workflow,
]

I am also very hesitant to add a heavy dependency (networkx) for just this one algorithm. Can we implement the algorithm internally?

[SoshunNaito]

By this I mean, turning this BasePass actually into a PassPredicate, or have it work with a predicate. This should also remove the RuntimeErrors.

Great idea! I have removed RuntimeErrors for the first step. In this version, the StaticPlacementPass can be used as follows:

workflow = [
    SetModelPass(model),
    StaticPlacementPass(),
    IfThenElsePass(
        PhysicalPredicate(),
        [LogPass("Static Placement Found")],
        [LogPass("Greedy Placement Required"), GreedyPlacementPass()],
    ),
    ApplyPlacement(),
]

I am also very hesitant to add a heavy dependency (networkx) for just this one algorithm. Can we implement the algorithm internally?

Yes, of course! We can use an exhaustive search for monomorphism by checking all possible embeddings from logical to physical qudits. I hope implementing the algorithm internally will remove both networkx and timeout_decorator dependencies.

[SoshunNaito]

Here I have added a naive implementation of the find_monomorphic_subgraph method. Since it requires approximately $(N_p)^{N_l}$ iterations (where $N_p$ and $N_l$ represent the number of physical and logical qudits), we need to further optimize it by pruning the search space.

[SoshunNaito]

I have added a pruning feature to reduce the search space. While placing logical qudits one by one, it skips physical qudits based on the following conditions:

1. The physical qudit must not be occupied by another logical qudit.
2. The degree of the physical qudit must not be less than the degree of the logical qudit.
3. The physical qudit must be connected to all the previous logical qudits.

Using this feature, the search space is reduced from $(N_p)^{N_l}$ to $|S|^{N_l}$, where $|S|$ is the average number of candidates for each step.

[SoshunNaito]

Hi @edyounis, how does my code look to you? I would appreciate your comments, feedbacks, or suggestions for further improvement. Thanks!

[edyounis]

Looks good, can we add some tests? How large can we push this within a 1- or 10-second time frame?

[SoshunNaito]

Sure, of course! I have added test_static.py and measured how long it takes for graph embedding. I used circuits with circular connectivity and physical devices with square grid topology, so it is clear that the circuits can be embedded iff the number of qudits is even.

These two plots below show the elapsed time for each condition (grid_size, logical_qudits). To answer your question, we can test all possible placements for up to (5x5, 20) in 10 seconds and (5x5, 15) in 1 second. When there is a valid placement, the embedding runs in less than 1 second even for (7x7, 40). In addition, when the circuit contains nodes with high degrees, the embedding ends in a short time owing to the pruning feature.

[edyounis]

Pre-commit and tests are failing, can you get those fixed. The code does look good

[SoshunNaito]

@edyounis The code seems to be fixed now. Could you check it?