graph_builder.py

from qiskit import *
import networkx as nx
from collections import defaultdict
import config

from qiskit import *
import networkx as nx
from collections import defaultdict
import config


def MeasureF():
    measures = [None] * config.qc.num_qubits
    new_data = []
    for item in config.qc.data[::-1]:
        if item[0].name == "measure":
            measures[item[1][0].index] = item
            
        elif item[0].name in ['ccx', 'mcx', 'x', 'cx', 'mcx_gray']:
            can_move_target = True
            for ctrl_qubit in item[1][:-1]:
                if measures[ctrl_qubit.index] == None:
                    can_move_target = False
            if not can_move_target:
                if measures[item[1][-1].index] != None:
                    new_data.append(measures[item[1][-1].index])
                    measures[item[1][-1].index] = None
        elif item[0].name in ['rzz', 'cp', 'cz', 'rz', 'p', 's', 'sdg', 't', 'tdg']:
            pass
        elif item[0].name in ['swap']:
            if measures[item[1][0].index] == None or measures[item[1][1].index] == None:
                for qubit in item[1]:
                    if measures[qubit.index] != None:
                        new_data.append(measures[qubit.index])
                        measures[qubit.index] = None
        else:
            for qubit in item[1]:
                if measures[qubit.index] != None:
                    new_data.append(measures[qubit.index])
                    measures[qubit.index] = None

        new_data.append(item)
        
    for item in measures:
        if item != None:
            new_data.append(item)
        
    config.qc.data = new_data[::-1]

    


def Commute():
    com_set1 = ["x", "y", "z"]
    com_set2 = ["z", "rz", "s", "t", "sdg", "tdg", "p", "cz", "cp", "rzz"]
    com_set3 = ["x", "rx", "sx"]
    com_set4 = ["y", "ry"]
    gateNum = 0
    measureNum = 0
    config.gate = []
    config.measure = []
    config.qubit_for_g = {}
    config.measure_to_index = {} # measure index to qubit index
    if config.mode == "reorder"  or config.mode == "all":
        
        for i in range(config.totalNum):
            if config.qc.data[i][0].name != "measure":
                config.gate.append(i)
                config.qubit_for_g[i] = [qubit.index for qubit in config.qc.data[i][1]]
                gateNum += 1
            else:
                measureNum += 1
                config.qubit_for_g[i] = [qubit.index for qubit in config.qc.data[i][1]]
                config.measure.append(i)
                config.measure_to_index[i] = config.qc.data[i][1][0].index
        config.commute = [[None for _ in range(config.totalNum)] for _ in range(config.totalNum)] # 0 for commute, 1 for non-commute
        config.paraList = [[1 for _ in range(config.totalNum)] for _ in range(config.totalNum)] # 0 for commute, 1 for non-commute
        config.gate_on_q = {i: [] for i in range(config.qc.num_qubits)}
        for i in range(config.totalNum):
            qubit = config.qc.data[i][1]
            for q in qubit:
                config.gate_on_q[q.index].append(i)
            for j in range(i, config.totalNum):
                if i == j:
                    config.commute[i][j] = 0
                else:
                    gi = [qubit.index for qubit in config.qc.data[i][1]]
                    gj = [qubit.index for qubit in config.qc.data[j][1]]
                    lenA = len(gi)
                    lenB = len(gj)
                    ni = config.qc.data[i][0].name
                    nj = config.qc.data[j][0].name
                    
                    # parallel
                    parallel = True
                    for loci in gi:
                        for locj in gj:
                            if loci == locj:
                                parallel = False
                                break
                        if not parallel:
                            break
                    if parallel:
                        config.commute[i][j] = 0
                        config.paraList[i][j] = 0
                        continue
                                    
                    # commuting group
                    if ni in com_set1 and nj in com_set1:
                        config.commute[i][j] = 0
                        continue
                    elif ni in com_set2 and nj in com_set2: 
                        config.commute[i][j] = 0
                        continue
                    elif ni in com_set3 and nj in com_set3:
                        config.commute[i][j] = 0
                        continue
                    elif ni in com_set4 and nj in com_set4:
                        config.commute[i][j] = 0
                        continue
                        
                    # x, cx, ccx, mcx, rx, sx
                    x_series = ["x", "cx", "ccx", "mcx", "rx", "sx"]
                    if ni in x_series and nj in x_series:
                        if (gi[-1] not in gj[:-1]) and (gj[-1] not in gi[:-1]):
                            config.commute[i][j] = 0
                            continue
                            
                    # z-rotation on controls
                    if nj in com_set2 and ni in x_series:
                        (gi, gj, lenA, lenB, ni, nj) = (gj, gi, lenB, lenA, nj, ni)
                    if ni in com_set2 and nj in x_series:
                        if gj[-1] not in gi:
                            config.commute[i][j] = 0
                            continue
                            
                    # only control qubits overlapping
                    contolled_gates = ["cx", "ccx", "mcx", "cz", "cp"]                                         
                    if ni in contolled_gates and nj in contolled_gates:
                        if ni[-1] != nj[-1]:
                            config.commute[i][j] = 0
                            continue
                    
                    config.commute[i][j] = 1
    elif config.mode == "none" or config.mode == "eager":
        for i in range(config.totalNum):
            if config.qc.data[i][0].name != "measure":
                config.gate.append(i)
                config.qubit_for_g[i] = [qubit.index for qubit in config.qc.data[i][1]]
                gateNum += 1
            else:
                measureNum += 1
                config.qubit_for_g[i] = [qubit.index for qubit in config.qc.data[i][1]]
                config.measure.append(i)
                config.measure_to_index[i] = config.qc.data[i][1][0].index
        config.commute = [[None for _ in range(config.totalNum)] for _ in range(config.totalNum)] # 0 for commute, 1 for non-commute
        config.gate_on_q = {i: [] for i in range(config.qc.num_qubits)}
        for i in range(config.totalNum):
            qubit = config.qc.data[i][1]
            for q in qubit:
                config.gate_on_q[q.index].append(i)
            for j in range(i, config.totalNum):
                if i == j:
                    config.commute[i][j] = 0
                else:
                    gi = [qubit.index for qubit in config.qc.data[i][1]]
                    gj = [qubit.index for qubit in config.qc.data[j][1]]
                    lenA = len(gi)
                    lenB = len(gj)
                    ni = config.qc.data[i][0].name
                    nj = config.qc.data[j][0].name
                    
                    # parallel
                    parallel = True
                    for loci in gi:
                        for locj in gj:
                            if loci == locj:
                                parallel = False
                                break
                        if not parallel:
                            break
                    if parallel:
                        config.commute[i][j] = 0
                        continue          
                    config.commute[i][j] = 1



