contrib.routing algorithm hangs

[kevinsung]

The repro code below constructs a QAOA circuit and then tries to route it on a device 100 times, printing some output before each attempt. It prints up to Attempt 1 and then hangs.

import random
import networkx as nx
import numpy as np
import cirq
from cirq.contrib import routing


def random_3_regular_model(n, seed):
    connectivity_graph = nx.random_regular_graph(3, n, seed=seed)
    graph = nx.Graph()
    for i, j in connectivity_graph.edges:
        graph.add_edge(cirq.LineQubit(i), cirq.LineQubit(j),
                       weight=1)
    return graph


def Rzz(rads):
    return cirq.ZZPowGate(exponent=2 * rads / np.pi, global_shift=-0.5)


def qaoa_rzz_layer(graph, gamma):
    return (Rzz(gamma * graph[q][r]['weight']).on(q, r)
            for q, r in graph.edges)


def qaoa_rx_layer(graph, beta):
    return cirq.Rx(2 * beta).on_each(*graph.nodes)


def qaoa_unitary(graph, gammas, betas):
    for gamma, beta in zip(gammas, betas):
        yield qaoa_rzz_layer(graph, gamma)
        yield qaoa_rx_layer(graph, beta)


def qaoa_circuit(graph, gammas, betas):
    return cirq.Circuit.from_ops(
        cirq.H.on_each(*graph.nodes),
        qaoa_unitary(graph, gammas, betas))


def _parse_device(s: str):
    lines = s.strip().split('\n')
    qubits = []  # type: List[GridQubit]
    for row, line in enumerate(lines):
        for col, c in enumerate(line.strip()):
            if c != '-':
                qubit = cirq.GridQubit(row, col)
                qubits.append(qubit)
    return qubits


device_grid = """
--A----
-ABC---
ABCDE--
-CDEFG-
--EFGHI
---GHI-
----I--
"""
device_qubits = _parse_device(device_grid)
device_graph = routing.gridqubits_to_graph_device(device_qubits)

n = 20
p = 2

prng = np.random.RandomState(36587)

gammas = prng.randn(p)
betas = prng.randn(p)

graph = random_3_regular_model(n, seed=prng)
circuit = qaoa_circuit(graph, gammas, betas)

for i in range(100):
    print(f'Attempt {i}')
    _ = routing.route_circuit(circuit, device_graph, algo_name='greedy', random_state=prng)

[kevinsung]

Now that it is possible to seed the routing code, I've updated the repro in the opening post so that it is deterministic and hangs after printing Attempt 1.

[mpharrigan]

@bryano any ideas?