shun-quantum-icc/paper.tex

% -*- japanese-LaTeX -*-
% 
% 
% Copyright (c) 2016, Hiroyuki Ohsaki.
% All rights reserved.
% 
% $Id: paper.tex,v 1.4 2020/08/27 16:31:45 ohsaki Exp ohsaki $
% 


\documentclass[conference, dvipdfmx, a4paper]{IEEEtran}
%% \documentclass[twocolumn,dvipdfmx, a4paper]{ieicejsp}


\usepackage{cite} \usepackage{insertfig} \usepackage{times}
\usepackage{url} \usepackage{revhistory} \usepackage{amsmath}
\usepackage{float} \usepackage{comment} \usepackage{algorithm,
  algpseudocode}

%% insertfigでは無く
% IEEEフォーマットで一般的に使用されるパッケージ
%% \usepackage{cite}
%% \usepackage[dvipdfmx]{graphicx} % 図の挿入
%% \usepackage{amsmath} % 高度な数式表現
%% \usepackage{url} % URLの表示
%% \usepackage{algorithm, algpseudocode} % アルゴリズムの記述

%% \importrevisions

%% \makeatletter \renewcommand{\thesection}{\@arabic\c@section}
%% \renewcommand{\thesubsection}{\thesection.\,\@arabic\c@subsection}
%% \renewcommand{\ext@subfigure}{lof} \renewcommand{\baselinestretch}{.6}
%% \makeatother



%% \title{{\bf 通信需要を考慮した量子ネットワークの\\リンク忠実度計測手法
%%     に関する一検討}\\ {\normalsize  A Study on Link Fidelity Measurement in Quantum Networks Considering Communication Demand }}

% サブタイトルは設けず、メインタイトルに統一する。 → 最後に英語にする
\title{通信需要を考慮した量子ネットワークのリンク忠実度計測手法}

%% \author{
%%   山近 駿   $^1$ \\ Shun Yamachika \and
%%   柿原 悠人 $^2$ \\ Yuto Kakihara \and
%%   井上 翔太 $^2$ \\ Shota Inoue \and
%%   大崎 博之 $^2$ \\ Hiroyuki Ohsaki
%% }

%% \affliate{
%%   関西学院大学 工学部 情報工学課程 $^1$ \\
%%   Department of Computer Science, School of Engineering, Kwansei Gakuin University \\  
%%   関西学院大学 大学院理工学部研究科 情報工学専攻 $^2$ \\
%%   Department of Informatics, Graduate School of Science and
%%   Technology, Kwansei Gakuin University \\
%% }%% fixme: 所属が正しいか確認しておいてください。 -shota

% --- 著者情報 ---
% IEEE指定のフォーマットで著者と所属を記述します。
\author{
    \IEEEauthorblockN{山近 駿\IEEEauthorrefmark{1}, 柿原 悠人\IEEEauthorrefmark{2}, 井上 翔太\IEEEauthorrefmark{2}, 大崎 博之\IEEEauthorrefmark{2}}
    \IEEEauthorblockA{\IEEEauthorrefmark{1}関西学院大学 工学部 情報工学課程}
    \IEEEauthorblockA{\IEEEauthorrefmark{2}関西学院大学 大学院理工学部研究科 情報工学専攻}
    % 通常は連絡先Emailを記載します
    % \IEEEauthorblockA{Email: \IEEEauthorrefmark{1}shun@lsnl.jp, \IEEEauthorrefmark{2}\{yuto, shota, ohsaki\}@lsnl.jp}
}

%% \renewcommand{\baselinestretch}{0.005}

\usepackage[T1]{fontenc} % bibの特殊な文字を読みこむためのやつ

\begin{document}
\setlength{\parskip}{0.2pt}  % 段落間の余白をゼロにする

\maketitle

% --- 概要 (Abstract) ---
\begin{abstract} % 最後に直します。
本研究では、量子ネットワークにおけるリンク忠実度計測の問題に対し、通信
経路ごとの重要度（通信需要）を考慮した新たな資源配分手法を提案する。従
来のリンク品質推定問題を発展させ、各経路の重要度と推定忠実度の積で定義
される「価値」の総和を最大化する問題として定式化する。この問題に対する
効率的な近似解法として、広域的な探索と集中的な活用から成る二段階貪欲法
を提案する。シミュレーション評価を通じて、提案手法が限られた測定資源の
下で、通信需要を考慮しない従来のアプローチに比べてネットワーク全体の総
価値を効率的に向上させることを示す。

\end{abstract}

% --- キーワード ---
\begin{IEEEkeywords}
量子ネットワーク, 忠実度計測, 資源配分, 通信需要, 貪欲法
\end{IEEEkeywords}

\section{はじめに}
%% ### トピックセンテンス