def BuildCanon():
    G = nx.DiGraph()
    pa_pair = []
    # canonical form
    for j in range(config.totalNum):
        for k in range(j):
            G.nodes[k]['isReachable'] = True
            G.nodes[k]['control'] = False # control qubit before measurement
            G.nodes[k]['target'] = False # target qubit before measurement
        if config.qc.data[j][0].name == "measure":
            G.add_node(j, isReachable = True, M = True, name = config.qc.data[j][0].name)
        else:
            G.add_node(j, isReachable = True, M = False, name = config.qc.data[j][0].name)

        for i in range(j - 1, -1, -1):
            if not G.nodes[i]['isReachable']:
                for pred in G.predecessors(i):
                    G.nodes[pred]['isReachable'] = False
            if G.nodes[i]['isReachable'] and config.commute[i][j] == 0:
                if config.paraList[i][j] == 1:
                    pa_pair.append((i, j))
            if G.nodes[i]['isReachable'] and config.commute[i][j] != 0:
                G.add_edge(i, j)
                for pred in G.predecessors(i):
                   G.nodes[pred]['isReachable'] = False
    tmp_pair = set(tuple(sorted(pair)) for pair in pa_pair) 
    paral_pair = list(tmp_pair)    
    
    return G, paral_pair

def DeleteOne(G):
    config.single_qubit = []
    num_gate = config.qubit_for_g.get('default', 0)
    for i in range(num_gate):
        if len(config.qubit_for_g[i]) == 1 and i in G.nodes:
            pre = list(G.predecessors(i))
            suc = list(G.successors(i))
            if len(pre) == 0:
                
                for s in suc:
                    G.remove_edge(i, s)
            elif len(suc) == 0:
                for p in pre:
                    G.remove_edge(p, i)
            else:
                for s in suc:
                    G.remove_edge(i, s)
                for p in pre:
                    G.remove_edge(p, i)
                    for s in suc:
                        G.add_edge(p, s)
            G.remove_node(i)
            config.single_qubit.append(i)
                        
    return G

def PotentialPair(G):
    pair = {}
    for i in range(config.qc.num_qubits):
        if i in config.used:
            pair[i] = []
        else:
            pair[i] = [j for j in range(config.qc.num_qubits)
               if j != i and j not in config.a.values()]


    for i in config.measure:
        if i not in G:
            continue
        q = config.measure_to_index[i]
        anc = nx.ancestors(G, i) 
        related_qubits = set()
        for a in anc:
            related_qubits.update(config.qubit_for_g[a])

        for k in related_qubits:
            if k in pair[q]:
                pair[q].remove(k)

    return pair 

def reuseGraph(pair, k, paral_pair):
    edges = [(u, v) for u in pair for v in pair[u] if u != v]

    adj = defaultdict(lambda: defaultdict(int))
    for u, v in edges:
        adj[u][v] += 1
        adj[v][u] += 1

    all_nodes = set(adj.keys()) | {v for neighbors in adj.values() for v in neighbors}

    def total_weight(node):
        return sum(adj[node].values())

    degree_list = sorted(all_nodes, key=total_weight, reverse=True)

    selected = set()
    candidates = set(all_nodes)
    if not degree_list:
        return set(), 0

    selected.add(degree_list[0])
    candidates.remove(degree_list[0])

    while len(selected) < k and candidates:
        best_node = None
        max_connection_weight = -1

        for node in candidates:
            weight_sum = sum(adj[node].get(s, 0) for s in selected)
            if weight_sum > max_connection_weight:
                max_connection_weight = weight_sum
                best_node = node

        if best_node is None:
            break

        selected.add(best_node)
        candidates.remove(best_node)

    selected = sorted(list(selected))
    filtered_edges = [(u, v) for (u, v) in edges if u in selected and v in selected]
    filtered_pair_dict = defaultdict(list)
    for u, v in filtered_edges:
        filtered_pair_dict[u].append(v)

    filtered_paral = [
        (u, v) for (u, v) in paral_pair
        if any(q in selected for q in config.qubit_for_g[u]) and
        any(q in selected for q in config.qubit_for_g[v])
    ]
    return selected, filtered_pair_dict, filtered_paral