Cirq routing is hanging again for some circuits

[yourball]

Hi guys,

I have a concern similar to the one from issue #2282. The problem was fixed later and when running from 6d81ddbb commit everything works just fine. However, there were further changes in apply_next_swaps(...) function, in particular a new parameter max_num_empty_steps was introduced.

In the last version of code when running routing via route_circuit_greedily(...) and with parameters max_search_radius=1, max_num_empty_steps=1 everything also works well. However, when choosing different values for these two parameters (e.g. max_search_radius=2, max_num_empty_steps=1) routing hangs on some circuit instances.

Should there be any constraint on how to choose values for the parameters max_search_radius and max_num_empty_steps? Or maybe there is some bug in the routing code?

Thanks!

[dabacon]

@bryano I think you added this feature. Thoughts?

[bryano]

@wcourtney Could you provide some circuits (or code to generate them) on which the router hangs?

[yourball]

This is the code snippet. It works fine if number of qubits involved in the random circuit <16 (number of qubits in the hardware is 16) or for small value of n_moments. Otherwise it hangs.

import networkx as nx
import cirq
from cirq import LineQubit
from cirq.contrib.routing.greedy import route_circuit_greedily

edges = [
        [0, 1],
        [0, 7],
        [0, 15],
        [1, 2],
        [7, 6],
        [7, 8],
        [15, 8],
        [15, 14],
        [2, 3],
        [3, 4],
        [4, 5],
        [5, 6],
        [8, 9],
        [9, 10],
        [10, 11],
        [11, 12],
        [12, 13],
        [13, 14],
        ]

def create_cirq_hardware(edges):
    graph = nx.Graph()
    for edge in edges:
        graph.add_edges_from([(LineQubit(edge[0]), LineQubit(edge[1]))])
    return graph

cirq_hardware = create_cirq_hardware(edges)
circuit = cirq.testing.random_circuit(qubits=16, n_moments=200, 
                                      op_density=.5, random_state=1)

swap_network = route_circuit_greedily(circuit, 
                                      cirq_hardware,
                                      max_search_radius=2, 
                                      max_num_empty_steps=1,
                                      random_state=1)

[balopat]

This is definitely odd:

In colab works up to 8 qubits (~ 1 minute at that point) and then it hangs (it's been running for 12+ minutes now).

[yourball]

I think I managed to fix the issue by modifying function apply_next_swaps(...) in greedy router. In fact these changes were implemented earlier to fix such a problem and then for some reason were reverted.

See this screenshot:

After partially reverting these changes in apply_next_swaps(...) in Cirq. 0.8.2 the greedy router works fine! Should I create a pool request with the changes?

This is the modified version of apply_next_swaps(...) function:

def apply_next_swaps(self, require_frontier_adjacency: bool = False):
        """Applies a few SWAPs to get the mapping closer to one in which the
        next logical gates can be applied.

        See route_circuit_greedily for more details.
        """

        time_slices = get_time_slices(self.remaining_dag)

        if require_frontier_adjacency:
            frontier_edges = sorted(time_slices[0].edges)
            self.bring_farthest_pair_together(frontier_edges)
            return

        for k in range(1, self.max_search_radius + 1):
            candidate_swap_sets = list(self.get_edge_sets(k))
            for time_slice in time_slices:
                edges = sorted(time_slice.edges)
                distance_vectors = list(
                    self.get_distance_vector(edges, swap_set)
                    for swap_set in candidate_swap_sets)
                dominated_indices = _get_dominated_indices(distance_vectors)
                candidate_swap_sets = [
                    S for i, S in enumerate(candidate_swap_sets)
                    if i not in dominated_indices
                ]
                if len(candidate_swap_sets) == 1:
                    self.apply_swap(*candidate_swap_sets[0])
                    if list(
                            self.remaining_dag.findall_nodes_until_blocked(
                                self.acts_on_nonadjacent_qubits)):
                        return
                    else:
                        break

        self.apply_next_swaps(True)

These are the lines I added:

                    if list(
                            self.remaining_dag.findall_nodes_until_blocked(
                                self.acts_on_nonadjacent_qubits)):
                        return
                    else:
                        break

[yourball]

Submitted PR #3360

[balopat]

Was fixed in #3360.