%% 1.  量子コンピュータ間を接続する量子ネットワークは、次世代の通信基盤として大きな期待が寄せられている。
%% 2.  量子ネットワーク上で高信頼な通信を実現するには、経由する物理リンクが高い忠実度を保つことが不可欠である。
%% 3.  したがって、ネットワーク内に存在する多数の物理リンクの中から、忠実度の高いものを効率的に選択する技術が極めて重要となる。
%% 4.  しかし、各リンクの忠実度を正確に推定するには多数回の量子測定が必要となり、その測定コストが実用上の大きな制約となる。
%% 5.  限られた測定資源をいかに効率的に配分し、高忠実度なリンクを特定するかが重要な課題である。
%% 6.  この課題に対する有望な解決策として、測定コストを削減しつつ高忠実度リンクを特定する LinkSelFiE が提案されている。
%% 7.  LinkSelFiE は、統計的な探索アルゴリズムを用いることで、最も忠実度の高いリンクを効率的に特定する優れた手法である。
%% 8.  一方で、LinkSelFiE の問題設定では、全ての通信経路候補が均等な重要度を持つことを前提としている。
%% 9.  実際のネットワーク運用では、アプリケーションの要求などに応じて通信経路ごとに重要度は異なり、均等に扱うことが最善とは限らない。
%% 10. ネットワーク全体の価値を最大化するためには、各通信経路の重要度、すなわち通信需要を考慮した資源配分が求められる。
%% 11. LinkSelFiE は優れたリンク特定手法であるが、通信需要という新たな指標を組み合わせることで、さらに実用性を高められる可能性がある。
%% 12. そこで本研究では、通信需要の概念を導入し、測定資源をより価値の高い通信経路へ優先的に配分する新たな手法を提案する。
%% 13. 具体的には、各通信経路の重要度と推定忠実度の積をその経路の価値と定義し、ネットワーク全体の総価値を最大化する問題として定式化する。
%% 14. この問題に対し、本稿では効率的な近似解法として、広域的な探索と集中的な活用から成る二段階貪欲法を提案する。

量子コンピュータ間を接続する量子ネットワークは、次世代の通信基盤として
大きな期待が寄せられている。複数の量子プロセッサを大規模に連携させる分
散量子計算や、物理的な限界を超えたセンシング精度の実現など、単一の量子
デバイスでは達成不可能な応用を可能にするためである。

量子ネットワーク上で高信頼な通信を実現するには、経由する物理リンクが高
い忠実度を保つことが不可欠である。量子情報は環境ノイズに対して極めて脆
弱であり、通信中に量子状態が破壊されやすい。そのため、量子もつれのよう
な繊細な相関を遠隔地へ配送する際には、経路上に存在する物理リンクの品質
が通信性能を直接的に決定づける。

したがって、ネットワーク内に存在する多数の物理リンクの中から、忠実度の
高いものを効率的に選択する技術が極めて重要となる。特に、複数の並列リン
クが存在する経路では、その中から最も通信品質の高いリンクを見つけ出し、
データ転送に利用することで、通信の成功確率を最大化できる。

しかし、各リンクの忠実度を正確に推定するには多数回の量子測定が必要とな
り、その測定コストが実用上の大きな制約となる。忠実度は確率的な量である
ため、その値を十分な精度で推定するには、同一の量子状態を何度も送受信し、
統計を取る必要がある。このプロセスは、時間や量子ビットといった貴重な計
算資源を大量に消費する。

限られた測定資源をいかに効率的に配分し、高忠実度なリンクを特定するかが
重要な課題である。全てのリンク候補に対して十分な回数の測定を行うことは、
ネットワークの規模が大きくなるにつれて現実的でなくなる。このため、測定
コストと推定精度のトレードオフを考慮した、賢明な資源配分戦略が不可欠と
なる。

この課題に対する有望な解決策として、測定コストを削減しつつ高忠実度リン
クを特定する LinkSelFiE が提案されている\cite{Liu24:INFOCOM}。
LinkSelFiE は、多腕バンディット問題にヒントを得たアルゴリズムであり、
有望なリンクを集中的に測定し、見込みの薄いリンクの測定を早期に打ち切る
ことで、全体の測定回数を削減する。

LinkSelFiE は、統計的な探索アルゴリズムを用いることで、最も忠実度の高
いリンクを効率的に特定する優れた手法である。これにより、従来法では膨大
なコストを要した高忠実度リンクの特定を、現実的な資源の範囲内で実現する
道が拓かれた。

一方で、LinkSelFiE の問題設定では、全ての通信経路候補が均等な重要度を
持つことを前提としている。これは、単一のノードペア間に存在する複数の並
列リンクの中から、純粋に最も忠実度の高いリンクを一つ選択するという問題
に特化しているため、自然な定式化である。

実際のネットワーク運用では、アプリケーションの要求などに応じて通信経路
ごとに重要度は異なり、均等に扱うことが最善とは限らない。例えば、誤り訂
正符号の検証といった基幹的なタスクに用いる通信経路と、優先度の低い補助
的なデータ転送に用いる経路とでは、品質保証に割くべき測定資源の量は自ず
と異なるはずである。

ネットワーク全体の価値を最大化するためには、各通信経路の重要度、すなわ
ち通信需要を考慮した資源配分が求められる。重要度の低いリンクの忠実度を
高精度に推定するよりも、重要度の高いリンクの品質を優先的に保証する方が、
システム全体として得られる便益は大きくなる。

LinkSelFiE は優れたリンク特定手法であるが、通信需要という新たな指標を
組み合わせることで、さらに実用性を高められる可能性がある。つまり、
LinkSelFiE が持つ効率的なリンク特定能力を、通信需要に基づいて重み付け
された問題設定に適用することで、より現実の要求に即した資源配分が実現で
きると考えられる。

