shun-quantum-icc/new_add_linkselfie/schedulers/lonline_nb.py

# lonline_nb.py
import math

def _ns_for_round(s, k, C_const, delta, min_sets):
    """LinkSelFiE 由来の Ns(s,k) を計算（k=len(candidate_set)）。"""
    Ns = math.ceil(C_const * (2 ** (2 * s)) * math.log2(max((2 ** s) * k / delta, 2)))
    return max(Ns, min_sets)

def lonline_init(
    network, path_list, bounces, C_budget,
    *, return_details=False, C_const=0.01, delta=0.1, min_sets=4
):
    """
    広域探索フェーズ（s=1 の 1 ラウンドのみ）。候補全リンクに一律 Ns セットを投入できる場合に限り実行。
    出力:
      correctness, cost, best_path_fidelity, [alloc_by_path, est_fid_by_path,] state
    """
    # ★ 受け取った path_list を“公開ID(=1..L)”として、そのまま使う
    candidate_set = list(path_list)
    alloc_by_path = {int(p): 0 for p in path_list}
    est_fid_by_path = {}
    estimated_fidelities = {}
    cost = 0

    if not candidate_set or C_budget <= 0:
        base = (False, 0, None)
        if return_details:
            base += (alloc_by_path, est_fid_by_path)
        state = {
            "s": 1, "candidate_set": candidate_set, "estimated_fidelities": estimated_fidelities,
            "alloc_by_path": alloc_by_path, "est_fid_by_path": est_fid_by_path, "bounces": list(bounces),
            "C_const": C_const, "delta": delta, "min_sets": min_sets
        }
        return (*base, state)

    c_B = sum(bounces) if sum(bounces) > 0 else 1
    s = 1
    Ns = _ns_for_round(s, len(candidate_set), C_const, delta, min_sets)

    # 候補全リンクに一律 Ns セットを入れられるかを事前判定（途中打ち切りなしを保証）
    round_cost_all = len(candidate_set) * Ns * c_B
    if round_cost_all > C_budget:
        base = (False, 0, None)
        if return_details:
            base += (alloc_by_path, est_fid_by_path)
        state = {
            "s": s, "candidate_set": candidate_set, "estimated_fidelities": estimated_fidelities,
            "alloc_by_path": alloc_by_path, "est_fid_by_path": est_fid_by_path, "bounces": list(bounces),
            "C_const": C_const, "delta": delta, "min_sets": min_sets
        }
        return (*base, state)

    # ここから候補全リンクに一律 Ns セット投入（途中打ち切りなし）
    sample_times = {h: int(Ns) for h in bounces}
    p_s, measured = {}, []
    for path in list(candidate_set):
        p, used = network.benchmark_path(path, bounces, sample_times)
        cost += int(used)
        fidelity = p + (1 - p) / 2.0
        estimated_fidelities[path] = fidelity
        p_s[path] = p
        measured.append(path)
        alloc_by_path[int(path)] = alloc_by_path.get(int(path), 0) + int(used)
        est_fid_by_path[int(path)] = float(fidelity)

    # 逐次除去（現時点では 2^{-s} 閾値ルール）
    if p_s:
        p_max = max(p_s.values())
        new_cand = [path for path in measured if (p_s[path] + 2 ** (-s) > p_max - 2 ** (-s))]
        candidate_set = new_cand or candidate_set

    best_path_fid = None
    if estimated_fidelities:
        best_path = max(estimated_fidelities, key=estimated_fidelities.get)
        best_path_fid = estimated_fidelities[best_path]
        correctness = (best_path == getattr(network, "best_path", None))
    else:
        correctness = False

    state = {
        "s": s, "candidate_set": candidate_set, "estimated_fidelities": estimated_fidelities,
        "alloc_by_path": alloc_by_path, "est_fid_by_path": est_fid_by_path, "bounces": list(bounces),
        "C_const": C_const, "delta": delta, "min_sets": min_sets
    }
    base = (bool(correctness), int(cost), best_path_fid)
    if return_details:
        base += (alloc_by_path, est_fid_by_path)
    return (*base, state)

