% -*- 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[twocolumn,dvipdfmx, a4paper]{ieicejsp} \usepackage{cite} \usepackage{insertfig} \usepackage{times} \usepackage{url} \usepackage{revhistory} \usepackage{amsmath} \usepackage{float} \usepackage{comment} \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 }} \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 \renewcommand{\baselinestretch}{0.005} \begin{document} \setlength{\parskip}{0.2pt} % 段落間の余白をゼロにする \maketitle \section{はじめに} %% ### トピックセンテンス %% 1. 量子コンピュータ間を接続する量子ネットワークは、次世代の通信基盤として大きな期待が寄せられている。 %% 2. 量子ネットワーク上で高信頼な通信を実現するには、経由する物理リンクが高い忠実度を保つことが不可欠である。 %% 3. したがって、ネットワーク内に存在する多数の物理リンクの中から、忠実度の高いものを効率的に選択する技術が極めて重要となる。 %% 4. しかし、各リンクの忠実度を正確に推定するには多数回の量子測定が必要となり、その測定コストが実用上の大きな制約となる。 %% 5. 限られた測定資源をいかに効率的に配分し、高忠実度なリンクを特定するかが重要な課題である。 %% 6. この課題に対する有望な解決策として、測定コストを削減しつつ高忠実度リンクを特定する LinkSelFiE が提案されている。 %% 7. LinkSelFiE は、統計的な探索アルゴリズムを用いることで、最も忠実度の高いリンクを効率的に特定する優れた手法である。 %% 8. 一方で、LinkSelFiE の問題設定では、全ての通信経路候補が均等な重要度を持つことを前提としている。 %% 9. 実際のネットワーク運用では、アプリケーションの要求などに応じて通信経路ごとに重要度は異なり、均等に扱うことが最善とは限らない。 %% 10. ネットワーク全体の価値を最大化するためには、各通信経路の重要度、すなわち通信需要を考慮した資源配分が求められる。 %% 11. LinkSelFiE は優れたリンク特定手法であるが、通信需要という新たな指標を組み合わせることで、さらに実用性を高められる可能性がある。 %% 12. そこで本研究では、通信需要の概念を導入し、測定資源をより価値の高い通信経路へ優先的に配分する新たな手法を提案する。 %% 13. 具体的には、各通信経路の重要度と推定忠実度の積をその経路の価値と定義し、ネットワーク全体の総価値を最大化する問題として定式化する。 %% 14. この問題に対し、本稿では効率的な近似解法として、広域的な探索と集中的な活用から成る二段階貪欲法を提案する。 量子コンピュータ間を接続する量子ネットワークは、次世代の通信基盤として大きな期待が寄せられている。複数の量子プロセッサを大規模に連携させる分散量子計算や、物理的な限界を超えたセンシング精度の実現など、単一の量子デバイスでは達成不可能な応用を可能にするためである。 量子ネットワーク上で高信頼な通信を実現するには、経由する物理リンクが高い忠実度を保つことが不可欠である。量子情報は環境ノイズに対して極めて脆弱であり、通信中に量子状態が破壊されやすい。そのため、量子もつれのような繊細な相関を遠隔地へ配送する際には、経路上に存在する物理リンクの品質が通信性能を直接的に決定づける。 したがって、ネットワーク内に存在する多数の物理リンクの中から、忠実度の高いものを効率的に選択する技術が極めて重要となる。特に、複数の並列リンクが存在する経路では、その中から最も通信品質の高いリンクを見つけ出し、データ転送に利用することで、通信の成功確率を最大化できる。 しかし、各リンクの忠実度を正確に推定するには多数回の量子測定が必要となり、その測定コストが実用上の大きな制約となる。忠実度は確率的な量であるため、その値を十分な精度で推定するには、同一の量子状態を何度も送受信し、統計を取る必要がある。このプロセスは、時間や量子ビットといった貴重な計算資源を大量に消費する。 限られた測定資源をいかに効率的に配分し、高忠実度なリンクを特定するかが重要な課題である。全てのリンク候補に対して十分な回数の測定を行うことは、ネットワークの規模が大きくなるにつれて現実的でなくなる。このため、測定コストと推定精度のトレードオフを考慮した、賢明な資源配分戦略が不可欠となる。 この課題に対する有望な解決策として、測定コストを削減しつつ高忠実度リンクを特定する LinkSelFiE が提案されている。LinkSelFiE は、多腕バンディット問題にヒントを得たアルゴリズムであり、有望なリンクを集中的に測定し、見込みの薄いリンクの測定を早期に打ち切ることで、全体の測定回数を削減する。 LinkSelFiE は、統計的な探索アルゴリズムを用いることで、最も忠実度の高いリンクを効率的に特定する優れた手法である。これにより、従来法では膨大なコストを要した高忠実度リンクの特定を、現実的な資源の範囲内で実現する道が拓かれた。 一方で、LinkSelFiE の問題設定では、全ての通信経路候補が均等な重要度を持つことを前提としている。これは、単一のノードペア間に存在する複数の並列リンクの中から、純粋に最も忠実度の高いリンクを一つ選択するという問題に特化しているため、自然な定式化である。 実際のネットワーク運用では、アプリケーションの要求などに応じて通信経路ごとに重要度は異なり、均等に扱うことが最善とは限らない。例えば、誤り訂正符号の検証といった基幹的なタスクに用いる通信経路と、優先度の低い補助的なデータ転送に用いる経路とでは、品質保証に割くべき測定資源の量は自ずと異なるはずである。 ネットワーク全体の価値を最大化するためには、各通信経路の重要度、すなわち通信需要を考慮した資源配分が求められる。重要度の低いリンクの忠実度を高精度に推定するよりも、重要度の高いリンクの品質を優先的に保証する方が、システム全体として得られる便益は大きくなる。 LinkSelFiE は優れたリンク特定手法であるが、通信需要という新たな指標を組み合わせることで、さらに実用性を高められる可能性がある。つまり、LinkSelFiE が持つ効率的なリンク特定能力を、通信需要に基づいて重み付けされた問題設定に適用することで、より現実の要求に即した資源配分が実現できると考えられる。 そこで本研究では、通信需要の概念を導入し、測定資源をより価値の高い通信経路へ優先的に配分する新たな手法を提案する。これにより、限られた測定資源から得られる全体的な価値の向上を目指す。 具体的には、各通信経路の重要度と推定忠実度の積をその経路の価値と定義し、ネットワーク全体の総価値を最大化する問題として定式化する。この定式化は、単に最も忠実度の高いリンクを見つけるだけでなく、それがどれだけ重要かという側面も同時に考慮するものである。 この問題に対し、本稿では効率的な近似解法として、広域的な探索と集中的な活用から成る二段階貪欲法を提案する。本手法は、まず限られた資源で全リンクを大局的に調査し、次いで得られた知見に基づき、価値が高いと見込まれる有望な経路の調査に資源を集中させる。シミュレーション実験を通じて、提案手法が従来のアプローチに比べてネットワーク全体の総価値を効率的に向上させることを示す。 本研究の貢献は以下のとおりである。 \begin{itemize} \item 従来の物理的なリンク品質の推定問題を発展させ、通信需要という経済 的・運用的な価値尺度を導入した、より実践的なネットワーク総価値最大化 問題を初めて定式化した。 \item 上記の問題に対する効率的な近似解法として、二段階貪欲法を提案した。 これは、探索と活用を明確に分離することで、大規模ネットワークにおいて も実用的な計算時間で高品質な解を得ることを可能にする。 \item 量子ネットワークシミュレータを用いた評価実験を通じて、提案手法が、 通信需要を考慮しない既存のアプローチに比べて、ネットワーク全体の総価 値を大幅に向上させることを定量的に明らかにした。 \end {itemize} 本稿の構成は以下の通りである。2章で本研究が対象とする問題モデルと目的 関数を定義する。3章では提案手法である二段階貪欲法の詳細を述べる。4章で シミュレーション評価の結果を示し、提案手法の有効性を考察する。最後に5 章で結論と今後の課題を述べる。 \section{通信需要を考慮したリンク忠実度計測問題} %% 本問題は通信需要の大きさが異なる複数ノードペアに対し最適な測定資源配分 %% を決定する問題として定式化される。これは単一ノードペア間の最高忠実度リ %% ンク特定問題を、より現実的な状況へ拡張したものである。 %% 本問題の入力はネットワーク構成と総測定予算である。具体的には単一の対象 %% ノード $S$ と $N$ 個の隣接ノード集合、各ノードペア $(S, D_n)$ 間の並列 %% リンク集合 $L_n$、各ノードペアの重要度 $I_n$、そして総測定予算 $C$ が %% 与えられる。ただし、各リンク $l_{nj}$ の真の忠実度 $f_{nj}$ は未知であ %% る。 %% 問題の出力は測定予算内で選択された価値ある通信経路の集合である。アルゴ %% リズムは価値が高いと判断した $K$ 個のノードペア集合 $S_{sel}$ を決定す %% る。そして選択された各ノードペア $n_k$ において最も忠実度が高いと特定 %% されたリンク $l_{nk}^*$ とその推定忠実度 $\hat{F}^*_{nk}$ を出力する。 %% 本問題の目的は目的関数 ($\text{maximize} \sum_{n_k \in S_{sel}} I_{n_k}\hat{F}^*_{n_k}$) %% で定義されるネットワーク全体の総価値を最大化することである。これは選択 %% された全経路の価値すなわち重要度と忠実度の積の総和を示す。 %% \radd{このとき、制約条件は、全リンクにおける総測定コストが総測定予算 %% $C$ を超えないこと、すなわち %% $\sum^N_{n=1} \sum_{l \in L_n} Cost(l) \leq C$ %% で与えられる。 %% } 本問題は、通信需要 (重要度 $I_n$) が異なる $N$ 個のノードペア$(S, D_n)$に対し、総測定予算 $C$ の制約下で、ネットワーク全体の総価値を最大 化する測定資源配分を決定する問題である。各ノードペアは並列リン ク集合 $L_n$ を持ち、各リンク $l_{nj}$ の真の忠実度$f_{nj}$ は未知とす る。 本問題は、価値が高いと判断したノードペア集合 $S_{sel}$ 選択し、 各ペア $n_k \in S_{sel}$ で最高と推定されたリンク忠実度$F^*_{nk}$ を用 いて、以下の目的関数で定義される総価値を最大化することである。 {\footnotesize \begin{align} \text{maximize} \sum_{n_k \in S_{sel}} I_{n_k}\hat{F}^*_{n_k} \end{align} } このとき、制約条件は、全リンクにおける総測定コストが総測定予算$C$ を超 えないこと、すなわち $\sum^N_{n=1} \sum_{l \in L_n} Cost(l) \leq C$で 与えられる。 \section{提案手法 : 二段階貪欲法(Two-Phase Greedy)による資源配分} %% 本稿では上記の問題を解くためにTwo-Phase Greedy手法を提案する。本手法は %% 広域的な探索と集中的な活用の二段階処理により限られた測定資源を効率的に %% 配分する。第一段階では全リンクに対して少量の測定を行い忠実度の初期推定 %% 値を低コストで得る。これによりネットワーク全体の品質分布を大局的に把握 %% する。 %% 第二段階では第一段階の結果を基に残りの測定資源を価値が高いと見込まれる %% 有望なリンクへ集中的に投下する。具体的には各ノードペアの重要度 $I_n$ %% と初期推定忠実度 $\hat{f}_n$ の積から価値スコアを計算する。そして価値 %% の高いノードペア内のリンク群にのみLinkSelFiEを適用し詳細な測定を行う。 %% この貪欲戦略により測定資源は価値創出の期待値が高い経路の特定へ自動的に %% 集中し総価値の効率的な最大化が期待できる。 本稿では、上記の問題を解くための効率的な近似解法として、広域的な探索と 集中的な活用を組み合わせた二段階貪欲法を提案する。この手法は、 組合せ最適化問題に対する現実的なアプローチとして、限られた測定資源を準 最適に配分し、計算コストを抑えつつ高い性能を実現することを目的とする。 二段階貪欲法の第一段階は、広域探索フェーズである。ここでは、限ら れた測定予算の一部を、対象となる全てのリンクに少量ずつ均等に配分するこ とで、各リンクの忠実度の初期推定値を低コストで得る。 本手法の第二段階は、活用フェーズである。ここでは、広域探索フェーズで得 られた初期推定忠実度と各ノードペアの重要度の積から価値スコアを算出し、 このスコアが高い有望なノードペア内のリンク群に残りの測定資源を集中的に 投下する。具体的には、各ノードペア $n$ に対して価値スコア $I_n\hat{f}_n$を計算し、スコアの高い順にノードペアを選択する。 %% そして、選 %% 択されたノードペア内のリンク群に対してのみ、先行研究である LinkSelFiE %% を適用し、最も忠実度の高いリンクを高い精度で特定する。 %% この貪欲戦略により、測定資源は価値創出の期待値が高い経路の特 %% 定へと自動的に割り当てられ、ネットワーク全体の総価値が効率的に最大化さ %% れることが期待できる。 \section{実験} \begin{figure}[t] \centering \begin{minipage}[b]{0.235\textwidth} \centering \includegraphics[width=\textwidth]{graphA.eps} \vspace{0.5em} {\scriptsize 図1: 隣接ノード数3における\\測定予算と総価値スコアの関係} \label{fig:r3} \end{minipage} \hfill \begin{minipage}[b]{0.235\textwidth} \centering \includegraphics[width=\textwidth]{graphC.eps} \vspace{0.5em} {\scriptsize 図2: 隣接ノード数5における\\測定予算と総価値スコアの関係} \label{fig:r5} \end{minipage} \end{figure} 本章では、提案手法がネットワーク全体の総価値を効率的に最大化できること を示すため、量子ネットワークシミュレータ NetSquid を用いた評価実験を行っ た。 本実験では、1つの対象ノードに接続する隣接ノード数が $N=3$ および $N=5$ の2種類のスター型トポロジを用いた。各ノードペア間には5本のリンクが存在し、そのうち1本の平均忠実度を $0.95$、残りの4本を $0.85$ とする正規分布に従って忠実度を設定した。各ノードペアの重要度 $I_n$ は、区間 $[0, 1]$ の一様乱数により決定した。 二段階貪欲法の設定として、広域探索フェーズでは、各リンクに対して 初期予算($t_0=40$)を割り当て、全リンクを均等に測定し初期推定値を得る。 活用フェーズでは、価値スコアによって選択されたノードペア内のリンク 群に対して、LinkSelFiEを適用することで、最も忠実度の高いリンクを特定 する。 比較手法として、Uniform-LinkSelFiEおよびUniform-Naiveを用いた。前者は、 LinkSelFiEの枠組みで測定予算を全ペアに均等配分し、リンクが一意に定まれ ばそのリンクを、そうでなければ推定忠実度が最大のリンクを選出する手法で ある。後者は、予算を全ペア・全リンクに均等配分する手法である。 評価指標には、測定予算を変化させた際のネットワーク総価値スコアを用い、 各測定予算の値について、独立なシュミレーションを 20 回実施し、その平均 値と 95 \% 信頼区間を算出した。 図1および図2の結果から、提案手法は比較手法よりも高い総価値スコアを達成し、価値の高いリンクへ優先的に資源を配分することが示された。ただし、実験で検証した範囲を超えて予算をさらに増加させた場合には、価値の低いリンクにもコストをかけてしまうため、スコアの上昇率は鈍化し、追加投資による価値の向上は限定的になると考えられる。 %% 隣接ノードが 3 つの条件での結果 (図 1) では、 %% 測定予算が少ない初期段階でスコアは急激に上昇し、その後、上昇率は緩やか %% になる傾向が見られた。これは、提案手法が価値の高いリンクへ優先的に資源 %% を配分するため、初期の投資で大きな効果が得られる一方、有望なリンクの特 %% 定が進むにつれて追加投資による価値の向上が限定的になることを示唆してい %% る。この結果は、特に資源制約が厳しい状況において提案手法が有効であるこ %% とを示している。 %% また、隣接ノードが 5 つの条件での結果 (図 2) では、利用可能な予算が増 %% えるにつれ、提案手法と比較手法との性能差がより拡大する結果が得られた。 %% 探索対象となるリンクの総数が増加すると、各リンクに割り当て可能な平均測 %% 定資源は相対的に減少し、資源配分の効率性がより重要となる。このような厳 %% しい資源制約下において、通信需要と品質に基づいて資源を的確に配分する提 %% 案手法の優位性がより際立つためであると考えられる。以上の結果から、提案 %% 手法は、特に大規模で資源制約の厳しい量子ネットワークにおいて、全体の価 %% 値を最大化する上で高い有効性を持つことが示された。 %% 本章では、通信需要（重要度）と忠実度の両方を考慮した資源配分手法の有効 %% 性を、シミュレーションによって定量的に評価する。具体的には、限られた測 %% 定予算のもとで、提案手法がネットワーク全体の総価値スコア（$\sum I_n %% \cdot \hat{f}_n^*$）をどれだけ効率的に最大化できるかを検証する。 %% シミュレーションには、量子ネットワークシミュレータである NetSquid を用 %% いた。評価対象とするネットワークトポロジは、1つの対象ノードと、それに %% 接続する隣接ノードの数が3つ（$N=3$）または5つ（$N=5$）の2種類である。 %% 各ノードペア $(S, D_n)$ の間には、それぞれ5本の独立な量子リンクが存在 %% すると仮定する。リンクのノイズモデルにはデポラライジングチャネルを適用 %% し、リンク忠実度は、平均0.95のリンク1本と平均0.85のリンク4本からなる正 %% 規分布に従って生成された。 %% また、各ノードペアに割り当てられる重要度 $I_n$ は、通信タスクの優先度 %% を表すパラメータとして、区間 $[0, 1]$ における一様乱数により設定した。 %% なお、各評価点について20回の独立なシミュレーション試行を行い、その結果 %% の95\%信頼区間をグラフ中に縦線で示している。 %% 実験結果より、提案手法はすべての測定予算条件において比較手法よりも高い %% 総価値スコアを達成しており、その有効性が確認された。一方で、測定予算の %% 増加に伴ってスコアの上昇率は徐々に低下する傾向が見られた。これは、提案 %% 手法が価値の高いリンクに優先的に測定資源を集中させる戦略を取るため、初 %% 期段階において効果的な投資が行われる一方で、残されたリンク群には相対的 %% に低い価値しか見込めないためである。この結果から、提案手法は特にリソー %% ス制約が厳しい状況において有効であることが示唆される。 %% 図\ref{fig:r3}および図\ref{fig:r5}は、それぞれ隣接ノードが3つ（$N=3$） %% および5つ（$N=5$）の場合における、総価値スコアと測定予算の関係を示して %% いる。隣接ノード数を3から5へ増加させた場合の評価では、提案手法と比較手 %% 法との性能差がより顕著に拡大した。隣接ノード数が増加すると、各ノードペ %% アに割り当て可能な平均測定資源は相対的に減少する。このような厳しい資源 %% 制約下において、需要と品質に基づいて資源を的確に配分する提案手法の優位 %% 性がより際立ったものと考えられる。以上の実験結果から、提案手法は通信需 %% 要とリンク品質に基づいて測定資源を効率的に配分することにより、特に資源 %% 制約が厳しい、あるいはネットワーク規模が大きい状況において、全体の価値 %% を最大化する上で高い有効性を持つことが示された。 \vspace{-0.4em} % ← この行を追加（-0.8em 〜 -1.2em で調整） \section*{謝辞} 本研究の一部は JSPS 科研費 24K02936 の助成を受けたものである。 \vspace{-0.5em} % ← この行を追加 \renewcommand{\em}{\it} \bibliographystyle{ieeetr} \bibliography{bib/quantum} \end{document}