そこで本研究では、通信需要の概念を導入し、測定資源をより価値の高い通信
経路へ優先的に配分する新たな手法を提案する。これにより、限られた測定資
源から得られる全体的な価値の向上を目指す。

具体的には、各通信経路の重要度と推定忠実度の積をその経路の価値と定義し、
ネットワーク全体の総価値を最大化する問題として定式化する。この定式化は、
単に最も忠実度の高いリンクを見つけるだけでなく、それがどれだけ重要かと
いう側面も同時に考慮するものである。

本研究の問いは以下のとおりである。
\begin{itemize}

\item 限られた測定資源の制約下で、各通信経路の重要度を考慮した効率的な
  リンク忠実度の測定戦略は、いかにして設計できるか。
  
\item 広域的な品質の初期推定と、有望なリンクへの集中的な資源投下を組み
  合わせることで、測定効率を最大化する準最適な配分手法を構築できるか。

\item 通信需要と推定忠実度の積として定義されるネットワーク全体の総価値
  を、提案手法によって最大化し、システムの全体性能を向上させられるか。
  
\end {itemize}  

この問題に対し、本稿では効率的な近似解法として、広域的な探索と集中的な
活用から成る二段階貪欲法を提案する。本手法は、まず限られた資源で全リン
クを大局的に調査し、次いで得られた知見に基づき、価値が高いと見込まれる
有望な経路の調査に資源を集中させる。シミュレーション実験を通じて、提案
手法が従来のアプローチに比べてネットワーク全体の総価値を効率的に向上さ
せることを示す。


本研究の貢献は以下のとおりである。
\begin{itemize}

\item 通信需要を定量的な重みとして導入し、各通信経路の重要度と忠実度の
  積をその経路の価値と定義することで、ネットワーク全体の総価値を最大化
  する新たな資源配分問題として定式化した。
  
\item 近似解法として全リンクを低コストで探索する第一段階と、価値が高い
  と見込まれるリンク群に資源を集中させる第二段階から成る、二段階貪欲法
  を提案した。
  
\item シミュレーション評価により、提案手法が既存手法と比較して常に高い
  総価値を達成し、特にネットワーク規模が大きく資源制約が厳しい状況にお
  いて、その優位性が顕著になることを定量的に実証した。
  
\end {itemize}  

本稿の構成は以下の通りである。 % 最後に直します
%% 2章で本研究の関連研究について述べる。3章では通信需要を考慮したリン
%% ク忠実度計測問題を定式化する。4章では提案手法二段階貪欲法(Two-Phase
%% Greedy)について述べる。

\section{関連研究}
%% 量子ネットワークにおける高信頼な通信の実現には、その構成要素である量子
%% ゲートや物理リンクの品質を正確に評価するベンチマーキング技術が不可欠で
%% ある。

%% 個々の量子ゲートの品質評価手法として最も広く用いられているのが、ランダ
%% ム化ベンチマーキングである。

%% ランダム化ベンチマーキングは強力な手法である一方、その適用範囲や推定精
%% 度には理論的な限界も存在することが知られている。

%% ゲートレベルの評価に加えて、近年ではネットワーク全体の性能を評価するた
%% めのベンチマーキング手法も提案されている。

%% 本研究が取り組むリンク忠実度推定は、多腕バンディット問題として定式化で
%% きる。

%% 多腕バンディット問題の枠組みを量子ネットワークのリンク選択に応用した先
%% 行研究として、本研究の直接的な基礎となる LinkSelFiE が存在する。

%% LinkSelFiE の問題設定をさらに発展させ、ネットワーク全体の経路選択へと
%% 応用範囲を広げる研究も活発に進められている。

%% これらの研究の理論的基盤である多腕バンディット問題、特に最適アーム識別
%% は、それ自体が機械学習分野の重要な研究課題として深く研究されてきた。

%% 本研究におけるシミュレーション評価では、量子ネットワークの研究開発で広
%% く利用されている NetSquid シミュレータを用いた。

本章では、本研究の背景となる関連研究を概観する。まず、量子システムの品
質評価手法であるベンチマーキング技術について述べ、特にランダム化ベンチ
マーキングとその発展に焦点を当てる。次に、本研究の核心であるリンク・経
路選択問題に関する近年の動向を解説し、最後に、これらの研究の理論的基盤
である多腕バンディット問題に関する基礎的な研究を紹介する。

量子ネットワークにおける高信頼な通信の実現には、その構成要素である量子
ゲートや物理リンクの品質を正確に評価するベンチマーキング技術が不可欠で
ある。量子状態はノイズに対して極めて脆弱であるため、通信や計算の過程で
発生するエラーの大きさを定量的に把握し、制御することが極めて重要となる。
このため、システムの性能を客観的な指標で評価するための標準的な手法が長
年にわたり研究されてきた。