def lonline_continue(
    network, C_budget, *, state, return_details=False,
    C_const=None, delta=None, min_sets=None
):
    """
    集中的活用フェーズ。state を引き継ぎ s=2 以降を「フェーズ単位」で実施。
    1フェーズ分の均等投入コストが入らない場合は何も実行せず insufficient_budget=True を返す。
    出力:
      correctness, cost, best_path_fidelity, [alloc_by_path, est_fid_by_path,] new_state, insufficient_budget
    """
    # 引き継ぎ
    s = int(state.get("s", 1))
    candidate_set = list(state.get("candidate_set", []))
    estimated_fidelities = dict(state.get("estimated_fidelities", {}))
    alloc_by_path = dict(state.get("alloc_by_path", {}))
    est_fid_by_path = dict(state.get("est_fid_by_path", {}))
    bounces = list(state.get("bounces", []))

    C_const = state.get("C_const", 0.01) if C_const is None else C_const
    delta   = state.get("delta", 0.1)    if delta   is None else delta
    min_sets = state.get("min_sets", 4)  if min_sets is None else min_sets

    cost = 0
    if not candidate_set or C_budget <= 0 or len(candidate_set) <= 1:
        best_path_fid = None
        if estimated_fidelities:
            best_path = max(estimated_fidelities, key=estimated_fidelities.get)
            best_path_fid = estimated_fidelities[best_path]
            correctness = (best_path == getattr(network, "best_path", None))
        else:
            correctness = False
        base = (bool(correctness), int(cost), best_path_fid)
        if return_details:
            base += (alloc_by_path, est_fid_by_path)
        return (*base, {**state, "s": s}, False)

    c_B = sum(bounces) if sum(bounces) > 0 else 1
    insufficient_budget = False

    while cost < C_budget and len(candidate_set) > 1:
        s += 1
        Ns = _ns_for_round(s, len(candidate_set), C_const, delta, min_sets)

        # 候補全リンクに一律 Ns セット（途中打ち切りなし）
        round_cost_all = len(candidate_set) * Ns * c_B
        if cost + round_cost_all > C_budget:
            insufficient_budget = True
            s -= 1
            break

        sample_times = {h: int(Ns) for h in bounces}
        p_s, measured = {}, []
        for path in list(candidate_set):
            p, used = network.benchmark_path(path, bounces, sample_times)
            cost += int(used)
            fidelity = p + (1 - p) / 2.0
            estimated_fidelities[path] = fidelity
            p_s[path] = p
            measured.append(path)
            alloc_by_path[int(path)] = alloc_by_path.get(int(path), 0) + int(used)
            est_fid_by_path[int(path)] = float(fidelity)

        if not p_s:
            break

        p_max = max(p_s.values())
        new_cand = [path for path in measured if (p_s[path] + 2 ** (-s) > p_max - 2 ** (-s))]
        candidate_set = new_cand or candidate_set

    best_path_fid = None
    if estimated_fidelities:
        best_path = max(estimated_fidelities, key=estimated_fidelities.get)
        best_path_fid = estimated_fidelities[best_path]
        correctness = (best_path == getattr(network, "best_path", None))
    else:
        correctness = False

    new_state = {
        "s": s, "candidate_set": candidate_set, "estimated_fidelities": estimated_fidelities,
        "alloc_by_path": alloc_by_path, "est_fid_by_path": est_fid_by_path, "bounces": bounces,
        "C_const": C_const, "delta": delta, "min_sets": min_sets
    }
    base = (bool(correctness), int(cost), best_path_fid)
    if return_details:
        base += (alloc_by_path, est_fid_by_path)
    return (*base, new_state, insufficient_budget)

def _dry_phase_cost(state, C_budget, C_const=None, delta=None, min_sets=None):
    s = int(state.get("s", 1))
    k = len(state.get("candidate_set", []))
    bounces = state.get("bounces", [])
    c_B = sum(bounces) if bounces else 1
    C_const = state.get("C_const", 0.01) if C_const is None else C_const
    delta   = state.get("delta", 0.1)    if delta   is None else delta
    min_sets = state.get("min_sets", 4)  if min_sets is None else min_sets
    def Ns(s, k):
        val = math.ceil(C_const * (2**(2*s)) * math.log2(max((2**s)*k/delta, 2)))
        return max(val, min_sets)
    need_s2 = k * Ns(2, k) * c_B
    need_s3 = k * Ns(3, k) * c_B
    return dict(s=s, k=k, c_B=c_B, need_s2=need_s2, need_s3=need_s3, C_budget=int(C_budget))