個々の量子ゲートの品質評価手法として最も広く用いられているのが、ランダ
ム化ベンチマーキング (Randomized Benchmarking, RB) である
\cite{Knill2008_RB}。RBは、ランダムに選ばれた一連のクリフォードゲート
を量子ビットに適用し、その最終状態を測定することで、ゲート操作全体の平
均エラー率を推定する。この手法の利点は、状態準備や測定におけるエラー
(State Preparation and Measurement error, SPAM error) の影響を受けにく
く、特定のゲートセットに対する忠実度を頑健に評価できる点にある。RBは単
一量子ビットゲートの評価手法として確立されており、多量子ビットシステム
への拡張も研究されている \cite{Helsen2017_MultiqubitRB}。

しかし、ランダム化ベンチマーキングは強力な手法である一方、その適用範囲
や推定精度には理論的な限界も存在することが知られている。例えば、RBが正
確なエラー率を与えるためには、ノイズが時間に依存せず、かつゲートに依存
しないといった仮定が必要となる \cite{Epstein2014_LimitsRB}。現実のデバ
イスでは、クロストークや時間的に変動するノイズなど、これらの仮定から外
れるエラー源が存在するため、RBによる評価結果の解釈には注意を要する。

ゲートレベルの評価に加えて、近年ではネットワーク全体の性能を評価するた
めのベンチマーキング手法も提案されている \cite{Helsen2023_NB}。ネット
ワークにおいては、個々のゲート品質だけでなく、ノード間のリンク品質やも
つれ配送プロトコルの性能が重要となる。Helsenらが提案した手法は、ネット
ワーク全体を一つのブラックボックスと見なし、特定のタスクを実行させた際
の性能を評価することで、より実用に近い形での品質評価を可能にする。これ
は、単一コンポーネントの評価から、システム全体の機能評価へと視点を広げ
る重要な取り組みである。

本研究が取り組むリンク忠実度推定は、限られた測定資源を用いて最も品質の
高いリンクを特定する問題であり、不確実性の下での逐次的意思決定問題であ
る多腕バンディット問題 (Multi-Armed Bandit, MAB) として定式化できる。
MABは、未知の確率分布に従う報酬を生成する複数の選択肢（アーム）の中か
ら、総報酬を最大化するように試行を繰り返す問題の総称である。リンク忠実
度推定の文脈では、各リンクがアームに、忠実度の測定がアームを引く行為に、
そして測定結果が報酬に相当する。

多腕バンディット問題の枠組みを量子ネットワークのリンク選択に応用した先
行研究として、本研究の直接的な基礎となる LinkSelFiE が存在する
\cite{Liu24:INFOCOM}。LinkSelFiEは、複数の並列リンクの中から最も忠実度
の高いリンクを効率的に特定するためのアルゴリズムである。有望なリンクを
適応的に追加測定し、品質の低いリンクの測定を早期に打ち切ることで、全体
の測定コストを大幅に削減することを可能にした。しかし、LinkSelFiEの問題
設定は単一のノードペア間に限定されており、ネットワーク全体の通信需要の
異質性を考慮していない。本研究は、このLinkSelFiEの考え方を拡張し、経路
ごとの重要度を導入する点で新規性を有する。

LinkSelFiEの問題設定をさらに発展させ、ネットワーク全体の経路選択へと応
用範囲を広げる研究も活発に進められている。例えば、量子版のBGP (Border
Gateway Protocol) を想定し、ネットワークベンチマーキングを通じてオンラ
インで最適経路を選択する研究 \cite{Liu2024_QBGP} や、機械学習の手法を
用いて最適な量子通信経路を学習する研究
\cite{Wang2025_LearningBestPaths} が報告されている。これらの研究は、単
一リンクの品質評価から、より大規模で動的なネットワークにおける経路全体
の最適化へと関心が移行していることを示しており、本研究とも共通の方向性
を持つ。

これらの研究の理論的基盤である多腕バンディット問題、特に最適アーム識別
(Best-Arm Identification, BAI) は、それ自体が機械学習分野の重要な研究
課題として深く研究されてきた \cite{Bubeck2012_RegretAnalysis}。BAIは、
試行回数の sonunda最も期待報酬の高いアームを特定することを目的とする
MABの一分野であり、固定予算設定や固定信頼度設定など、様々な問題設定が
提案されている \cite{Audibert10:COLT, Jamieson2014_BAI}。LinkSelFiEを
はじめとする多くのリンク選択手法は、これらのBAIアルゴリズムに着想を得
ており、本研究もこの理論的基盤の上に構築されている。

本研究におけるシミュレーション評価では、量子ネットワークの研究開発で広
く利用されている NetSquid シミュレータを用いた
\cite{Coopmans2021_NetSquid}。NetSquidは、量子ビットの物理的な振る舞い
から高レベルのプロトコルまでを統一的に記述できる、離散事象シミュレーショ
ンのフレームワークである。このような精緻なシミュレータの存在が、複雑な
量子ネットワークにおけるプロトコルの設計と性能評価を可能にしている。



\section{通信需要を考慮したリンク忠実度計測問題}
%% 本章では、本研究が解決を目指す通信需要を考慮したリンク忠実度計測問題
%% を数学的に定式化する。

%% 本問題では、単一の始点ノードと複数の終点ノードから成るスター型ト
%% ポロジの量子ネットワークを想定する。

%% 本問題への入力として、ネットワークトポロジ、各通信経路の重要度、利用可
%% 能な総測定予算、そして推定結果に要求される信頼区間精度が与えられる。

%% ここでの本質的な課題は、各リンクの忠実度が未知であるという不確実性の下
%% で、限られた測定資源をどのリンクにどれだけ配分するかを決定することにあ
%% る。

%% 本問題の出力は、測定資源の配分計画と、その結果として忠実度が十分な精度
%% で確定した発見済みの通信経路の集合である。

%% ある通信経路が発見済みであるとは、その経路内で最も忠実度の高いリンクの
%% 推定値が、要求された精度を満たす信頼区間幅を達成した状態として定義する。

%% 本問題の目的は、総測定コストが与えられた予算を超えないという制約の下で、
%% 発見済みの通信経路から得られる価値の総和を最大化することである。

%% 以上の目的と制約をまとめ、本研究が取り組む最適化問題を定義する。

本章では、本研究が解決を目指す通信需要を考慮したリンク忠実度計測問題
を数学的に定式化する。本研究では、従来のリンク品質推定問題を拡張し、通
信経路ごとに異なる重要度、すなわち通信需要を考慮に入れる。これにより、
単に物理的な品質が高いリンクを見つけ出すだけでなく、限られた測定資源を
用いてネットワーク全体の運用価値を最大化するという、より実践的な課題設
定を取り扱う。

本問題では、単一の始点ノード $S$ と $N$ 個の終点ノード $D_n$ ($n=1,
\dots, N$) から成るスター型トポロジの量子ネットワークを想定する。各ノー
ドペア $(S, D_n)$ 間には、それぞれ複数の並列な物理リンクから成るリンク
集合 $L_n = \{l_{n1}, l_{n2}, \dots, l_{n|L_n|}\}$ が存在すると仮定す
る。各リンク $l_{nj} \in L_n$ の真の忠実度 $f_{nj} \in [0, 1]$ は未知
であり、量子測定を繰り返すことによってのみ、その値を統計的に推定できる。

本問題への入力として、ネットワークトポロジ、各通信経路の重要度、利用可
能な総測定予算、そして推定結果に要求される信頼区間精度が与えられる。各
ノードペア $(S, D_n)$ の重要度 $I_n \in [0, 1]$ は、その通信経路が担う
タスクの優先度やアプリケーションの要求品質を反映する重みであり、これが
本稿における通信需要に相当する。総測定予算 $C$ は、忠実度の推定に費や
すことができる測定操作の総コストの上限を定める。さらに、推定忠実度の信
頼性を保証するためのパラメータとして、許容誤差 $y > 0$ が与えられる。
この許容誤差 $y$ は、推定忠実度の信頼区間幅に関する要求精度を規定する
ものである。

ここでの課題は、各リンクの忠実度が未知であるという不確実性の下で、限ら
れた測定資源をどのリンクにどれだけ配分するかを決定することにある。すな
わち、どのノードペアの、どのリンクに対して、何回の測定を行うかという配
分戦略を導出することが求められる。精度の高い忠実度推定には多くの測定コ
ストを要するため、全てのリンクの品質を完全に、かつ高い信頼性をもって把
握することは、特にネットワーク規模が大きい場合には現実的ではない。した
がって、重要度と品質の両面から価値が高いと見込まれる通信経路を選択的に
調査する資源配分戦略が不可欠となる。

本問題の出力は、測定資源の配分計画と、その結果として忠実度が十分な精度
で確定した発見済みの通信経路の集合である。具体的には、各リンク
$l_{nj}$ への測定回数を $a_{nj}$ としたとき、その配分計画全体
$\{a_{nj}\}$ が一つの出力となる。この配分計画に基づき各リンクの忠実度
を推定した結果、後述する発見条件を満たしたノードペアの集合
$S_{\text{sel}} \subseteq \{1, \dots, N\}$ が、もう一つの主要な出力と
なる。

ある通信経路が発見済みであるとは、その経路内で最も忠実度の高いリンクの
推定値が、要求された精度を満たす信頼区間幅を達成した状態として定義する。
ノードペア $n$ 内のリンク集合 $L_n$ の中で、最も忠実度が高いと推定され
たリンクを $l^*_{n}$ とし、その推定忠実度を $\hat{f}^*_n$ とする。この
推定値は確率変数であり、その信頼性は信頼区間 $[\text{LCB}^*_n,
  \text{UCB}^*_n]$ によって評価される。ここで $\text{LCB}^*_n$ と
$\text{UCB}^*_n$ は、それぞれ信頼区間の下限値と上限値を示す。この信頼
区間幅 $x_n = \text{UCB}^*_n - \text{LCB}^*_n$ が、入力として与えられ
た許容誤差 $y$ に対応する閾値 $x_{\text{thresh}}(y)$ 以下になった場合
に、ノードペア $n$ は発見済みであると見なす。すなわち、発見条件は以下
のように表される。
\begin{align}
    n \in S_{\text{sel}} \iff (\text{UCB}^*_n - \text{LCB}^*_n) \leq
    x_{\text{thresh}}(y)
\end{align}
この条件は、推定忠実度 $\hat{f}^*_n$ が、十分に信頼できる精度で確定し
たことを意味する。

本問題の目的は、総測定コストが与えられた予算を超えないという制約の下で、
発見済みの通信経路から得られる価値の総和を最大化することである。あるノー
ドペア $n$ が発見されたとき、その経路から得られる価値は、経路の重要度
$I_n$ と、その経路で利用可能な最良リンクの推定忠実度 $\hat{f}^*_n$ の
積 $I_n \hat{f}^*_n$ として定義される。したがって、本問題は、発見済み
の集合 $S_{\text{sel}}$ に含まれる全てのノードペアの価値の総和を最大化
する問題として定式化される。

以上の目的と制約をまとめ、本研究が取り組む最適化問題を定義する。各リン
ク $l_{nj}$ の忠実度推定に要した測定コストを $\text{Cost}(l_{nj})$ と
すると、問題は以下のように記述される。
\begin{align}
    \text{maximize} \quad & \sum_{n \in S_{\text{sel}}} I_n
    \hat{f}^*_n \label{eq:objective} \\ \text{subject to} \quad &
    \sum^N_{n=1} \sum_{l_{nj} \in L_n} \text{Cost}(l_{nj}) \leq
    C \label{eq:constraint1} \\ & n \in S_{\text{sel}} \iff
    (\text{UCB}^*_n - \text{LCB}^*_n) \leq
    x_{\text{thresh}}(y) \label{eq:constraint2}
\end{align}
ここで式(\ref{eq:objective})は最大化すべき目的関数、式
(\ref{eq:constraint1})は総測定予算に関する資源制約、式
(\ref{eq:constraint2})は通信経路の発見条件を示す。この定式化は、単に最
も忠実度の高いリンクを見つけるだけでなく、それがどれだけ重要かという側
面を同時に考慮するものである。



\section{提案手法 : 二段階貪欲法(Two-Phase Greedy)による資源配分}
%% 本章では、前章で定式化した通信需要を考慮したリンク忠実度計測問題に対し、
%% 効率的な近似解法である二段階貪欲法を提案する。

%% 本手法は、大局的な品質分布を把握する広域探索フェーズと、有望な経路に資
%% 源を集中させる集中的活用フェーズの二段階で構成される。

%% はじめに、本手法への入力と、最終的に得られる出力を明確に定義する。

%% 第一段階である広域探索フェーズでは、総測定予算の一部を全てのノードペア
%% に均等に配分し、各経路におけるリンク忠実度の初期推定値を低コストで取得
%% する。

%% 第二段階である集中的活用フェーズでは、第一段階で得られた初期推定値と各
%% 経路の重要度に基づき、残りの測定資源を価値の高い経路から順に、貪欲に配
%% 分する。

%% 以上の二段階処理により、本手法は限られた測定資源をネットワーク全体の価
%% 値が最大となるよう効率的に配分することを目指す。

本章では、前章で定式化した通信需要を考慮したリンク忠実度計測問題に対し、
効率的な近似解法である二段階貪欲法 (Two-Phase Greedy) を提案する。本手
法は、組合せ最適化問題に対する実用的なヒューリスティック解法として、解
の品質と計算コストのバランスを考慮して設計されている。特に、大規模なネッ
トワークにおいて全てのリンクの忠実度を正確に測定することが現実的でない
状況を想定し、限られた測定資源を準最適に配分することを目指す。

本手法は、大局的な品質分布を把握する広域探索フェーズと、有望な経路に資
源を集中させる集中的活用フェーズの二段階で構成される。最初にネットワー
ク全体を広く浅く調査することで有望な領域を見定め、次いでその領域を集中
的に調査するという戦略は、探索空間が広大な問題において有効なアプローチ
である。これにより、測定資源が価値の低いリンクの精密な調査に浪費される
ことを防ぎ、ネットワーク全体の総価値を効率的に高めることが期待できる。

はじめに、本手法への入力と、最終的に得られる出力を明確に定義する。本手
法への入力は以下の通りである。
\begin{itemize}
    \item ネットワークトポロジ: 始点ノード $S$、終点ノード集合
      $\{D_n\}_{n=1}^N$、および各ノードペア $(S, D_n)$ 間に存在する物
      理リンクの集合 $L_n$。
    \item 通信需要: 各ノードペア $(S, D_n)$ の重要度 $I_n \in [0, 1]$。
    \item 測定予算: 利用可能な総測定コストの上限 $C$、および広域探索
      フェーズで各ノードペアに割り当てる初期測定コスト
      $C_{\text{init}}$。
\end{itemize}
一方、本手法の出力は、各ノードペア $n$ について、その中で最も忠実度が
高いと最終的に判断されたリンクの推定忠実度 $\hat{f}^*_n$ である。

第一段階である広域探索フェーズでは、総測定予算の一部を全てのノードペア
に均等に配分し、各経路におけるリンク忠実度の初期推定値を低コストで取得
する。具体的には、各ノードペア $(S, D_n)$ 内のリンク集合 $L_n$ に対し、
それぞれ初期測定コスト $C_{\text{init}}$ を上限として忠実度測定を実行
する。この測定は、先行研究であるLinkSelFiE \cite{Liu24:INFOCOM} のよう
な逐次的な最適アーム識別手法を用いて行われる。$C_{\text{init}}$ を消費
するか、あるいは最も忠実度の高いリンクが特定できた時点で測定を打ち切り、
その時点での最良リンクの推定忠実度を初期推定値
$\hat{f}^{\text{init}}_n$ とする。このフェーズの目的は、あくまでネット
ワーク全体の品質傾向を低コストで把握することにあるため、
$C_{\text{init}}$ は比較的小さな値に設定される。

第二段階である集中的活用フェーズでは、第一段階で得られた初期推定値と各
経路の重要度に基づき、残りの測定資源を価値の高い経路から順に、貪欲に配
分する。まず、全ノードペア $n$ に対して、その経路がもたらす価値の期待
値を表す価値スコア $V_n = I_n \times \hat{f}^{\text{init}}_n$ を計算す
る。次に、この価値スコア $V_n$ が高い順にノードペアを整列させる。そし
て、総測定予算の残り $C_{\text{remain}} = C - \sum_n (\text{消費コス
  ト}_n^{\text{init}})$ を、整列された順序に従って各ノードペアに割り当
てていく。すなわち、最も価値スコアの高いノードペアから順に、残りの予算
の全てを投じて再度LinkSelFiEによる忠実度測定を実行し、より精度の高い推
定値 $\hat{f}^*_n$ を得る。これを予算が尽きるまで、あるいは全てのノー
ドペアの再測定が完了するまで繰り返す。一度も第二段階の測定対象とならな
かったノードペアについては、初期推定値 $\hat{f}^{\text{init}}_n$ を最
終的な推定忠実度 $\hat{f}^*_n$ とする。

以上の二段階処理により、本手法は限られた測定資源をネットワーク全体の価
値が最大となるよう効率的に配分することを目指す。広域探索によって有望な
経路を大局的に特定し、活用フェーズでそれらの経路の忠実度推定精度を集中
的に高めるという貪欲戦略は、計算コストを現実的な範囲に抑制しつつ、高品
質な解を得るための有効な近似解法である。


\section{実験}
%% 本章では、提案手法である二段階貪欲法の有効性を定量的に評価するため、量
%% 子ネットワークシミュレータを用いて行った計算機シミュレーションの詳細と、
%% その評価結果について述べる。

%% 本シミュレーションの目的は、限られた測定予算の制約下において、提案手法
%% が比較手法よりも効率的にネットワーク全体の総価値を最大化できることを示
%% すことにある。

%% 評価には、量子ネットワークの研究開発で広く用いられているシミュレータ
%% NetSquidを用い、1つの始点ノードと複数の終点ノードから成るスター型トポ
%% ロジを想定した。

%% 実験では、品質の異なる物理リンクが混在し、かつ通信経路ごとに重要度が異
%% なる、より現実的な状況を模倣するためのパラメータ設定を用いた。

%% 提案手法の有効性を明らかにするため、測定資源をネットワーク全体に均等に
%% 配分する二つの基本的な手法を比較対象とした。

%% 評価指標には、各通信経路の重要度と最終的に選択されたリンクの推定忠実度
%% の積を、全ての通信経路について合計したネットワーク総価値スコアを用いた。

%% まず、隣接ノード数が3の場合、提案手法はいずれの測定予算においても比較
%% 手法を一貫して上回る総価値を達成した。

%% この結果は、提案手法が通信需要の高い経路へ優先的に資源を配分することで、
%% 特に測定予算が限られる初期段階で高い投資対効果を実現していることを示唆
%% する。

%% 次に、隣接ノード数を5に増加させた場合、提案手法と比較手法との性能差は
%% さらに拡大する傾向が見られた。

%% 探索対象となるリンク数が増加したことで資源配分の効率性がより重要となり、
%% 通信需要とリンク品質の初期推定値に基づいて資源を集中させる提案手法の優
%% 位性がより顕著に現れたものと考えられる。

%% 以上の結果から、提案手法は、ネットワークの規模や利用可能な測定予算によ
%% らず、通信需要を考慮した効率的な資源配分によってネットワーク全体の価値
%% を最大化する上で高い有効性を持つことが示された。


本章では、提案手法である二段階貪欲法の有効性を定量的に評価するため、量
子ネットワークシミュレータを用いて行った計算機シミュレーションの詳細と、
その評価結果について述べる。

本シミュレーションの目的は、限られた測定予算の制約下において、提案手法
が比較手法よりも効率的にネットワーク全体の総価値を最大化できることを示
すことにある。そのために、総測定予算を変化させた際のネットワーク総価値
スコアの推移を計測し、提案手法と二つの比較手法との性能を比較評価する。

評価には、量子ネットワークの研究開発で広く用いられているシミュレータ
NetSquid \cite{Coopmans2021_NetSquid} を用い、1つの始点ノードと複数の
終点ノードから成るスター型トポロジを想定した。本評価では、ネットワーク
規模の指標となる隣接ノード数を3 ($N=3$) および5 ($N=5$) とした二種類の
トポロジを対象とした。

実験では、品質の異なる物理リンクが混在し、かつ通信経路ごとに重要度が異
なる、より現実的な状況を模倣するためのパラメータ設定を用いた。具体的に
は、各ノードペア $(S, D_n)$ 間には5本の独立な物理リンクが存在すると仮
定する。このうち1本のリンクの平均忠実度を0.95、残りの4本の平均忠実度を
0.85とし、それぞれ正規分布に従って忠実度の真値を設定した。これは、高品
質なリンクと標準的な品質のリンクが混在する状況を表現するためである。ま
た、各ノードペアの重要度 $I_n$ は、区間 $[0, 1]$ 上の一様乱数により生
成した。

提案手法である二段階貪欲法では、広域探索フェーズで各ノードペアに初期測
定コスト $C_{\text{init}}=40$ を割り当て、初期推定値を得る。続く集中的
活用フェーズでは、初期推定値と重要度から算出される価値スコアに基づき、
残りの測定予算を価値の高いノードペアから順に配分する。各ノードペア内に
おける最良リンクの特定には、先行研究であるLinkSelFiE
\cite{Liu24:INFOCOM} を用いた。

提案手法の有効性を明らかにするため、測定資源をネットワーク全体に均等に
配分する二つの基本的な手法を比較対象とした。第一の比較手法
Uniform-LinkSelFiE は、総測定予算を全てのノードペアに均等に配分し、各
ペア内でLinkSelFiEを用いて最良リンクを特定する。第二の比較手法
Uniform-Naive は、総測定予算を全てのノードペア、かつ全ての物理リンクに
均等に配分し、得られた推定忠実度に基づいて最良リンクを選択する、最も単
純なアプローチである。

評価指標には、各通信経路の重要度 $I_n$ と最終的に選択されたリンクの推
定忠実度 $\hat{f}^*_n$ の積を、全ての通信経路について合計したネットワー
ク総価値スコアを用いた。この総価値スコアは、式 (1) で定義した本研究の
最適化対象そのものである。なお、シミュレーション結果の信頼性を担保する
ため、各測定予算の値について独立なシミュレーションを20回実施し、その平
均値と95\%信頼区間を算出した。

\begin{figure}[t]
  \centering \includegraphics[width=0.8\columnwidth]{graphA.eps}
  \caption{隣接ノード数が3の場合における測定予算と総価値スコアの関係}
  \label{fig:r3_rewritten}
  \vspace{1.5em} % 図の間の垂直方向のスペース
  \includegraphics[width=0.8\columnwidth]{graphC.eps} 
  \caption{隣接ノード数が5の場合における測定予算と総価値スコアの関係}
  \label{fig:r5_rewritten}
\end{figure}

まず、隣接ノード数が3の場合、提案手法はいずれの測定予算においても比較
手法を一貫して上回る総価値を達成した。図\ref{fig:r3_rewritten}に、総測
定予算を横軸に、ネットワーク総価値スコアを縦軸にとった結果を示す。図か
らわかるように、特に測定予算が小さい領域において、提案手法は比較手法に
比べて急峻に総価値を高めている。

この結果は、提案手法が通信需要の高い経路へ優先的に資源を配分することで、
特に測定予算が限られる初期段階で高い投資対効果を実現していることを示唆
する。有望な経路の忠実度推定に資源を集中させるため、少ない予算で効率的
にネットワーク全体の価値を向上できる。一方で、測定予算の増加に伴い、総
価値の上昇率は緩やかになる。これは、価値の高い経路の忠実度推定がある程
度収束した後は、追加の測定予算が相対的に価値の低い経路の推定精度向上に
用いられるため、全体価値への貢献が限定的になるためである。

次に、隣接ノード数を5に増加させた場合、提案手法と比較手法との性能差は
さらに拡大する傾向が見られた。図\ref{fig:r5_rewritten}は、隣接ノード数
が5の場合の結果を示す。隣接ノード数が3の場合と同様に、提案手法が最も高
い性能を示している。さらに、測定予算が増加するにつれて、提案手法と
Uniform-LinkSelFiEとの性能差が、図\ref{fig:r3_rewritten}の場合と比較し
てより大きく開いていることが確認できる。

探索対象となるリンク数が増加したことで資源配分の効率性がより重要となり、
通信需要とリンク品質の初期推定値に基づいて資源を集中させる提案手法の優
位性がより顕著に現れたものと考えられる。ネットワーク規模が拡大すると、
各リンクに配分できる平均的な測定予算は減少し、資源を闇雲に分散させる手
法では十分な推定精度を得ることが困難になる。このような状況において、提
案手法の戦略的な資源配分が効果的に機能した結果である。

以上の結果から、提案手法は、ネットワークの規模や利用可能な測定予算によ
らず、通信需要を考慮した効率的な資源配分によってネットワーク全体の価値
を最大化する上で高い有効性を持つことが示された。特に、資源制約が厳しい
状況や、大規模なネットワークにおいて、その有効性はより顕著となることが
期待される。

% \vspace{-0.4em}  % ← この行を追加（-0.8em 〜 -1.2em で調整）

\section*{謝辞}
本研究の一部は JSPS 科研費 24K02936 の助成を受けたものである。
% \vspace{-0.5em} % ← この行を追加
\renewcommand{\em}{\it} \bibliographystyle{ieeetr}
\bibliography{bib/quantum}
\end{document}