** Q. 以下の論文が解いている問題の入力、出力、制約条件、目的関数を説明して IEEE INFOCOM 2024 - IEEE Conference on Computer Communications | 979-8-3503-8350-8/24/$31.00 ©2024 IEEE | DOI: 10.1109/INFOCOM52122.2024.10621263 L INK S EL F I E: Link Selection and Fidelity Estimation in Quantum Networks Maoli Liu, Zhuohua Li⇤ , Xuchuang Wang, John C.S. Lui The Chinese University of Hong Kong {mlliu, zhli, xcwang, cslui}@cse.cuhk.edu.hk Abstract—Reliable transmission of fragile quantum information requires one to efficiently select and utilize high-fidelity links among multiple noisy quantum links. However, the fidelity, a quality metric of quantum links, is unknown a priori. Uniformly estimating the fidelity of all links can be expensive, especially in networks with numerous links. To address this challenge, we formulate the link selection and fidelity estimation problem as a best arm identification problem and propose an algorithm named L INK S EL F I E. The algorithm efficiently identifies the optimal link from a set of quantum links and provides an accurate fidelity estimate of that link with low quantum resource consumption. L INK S EL F I E estimates link fidelity based on the feedback of a vanilla network benchmarking subroutine, and adaptively eliminates inferior links throughout the whole fidelity estimation process. This elimination leverages a novel confidence interval derived in this paper for the estimates from the subroutine, which theoretically guarantees that L INK S EL F I E outputs the optimal link correctly with high confidence. We also establish a provable upper bound of cost complexity for L INK S EL F I E. Moreover, we perform extensive simulations under various scenarios to corroborate that L INK S EL F I E outperforms other existing methods in terms of both identifying the optimal link and reducing quantum resource consumption. Index Terms—Quantum Networks, Link Selection, Fidelity Estimation I. I NTRODUCTION Quantum networks are capable of transmitting quantum information, represented by quantum bits or qubits, between multiple quantum systems, facilitating groundbreaking applications such as quantum cryptography [1], quantum key distribution (QKD) [2], clock synchronisation [3], and quantum internetof-things (QIoT) [4]. The principles of quantum mechanics [5] enable quantum networks to achieve functionalities that remain unattainable with classical networks. However, harnessing the potential of quantum networks also introduces new challenges in network design and benchmarking. For instance, direct transmission of qubits via physical quantum links, such as optical fibers, in a large-scale quantum network is not feasible, as the probability of successful transmission diminishes exponentially with the length of quantum links due to quantum decoherence. Additionally, the no-cloning theorem [6] prevents the replication of an arbitrary qubit for re-transmission or amplification, adding further complexity to quantum network design. Besides, quantum information is inherently fragile and easily corrupted by noise, necessitating the benchmarking of quantum networks to ensure their reliability and performance. ⇤ Zhuohua Li is the corresponding author. The work of John C.S. Lui was supported in part by the RGC GRF 14207721. A quantum network usually consists of quantum nodes connected via quantum links [7]. Each quantum node can function as a source, a destination, or a repeater, with the ability to perform quantum operations and store qubits in its quantum memory. Quantum links, often formed by optical fibers or free-space optical links, can deliver qubits from one end to the other. To realize long-distance qubit transmission, people rely on quantum entanglement, a phenomenon where multiple qubits are correlated and the state of individual qubits cannot be described independently of the others. Quantum entanglement is regarded as an important resource for transmitting quantum information. Various experiments [8]–[10] have successfully demonstrated the distribution of quantum entanglement. Once two quantum nodes share entangled pairs, they can transmit quantum information to each other by a process known as quantum teleportation [11], regardless of their distance. Reliable long-distance quantum information transmission is a fundamental requirement for many quantum applications. Many existing works [12]–[15] focus on long-distance quantum entanglement routing protocols. These protocols aim to establish end-to-end entanglement through quantum repeaters via an operation called entanglement swapping [11], [16] in a quantum network, with the goal of improving the network throughput, enhancing robustness and serving more users. However, due to the fragile nature of quantum information, qubits are susceptible to decoherence via interactions with the environment. For example, the generated entangled pairs may not be perfectly entangled, and attenuation in physical links and imperfect swapping operations may lead to corruption during the establishment of long-distance entanglement. As a result, the established end-to-end entanglement may not be at the desired states and cannot be used for reliable quantum information transmission. Usually, people use fidelity [5] to quantify the quality of an entanglement link. The value of fidelity is from 0 to 1, and it measures how well a quantum channel preserves quantum information. Despite some recent works [17]–[19] that take fidelity guarantee into consideration when designing entanglement routing protocols, it remains essential to explicitly verify the quality of entanglement links before transmitting important quantum information. The main objective of this work is to efficiently estimate the fidelity of established entangled links. Our approach is based on a method called network benchmarking [20], which measures the average fidelity of quantum entanglement links. However, network benchmarking is designed to measure a single quantum Authorized licensed use limited to:©2024 Chinese University of Hong Kong. Downloaded 979-8-3503-8350-8/24/$31.00 IEEE 1421on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. link. In cases where there are multiple links with unknown fidelities—a common scenario in quantum communications, one needs to apply network benchmarking to each link individually, S S S D D D leading to a rather high cost. In practice, one only needs to (b) Entanglement Swapping (c) End-to-End Entanglement (a) Entanglement Generation select a few high-fidelity quantum links to transmit quantum information. Precise fidelity estimation of links with low fidelity Repeater Entanglement Physical Link Qubit Swapping is unnecessary where the corresponding benchmarking cost Fig. 1. End-to-end entanglement establishment. is actually a waste and can be partially saved. Therefore, we consider identifying and eliminating low-fidelity links early on from a set of unknown links, so that we can efficiently obtain efficient decision-making with limited quantum resources. accurate fidelity estimates for the desired high-quality links • We propose a new algorithm named L INK S EL F I E, which and save quantum resources. utilizes the novel confidence interval for the network To tackle the challenging problem of link selection and benchmarking subroutine. We prove that our algorithm can fidelity estimation, we formulate it as a best arm identification correctly output the optimal link and its accurate fidelity problem, a classical sequential decision-making task in multiestimate with high probability. Additionally, we provide a armed bandits [21]. Specifically, each arm corresponds to an provable cost complexity upper bound for the algorithm. entangled link in a link set, and each arm is associated with an • We conduct extensive simulations, and the results show unknown stochastic reward representing the link fidelity. The that L INK S EL F I E can identify optimal links with signetwork benchmarking method requires transmitting qubits nificantly fewer quantum resources compared to other through a link multiple times to obtain a fidelity estimate, methods while providing comparable fidelity estimation which implies that one can only receive a reward or feedback accuracy. after pulling an arm multiple times. This poses a significant The rest of the paper is organized as follows. We first present challenge compared to the classical setting, where a single pull of an arm yields an immediate reward sample. Our objective some background information on quantum networks and the is to identify the link with the highest fidelity from a link set network benchmarking method in Section II. In Section III, and get its fidelity estimate while consuming as few quantum We formulate the link selection and fidelity estimation problem resources as possible. To achieve this, we design a phase-based as a best arm identification problem. The detailed algorithm elimination algorithm named L INK S EL F I E (Link Selection and design and its theoretical analysis are presented in Section IV. Fidelity Estimation). The elimination utilizes a novel confidence Performance evaluations of our algorithm are conducted in interval derived in this paper for the results of the vanilla Section V, and related work is discussed in Section VI. Finally, network benchmarking subroutine. Based on the confidence Section VII concludes the paper. interval, we prove that our algorithm identifies the optimal link II. BACKGROUND with high confidence. We also introduce the notion of cost In this section, we review some prerequisites about quantum complexity, which corresponds to quantum resources used by the algorithm and provide a cost complexity upper bound of networks and the network benchmarking method [20]. our algorithm, which theoretically shows that our algorithm is more efficient than the vanilla network benchmarking [20]. A. Quantum Networks A quantum network is composed of quantum nodes interconTo evaluate our algorithm, we simulate a quantum network where a pair of quantum nodes are connected via multiple nected via quantum links. Each quantum node typically contains entanglement links associated with different levels of noise. a quantum processor for performing quantum operations and Our goal is to determine the link with the highest fidelity. measurements and has the ability to generate and store quantum We conduct simulations with different noise models and link states in its limited quantum memory. Quantum links, which fidelity distributions. The results corroborate that our algorithm can be optical fibers or free-space optical links, facilitate the significantly reduces the total benchmarking cost compared physical transmission of qubits between quantum nodes, such as to the vanilla network benchmarking method and the naive the transmission of photons through an optical fiber. However, successive elimination method. Furthermore, our L INK S EL F I E since the successful transmission rate decreases exponentially algorithm operates without requiring any knowledge of the with the length of quantum links, people have proposed network topology or the entanglement generation process. entanglement-based networks and use quantum entanglement Therefore it can be easily integrated into the current multi- to enhance the transmission of quantum information. 1) End-to-End Entanglement: Quantum entanglement arises layer design of the quantum network protocol stack. This adaptability allows it to seamlessly function with different when the shared state between multiple qubits cannot be lower-level protocols, such as entanglement routing or network factored into a product of its individual qubit states. A classical example is the maximally entangled EPR (Einsteindiagnostic protocols. p We summarize our contributions as follows. Podolsky-Rosen) state | ± i = |01i±|10i . To overcome the 2 • We formulate the link selection and fidelity estimation distance limitation of end-to-end entanglement between two problem as a best arm identification problem, enabling distant quantum nodes, quantum repeaters are positioned at BSM BSM Authorized licensed use limited to: Chinese University of Hong Kong. Downloaded 1422on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. B. Network Benchmarking The idea behind network benchmarking is that by channel twirling process [22], which involves random applications of Clifford operations [25], one can transform arbitrary quantum channels into depolarizing channels with the same fidelity. By accessing these depolarizing channels repeatedly, one can estimate the average fidelity of them, which is equivalent to that of the original channel. The parameters used for network Link !! Link !" …… …… …… intermediate locations within the network. Given a source node S and a destination node D sharing no direct physical links, repeaters along a path of physical links connecting S and D are responsible for generating entanglement (Fig. 1 (a)) with adjacent nodes and executing entanglement swapping operations (Fig. 1 (b)) to establish an end-to-end entanglement link between S and D (Fig. 1 (c)). After the entanglement is successfully established, S can teleport an information qubit to D by consuming that entanglement. 2) Quantum Noise and Average Fidelity: When establishing end-to-end entanglement in quantum networks, various sources of noise can potentially arise. For instance, losses in optical fibers, imperfect hardware, and decoherence during qubit storage. Such noise can lead to imperfect entanglement being shared between the source and destination nodes, consequently causing errors in quantum state transmission. Quantum noise is often characterized by quantum channels [5]. Examples of noise channels include the bit-flip channel, the depolarizing channel, the dephasing channel, and so on. Specifically, the depolarizing channel E(⇢) := p⇢ + (1 p) I2 leaves the input quantum state ⇢ unchanged with probability p and replaces it with the maximally mixed state I2 (the quantum equivalent of a uniformly random classical bit) otherwise. The depolarizing channel model is a useful tool for characterizing quantum gates [22], [23] and quantum networks [20]. The average fidelity [24] of a quantum link associated with noise channel E is defined by F (E) := R d Tr[E(| i h |) | i h |], where the integral is taken uniformly over all pure quantum states | i and Tr denotes the trace of a matrix. The average fidelity quantifies how well a quantum link preserves information, where a fidelity of 1 corresponds to a noiseless channel. For quantum links corresponding to the depolarizing channel with parameter p, the average fidelity is (1 + p)/2 [5]. For simplicity, we use the term fidelity to refer to the average fidelity hereinafter. In this work, we adopt the assumption of Markovian noise [20], which implies that the noise is memoryless, and entanglement links constructed via the same path always correspond to the same quantum channel, irrespective of their prior usage history. A pair of source and destination nodes may be interconnected by multiple physical paths, along which entanglement links can be established. Consequently, each entanglement link between two nodes is implicitly associated with a specific physical path within the network. In this paper, we do not consider the low-level details of path discovery or entanglement link generation but assume the set of distinct entanglement links is known. S D Link !# Physical Quantum Link Entanglement Link Quantum Node Fig. 2. An example of a quantum network. We abstract away the irrelevant network topology between S and D and only assume there are L entanglement links. benchmarking are M and T . M is called the bounce number set, which contains a series of integers, and T represents the repetition times for each bounce number m 2 M. A “bounce” refers to the process in which node S applies a random Clifford operation to the state and sends it to node D, which then does the same and returns it to S. To estimate the average fidelity of entanglement links between nodes S and D, the following procedure will be implemented repeatedly for T times for each m 2 M: (i) source node S generates an initial state; (ii) nodes S and D “bounce” the state m times; (iii) source node S applies a final operation and measures the state. The average value of the T measurement results is denoted by bm , which is often called the survival probability. The survival probability is modeled by the exponential model bm = Ap2m , where A is a constant accounting for quantum state preparation and measurement errors, and p is the depolarizing parameter of the twirled channel. Thus, by fitting the exponential model bm = Ap2m to the data {M, {bm }m2M }, one can estimate the parameter p̂ and deduce the average fidelity (1 + p̂)/2. In quantum networks, transmitting a qubit over a long distance is costly, and each bounce consumes two entangled links. Therefore, we use the number of bounces as a cost metric for network benchmarking. In practice, it is essential not only to precisely estimate the fidelity of the target links but also to conserve the consumption of bounces. III. M ODEL In this section, we first define the link selection and fidelity estimation problem in quantum networks and provide a motivating example. Then we formulate our problem as a best arm identification problem in multi-armed bandits. A. Problem Definition Fig. 2 depicts a quantum network consisting of multiple nodes, among which we select a source node S and a destination node D. There are L 2 N+ entanglement links between S and D, denoted by L = {l1 , . . . , lL }. Each of these links is established along a distinct path connecting S and D. Note that we do not consider the underlying network topology or any specific mechanism for establishing these entanglement links, as they are irrelevant to our purposes. Instead, we abstract away these details and assume the existence of a network Authorized licensed use limited to: Chinese University of Hong Kong. Downloaded 1423on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. protocol capable of constructing these links. The fidelities equivalent to pulling arm i for T times. Besides, the quantum of entanglement links can vary due to noise. We denote the resources consumed by the subroutine increase linearly in terms fidelity of link li 2 L by fi . The optimal links are those with of the repetition times T and the summation of all bounces in P the highest fidelity, i.e., l⇤ 2 arg maxli 2L fi . M, i.e., m2M m. Our goal is to design an algorithm that correctly outputs To ensure high-quality quantum information transmission, it is essential to select entanglement links with the highest the optimal arm (link) 1 with the probability of at least 1 (confidence parameter 2 (0, 1)) with as small costs as fidelity. Since the link fidelities are unknown beforehand, one approach is to use the network benchmarking method described possible. We denote the total cost incurred by an algorithm A in Section II-B to estimate the fidelity of each link respectively as cost complexity, which can be expressed as follows, X X to a specific accuracy " > 0, i.e., |fˆi fi | < " at a given Cost(A) := Ni,⌧ m, confidence level, and then select the high-fidelity links to i2L m2M transmit quantum information. However, this method means that the benchmarking cost grows linearly with the number of where Ni,s is the total number of pulls to link i 2 L up to available links L. This indicates that the benchmarking cost time s, and ⌧ is the stopping time at which the algorithm A identifies the optimal arm. becomes prohibitive when the number of links is large. Motivating Example. A qubit may be corrupted if transmitIV. A LGORITHMS ted through noisy links, causing negative impacts on quantum In this section, we first elaborate on the design of our link communications. Since links with low fidelity are unsuitable for transmitting quantum information, it is unnecessary to spend selection and fidelity estimation algorithm, which we refer to resources and time on accurately estimating these inferior as L INK S EL F I E, and present the algorithmic details. We also links. For instance, consider two links l1 and l2 with unknown provide a theoretical analysis of its cost complexity. fidelities f1 = 0.9 and f2 = 0.7, respectively. When the estimation accuracy reaches 0.05, with a high probability the A. Algorithm Design Here, we propose an online algorithm (L INK S EL F I E) based confidence intervals of the estimate fidelities no longer overlap, enabling us to identify that link l2 is inferior to link l1 . Then we on multi-armed bandits results. Unlike the classical bandit can discard l2 , thus saving the benchmarking cost that would setting where each arm can be flexibly pulled, links in our have otherwise been spent on it, and focus on estimating the problem can only be pulled in “batches” by the network fidelity of l1 more precisely. This motivates us to explore an benchmarking subroutine. This inflexibility requires one to online learning approach to solve the link selection and fidelity assign multiple pulls for each link in a batched manner. Therefore, we consider phase-based algorithms, where in each estimation problem. phase we assign a fixed number of pulls to each link and B. Bandit Formulation run the network benchmarking subroutines to estimate their We now formulate the link selection and fidelity estimation fidelities. One key challenge in the algorithm design is how problem as a best arm identification problem. Let us consider to appropriately allocate the number of pulls to different a stochastic multi-armed bandit whose arm set is denoted as phases, which shall (a) be based on the theoretical estimation K := {1, . . . , L}. Each arm i 2 K corresponds to a distinct performance of this subroutine (see Lemma 1), and also (b) be link in li 2 L. The reward of each arm i 2 K is associated with adaptive to the relative magnitudes of all links fidelities (e.g., a stochastic random variable Pi , whose mean is pi , satisfying reward gaps i ), which are unknown a priori. To address this challenge, we propose a phase-based elimthat fi = (pi + 1)/2 and pi 2 (0, 1), i.e., there is a simple linear relation between the link fidelities and reward means. ination algorithm, presented in Algorithm 1. The algorithm Without loss of generality, we assume that reward means are runs in phases denoted as s = 0, 1, 2, . . . and proceeds with a sorted in descending order, i.e., p1 > p2 > · · · > pL , and arm link elimination mechanism. In the beginning, the algorithm 1 is the unique optimal arm, since one can always relabel the initializes a candidate set S as the full link set L. In each link index. We denote the reward mean gaps as i := p1 pi phase, the algorithm executes the vanilla network benchmarking subroutines for all remaining links in the candidate set S with for suboptimal arm i 6= 1, and for i = 1, we set 1 = 2 . In the stochastic multi-armed bandit, the decision maker appropriate pull times Ts according to Lemma 1 (address (a)). obtains samples drawn from the reward distribution of an arm At the end of each phase, the algorithm eliminates the inferior by pulling that arm. The empirical reward mean can then be links identified in this phase, and, therefore, the algorithm does estimated by averaging multiple samples of the arm. However, not need to spend costs on these inferior links (adaptively) in in the fidelity estimation of quantum entanglement links, the future phases (address (b)). L INK S EL F I E takes three input parameters: the link set L, empirical reward (fidelity estimate) is computed via regression by the vanilla network benchmarking subroutine. This implies the pre-configured bounce length set M, and the confidence that in our specific scenario, arms (links) can only be pulled parameter 2 (0, 1). Ts is the cumulative number of pulls for in batches. For simplicity, we regard the act of applying this remaining links in S in phase s, i.e., the assigned number Ts 1 . We set vanilla network benchmarking subroutine with the bounce of pulls for one link in phase s is Ts number set M and the repetition times T to link li once Ts = C22s log s(s+1)|S| (Line 3), where C is a constant in Authorized licensed use limited to: Chinese University of Hong Kong. Downloaded 1424on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. (s) Lemma 1. Let p̂i be the estimate fidelity of link i in phase (s) s and bi,m be the empirical survival probability of link i at the bounce number m after Ts trials. We integrate the vanilla network benchmarking illustrated in Section II-B as a subroutine here, i.e., Benchmarking (Line 5). The subroutine Fitting (Line 7) fits the model bm = Ap2m to the input data and returns p̂. Specifically, at the beginning of each phase s, L INK S EL F I E uniformly pulls links in the candidate set that have not been eliminated yet for Ts Ts 1 times (i.e., run the network benchmarking subroutine with the repetition times Ts Ts 1 (s) (Line 5)). Following this, it calculates bi,m by weighted (s 1) averaging the newly obtained data bi,m and the data bi,m (s) from last phase (Line 6), and gets fidelity estimates p̂i of the remaining links (Line 7). Then it determines the maximum estimate value p̂max (Line 8) and discards links i satisfying the (s) condition p̂i + 2 s < p̂max 2 s (Line 9). The condition means that the upper confidence bound of link i is less than the lower confidence bound of the link with the current highest empirical fidelity, which implies that link i is a suboptimal link with high confidence and we can eliminate link i. When there is only one link left in the candidate set S, the algorithm terminates and returns corresponding information. Algorithm 1: LinkSelFiE: Link Selection & Fidelity Estimation Input: path set L, confidence parameter , bounce length set M Initialization: candidate set S L, s 0, (0) p̂i 0, 8i 2 L, T0 = 0, (0) bi,m = 0, 8i 2 L, m 2 M 1 while |S| > 1 do 2 s s + 1 // s is the current phase. 3 Ts C · 22s log s(s+1)|S| // C is a constant. 4 for i 2 S do 5 {bi,m }m2M Benchmarking(i, M, Ts Ts 1 ) 6 7 (s) bi,m (s) p̂i bi,m (Ts Ts (s 1) 1 )+bi,m Ts 1 ,8m 2 M Ts (s) Fitting(M, {bi,m }m2M ) (s) p̂max maxi2S p̂i (s) 9 S S \ {i 2 S : p̂i + 2 s 6 p̂max 2 s } Output: the remaining link in S and p̂max 8 B. Theoretical Analysis In this subsection, We analyze the cost complexity upper bound of L INK S EL F I E. We begin by presenting the confidence interval for the estimate of the vanilla network benchmarking method described in Section II-B. Since the link fidelity is estimated from an exponential regression using data points of each bounce length m 2 M, rather than a simple average of independent random samples, directly applying the conventional analysis tools used in classical bandit literature, such as Hoeffding’s inequality, fails to capture the correlations between data, and thus yields a looser confidence interval. To address this issue, we examine the properties of non-linear regression and derive a new confidence interval in Lemma 1, which exploits information from all data points of each bounce length, offering an advantage over Hoeffding’s inequality. Lemma 1 (Confidence Interval for Network Benchmarking). Given the input parameters M and T 2 N+ , for a confidence parameter 2 (0, 1), to benchmark a link with the true depolarizing parameter p, the depolarizing parameter p̂ estimated by the vanilla network benchmarking method satisfies, " # r C 1 Pr |b p p| 6 log >1 , T where C is a constant related to the bounce length set M and measurement noise, which is explicitly expressed in Appendix A. We refer interested readers to Appendix A for its detailed proof. Given Lemma 1, we have the following corollary. Corollary 1. Given the confidence radius " and the confidence level 1 , the required repetition times for the vanilla network benchmarking method should satisfy: ✓ ◆ C 1 T =O log . "2 From Corollary 1, we know how to set the repetition times T to achieve certain accuracy when benchmarking one entanglement link, which also implies the benchmarking cost. Based on the above lemma, we derive a cost complexity upper bound for our Algorithm 1. The proof details of Theorem 1 is given in Appendix B. Theorem 1 (Cost Complexity of Algorithm 1). Given a bounce length set M and a confidence parameter 2 (0, 1), the cost complexity of Algorithm 1 is upper bounded as follows, ✓ ◆! X X C L 4 Cost(AL INK S EL F I E ) 6 O log · m, 2 log i2L i i m2M where L is the number of links and C is a universal constant. Remark 1 (Modify Algorithm 1 to find an "-optimal link). If we modify the algorithm proceeding condition in Line 1 to be more than one link remains in the candidate set and the estimation accuracy does not reach ", i.e., |S| > 1 and 2 s > ", then Algorithm 1 can output "-optimal links (whose fidelity is greater than the optimal one minus ", i.e., pi > p1 "). Identifying such "-optimal links is often practical in quantum networks [17]. With this modification, the cost complexity is upper bounded as follows, ✓ ◆! X X C L 4 Cost(Amod ) 6 O log log · m, (1) ˜2 ˜i i2L where e i := max{ i m2M i , "}. Authorized licensed use limited to: Chinese University of Hong Kong. Downloaded 1425on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. Remark 2 (Compare to vanilla network benchmarking (uniform exploration)). If one applies the vanilla network benchmarking method to uniformly estimate all links’ fidelities and stops at the accuracy ", then the cost complexity would be upper bounded as follows, ✓ ◆ X CL L Cost(Avanilla ) 6 O log · m. "2 m2M The above bound is greater than (1) especially when there are some links with large fidelity gaps i . This corresponds to that when i ’s are large, Algorithm 1 can eliminate these links with high fidelity gaps in early phases, thereby conserving a large number of quantum resources. V. P ERFORMANCE E VALUATION In this section, we evaluate our algorithm L INK S EL F I E. We first elaborate on our experiment setups, including quantum network structure, quantum noise model, baseline algorithms, and the performance metrics we use. Then, we show our evaluation results in terms of efficiency and precision. A. Experiment Setup and simulate a two-node quantum network with L links, which have fidelities 1, 1 , 1 2 , . . . , 1 (L 1) , respectively. Then we apply each link selection algorithm to the network for different values of L and measure the quantum resource consumption when the algorithms terminate. Note that we use the total number of bounces as the metric for quantum resource consumption and average the results over 10 trials. Figure 3 shows the plots of quantum resource consumption versus the number of links under different noise models. Since VanillaNB spends the same amount of resources for each link, its resource consumption is proportional to the number of links in the network. This leads to excessive resource waste when the network has many low-quality links. On the other hand, both L INK S EL F I E and SuccElimNB can adaptively decide the resources spent by each link, and the cost complexity grows slowly as L increases because it mainly depends on the fidelity gap . However, SuccElimNB only relies on Hoefdding’s inequality to estimate the confidence interval, while L INK S EL F I E benefits from the much tighter confidence intervals for the non-linear regression (Lemma 1). Therefore, L INK S EL F I E collects sufficient information and eliminates the inferior arms more efficiently. The numerical results demonstrate that L INK S EL F I E costs significantly fewer resources than the other two algorithms. We evaluate our algorithm by simulating a quantum network with two nodes connected via several quantum entanglement links. We employ various common noise models and assign different levels of noise to the quantum links, and the objective is to identify the optimal link using as few quantum resources as possible. The entanglement links are generated by placing a quantum source in the middle and bidirectionally distributing entangled photon pairs through noisy quantum channels. We apply four standard and widely used noise models to simulate quantum noise [5]: (1) depolarizing noise model, (2) dephasing noise model, (3) amplitude damping noise model, and (4) bit flip noise model. For the sake of fair comparison among these (a) Depolarizing Noise (b) Dephasing Noise noise models, given a fidelity value, we convert it into the corresponding noise parameters used to initialize each noise model. All the quantum mechanisms are simulated by an offthe-shelf quantum network simulation framework called NetSquid [26]. We compare our algorithm with two baselines, (1) the vanilla network benchmarking algorithm (VanillaNB) and (2) the successive elimination algorithm [27] (SuccElimNB). VanillaNB uniformly benchmarks all the quantum links for each bounce number with a fixed number of repetitions T , (c) Amplitude Damping Noise (d) Bit Flip Noise which we set to T = 200 in our experiments. SuccElimNB Fig. 3. Bounces v.s. the number of links L using different noise models. invokes the network benchmarking subroutine with repetition times T = 4 and treats the estimated fidelities as independent Next, we examine the effect of the fidelity gap on the random samples, then it makes optimistic decisions based on upper confidence bounds derived via Hoefdding’s inequality. It performance of the link selection algorithms. The fidelity gap iteratively eliminates identified bad links as learning proceeds reflects the hardness of the best arm identification problem. until there is only one link left. All the experiments were done We fix the number of links L = 4 and vary the fidelity gap , and we plot the quantum resource consumption versus the on a Linux machine (kernel 6.1.38) with a 3.70 GHz Intel fidelity gap under different noise models, averaged over 10 Xeon E5-1630 v4 CPU and 16GB RAM. trials. As shown in Figure 4, the cost of VanillaNB is preB. Quantum Resources Consumption determined so it is not affected by the fidelity gap, while First, we evaluate the quantum resource consumption of L INK S EL F I E and SuccElimNB can adaptively adjust the cost these link selection algorithms. We fix a fidelity gap = 0.05 according to the fidelity gap. Specifically, the smaller the Authorized licensed use limited to: Chinese University of Hong Kong. Downloaded 1426on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. fidelity gap is, the harder to identify the optimal link, and therefore more resources are needed. When the fidelity gap is large, both L INK S EL F I E and SuccElimNB can identify the optimal link quickly. However, when the fidelity gap is small, benefiting from Lemma 1, L INK S EL F I E can obtain a much tighter confidence interval and eliminate inferior links faster, while SuccElimNB has to perform much more benchmarking subroutines to achieve sufficient confidence. (a) Depolarising Noise (b) Dephasing Noise (a) Depolarizing Noise (b) Dephasing Noise (c) Amplitude Damping Noise (d) Bit Flip Noise Fig. 5. Relative error v.s. the number of links L using different noise models. Vienna QKD network [28], SwissQuantum QKP network [29], Tokyo QKD network [30], and the space-to-ground network [28], demonstrating the promising potential of the upcoming quantum revolution. However, the susceptibility of quantum information to noise necessitates the characterization (c) Amplitude Damping Noise (d) Bit Flip Noise of quantum link noise for reliable quantum information transmission. Ruan [31] proposes a protocol to estimate the fidelity Fig. 4. Bounces v.s. gap using different noise models. of entanglement shared by remote nodes, but it does not take quantum measurement errors into account. Helsen et al. [20] C. Fidelity Estimation Accuracy propose a network benchmarking method, which is robust to Finally, we show the fidelity estimation accuracy of L INK - state preparation and measurement errors and can efficiently S EL F I E. We initialize a two-node network with L links, where and accurately estimate the fidelity of quantum links, regardless the fidelity of each link is generated as follows. We set of how these quantum links are formed. Recently, Andrade et µ1 = 0.95 and µi = 0.85 for i = 2, . . . , L, then for each al. [32] devise novel network tomography protocols (NTP) to link i, we sample its fidelity fi from a Gaussian distribution characterize the channel noise in quantum networks, but it only with mean µi and variance 1/4. We apply each algorithm to the considers bit-flip probabilities of quantum star networks. Liu et network, get the estimated fidelity of the identified optimal link, al. [33] propose quantum Border Gateway Protocol (BGP) to and calculate the relative error. Figure 5 plots the relative error support entanglement routing across multiple quantum Internet versus the number of links L, varying from 2 to 20, and the Service Providers (qISPs) and integrate network benchmarking results are averaged over 10 trials. As expected, L INK S EL F I E with the top-K arm identification problem. However, their can not only identify the optimal link but also evaluate its formulation has more stringent assumptions than ours. Our fidelity accurately. The relative error of L INK S EL F I E is less online link selection algorithm L INK S EL F I E leverages the than 1%, which has no significant difference compared with idea of online learning and inherits the favorable properties other algorithms. When the number of links is large, the relative of network benchmarking. When selecting the optimal link error tends to decrease because the algorithms need to spend from a set of links, L INK S EL F I E is much more efficient than more bounces to distinguish the optimal link, resulting in a network benchmarking. The multi-armed bandit (MAB) [34], [35] is a well-known more accurate estimation. In summary, L INK S EL F I E identifies the optimal link with significantly less quantum resource framework with numerous applications in various fields, such consumption while providing comparable fidelity estimation as crowdsensing [36], opportunistic channel access [37], and social networks [38]. In this literature, our model is related to accuracy. best arm identification with fixed confidence, aiming to identify VI. R ELATED W ORK the optimal arm with high probability using as few samples as Quantum networks have gained a lot of attention since their possible. To solve this problem, algorithms like the successive introduction. Several real-world quantum networks have been elimination algorithm [27], the lil’UCB algorithm [39], and successfully tested outside the laboratory, such as SECOQC the track-and-stop strategy [40] are proposed and theoretically Authorized licensed use limited to: Chinese University of Hong Kong. Downloaded 1427on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. analyzed. The problem has also been extended to the best- measuring the survival probability at sequence length m 2 M. K arms identification setting [41], [42], with the objective to Since bmi is the average of T samples, the variance of its noise select top K arms with the highest means with high confidence. "i is 2 /T . The goal of non-linear least squares is to find the parameters Another variant of the best arm identification problem is to identify the best arm in the fixed-budget scenario [21], [43]– ✓b that minimize the sum of squares of residual errors S(✓), [45], which aims to minimize the probability of returning wrong where |M| X arms at the end of the time budget. We are the first to exploit the 2 S(✓) = (bmi f (mi ; ✓)) . MAB framework to solve the link selection and fidelity estimate i=1 problem in quantum networks. Our algorithm deliberately We compute the confidence interval using the linear approxconsiders the property of the network benchmarking, with the objective of identifying the optimal high-fidelity link from imation method. Taking the Taylor expansion of function f (mi ; ✓) at point a link set with high confidence and consuming as few resources ⇤ ✓ = (A⇤ , p⇤ )T , we have as possible. Unlike using the standard confidence interval based on Hoeffding’s inequality to analyze the sample complexity @f (mi ; ✓) f (mi ; ✓) ⇡f (mi ; ✓ ⇤ ) + (A A⇤ ) of algorithms in classical bandits, we deduce a confidence @A ⇤ ✓ interval for the network benchmarking subroutine and hereby @f (mi ; ✓) ⇤ + (p p ) analyze the cost complexity upper bound of our algorithm from (2) @p ✓⇤ a different perspective. 2m =A⇤ (p⇤ ) i + (p⇤ )2mi (A A⇤ ) VII. C ONCLUSION 2m 1 + 2mi A⇤ (p⇤ ) i (p p⇤ ) , In this paper, we consider the problem of link selection and fidelity estimation in quantum networks. To address this where the ⇡ hides a small o(1) quantity. Hence, challenge, we formulate it as a best arm identification problem |M| and design an efficient algorithm named L INK S EL F I E. We X 2 S(✓) = (bmi f (mi ; ✓)) derive a novel confidence interval of estimates for the vanilla i=1 network benchmarking, a key subroutine within L INK S EL F I E, |M| ⇣ and prove that given a confidence parameter 2 (0, 1), with the (a) X 2m 2m ⇡ bmi A⇤ (p⇤ ) i (p⇤ ) i (A A⇤ ) probability of at least 1 , L INK S EL F I E outputs the optimal (3) i=1 link and its accurate estimate. We also prove a cost complexity ⌘2 2m 1 upper bound for L INK S EL F I E. To validate the performance of 2mi A⇤ (p⇤ ) i (p p⇤ ) L INK S EL F I E, we simulate a quantum network with quantum |M| X nodes connected via multiple entanglement links. Simulation 2 = "i (✓ ✓ ⇤ )T Fi , results show that L INK S EL F I E outperforms other methods in i=1 efficiently selecting the optimal link and accurately estimating f (mi ; ✓) with its Taylor expansion the fidelity while consuming fewer quantum resources across where (a) is by substituting ⇣ ⌘T 2m 1 various scenarios. (2) above, and Fi = (p⇤ )2mi , 2mi A⇤ (p⇤ ) i and " = The authors have provided public access to their code and/or T ("1 , . . . , "|M| ) . data at https://zenodo.org/doi/10.5281/zenodo.10444443. After the linear approximation, we can minimize (3) by the linear least squares and get: A PPENDIX 0 1 1 |M| |M| A. Proof of Lemma 1 X X ⇤ TA @ (4) "i F i ✓ ✓ = F F i i Since the estimate fidelity p̂ is obtained by non-linear i=1 i=1 regression, we use the linear approximation method [46], [47] to derive the confidence interval of p̂ for the vanilla network Equation (4) shows that ✓ ✓ ⇤ is a linear combination of benchmarking. "i ⇠ N (0, 2 /T ). By the definition of multivariate normal In the model bm = Ap2m , ✓ = (A, p)T are the parameters distribution, we have ✓ ◆ we want to estimate. We denote their true values by ✓ ⇤ = 2 b pb)T . ✓b ⇠ N2 ✓ ⇤ , Q , (A⇤ , p⇤ )T , and their least-square estimates by ✓b = (A, T In network benchmarking, the observed data (mi , bmi ) for ⇣P ⌘ 1 |M| i = 1, . . . , |M| are i.i.d. random samples drawn from the where Q = T . i=1 Fi Fi non-linear model as follows: Since we only care about the estimation of p⇤ , by the property of multivariate normal distribution, we can extract the second bmi = f (mi ; ✓) + "i = Ap2mi + "i , b pb)T , which has the distribution: component of ✓b = (A, ✓ ◆ 2 where "i is the noise term, which follows the normal distribu⇤ pb ⇠ N p , Q2,2 . tion N (0, 2 /T ). Parameter 2 is the single-shot variance for T Authorized licensed use limited to: Chinese University of Hong Kong. Downloaded 1428on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. where Q2,2 is the entry of Q in the second row and the second column. Although Q2,2 depends on the true values A⇤ and p⇤ , which are unknown to us, the inherent range of A⇤ and p⇤ [22] shows that Q2,2 is bounded. We can approximate Fi using ⇣ ⌘T ⇣ ⌘ 1 b = P|M| Fbi Fb T bp2mi 1 Fbi = pb2mi , 2mi Ab and so Q . i=1 Since Pr Ē 6 6 i We approximate the sample variance s2 as follows, s2 = b S(✓) |M| 2 ⇡ . |M| 2 (|M| 2)T Finally, we get the asymptotic confidence interval of p⇤ by the property of t-distribution as follows, s " # 1 |M| ⇤ b Pr |b p p |> p · Q2,2 · t|M| 2,1 ↵/2 6 ↵, |M| 2 T where tk,p is the p-th quantiles of the t-distribution with k degrees of freedom. That is, the confidence interval depends on O( p1T ). Let |M| b 2,2 · t2 C= 2 ·Q |M| 2,1 ↵/2 |M| 2 for a fixed value of ↵. By applying the powering lemma [48], i.e., repeating the algorithm O(log 1 ) times and taking the median, the vanilla network benchmarking method can return pb such that " # r C 1 ⇤ Pr |p̂ p | > log 6 , T Then we can conclude Lemma 1. Proof. We now prove Theorem 1 by showing that, with probability of at least 1 , (a) the optimal link will always remain in the candidate set S, and (b) the number of pulls required for a suboptimal link i to be removed from S is bounded by O(C i 2 log (L/ log (4 i 1 ))). First, we prove (a): Note that link i will be eliminated from S only if there exists some j 6= i and some s > 0 such that (s) (s) 2 s. (5) (s) We denote the event {8s > 0, 8i 2 S, |p̂i pi | 6 2 s } by (s) s (s) s E. On the event E, pi 2 [p̂i 2 , p̂i + 2 ] holds for any (s) link i 2 S in any stage s > 0. and thus, p̂i + 2 s > pi and (s) s p̂j 2 6 pj . Plugging them into (5), we have (s) (s) pi 6 p̂i + 2 s < p̂j ⇣ (s) Pr |p̂i s=1 i2S |S|s(s + 1) s=1 i2S 1 X X 2 s 6 pj , showing that pi < pj , i.e., i is not an optimal link. Therefore, if the event E holds, Algorithm 1 never makes mistakes and must output the correct optimal link in the end. It is sufficient to show that the probability that the event E happens is no less than 1 . pi | > 2 s ⌘ (6) (7) (8) < , where (6) holds by the union bound, (7) is because of Lemma 1, P1 1 < 1, i.e., Pr(E) > 1 and (8) is from s=1 s(s+1) , we can conclude (a). Then we prove (b): We consider the cost complexity when E holds. We show that a suboptimal link i must have been eliminated when i 6 4 · 2 s ; otherwise, it results in a contradiction. Suppose i > 4·2 s and link i is not eliminated (s) in phase s, implying that p̂i + 2 s > p̂max 2 s . Then, (s) (s) pi +2·2 s > p̂i +2 s > p̂max +2 s > p̂1 2 s > p1 2·2 s , holds, i.e., i 6 4 · 2 s , which contradicts with i > 4 · 2 s . Denote the phase in which link i is eliminated by phase si . We have i 6 4 · 2 si . Therefore, the total number of pulls of link i is upper bounded as follows, Ni,si = C22si log si (si + 1)|S| 6 C22si log si (si + 1)L (9) ✓ L 4 4 6 C22si log log (log + 1) i ✓ ✓ ◆◆ i C L 4 =O log , 2 log ◆ (10) (11) (12) i i B. Proof of Theorem 1 p̂i + 2 s < p̂j 1 X X where (9) is from the definition, (10) is because of |S| 6 L, (11) and (12) are because of i 6 4 · 2 si . Then we have (b). Summing over the number of pulls of all links and multiplying it with the cost per pull, we have: ✓ ◆! X X C L 4 Cost(AL INK S EL F I E ) 6 O log · m, 2 log i2L i i m2M which concludes the proof. R EFERENCES [1] A. K. Ekert, “Quantum cryptography based on Bell’s theorem,” Phys. Rev. Lett., vol. 67, pp. 661–663, Aug 1991. [2] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” in Proceedings of the International Conference on Computers, Systems & Signal Processing, 1984, pp. 175– 179. [3] P. Komar, E. M. Kessler, M. Bishof, L. Jiang, A. S. Sørensen, J. Ye, and M. D. Lukin, “A quantum network of clocks,” Nature Physics, vol. 10, no. 8, pp. 582–587, 2014. [4] L. Chen, Q. Chen, M. Zhao, J. Chen, S. Liu, and Y. Zhao, “DDKAQKDN: Dynamic On-Demand Key Allocation Scheme for Quantum Internet of Things Secured by QKD Network,” Entropy, vol. 24, no. 2, p. 149, 2022. [5] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information. Cambridge university press, 2010. [6] W. K. Wootters and W. H. Zurek, “A Single Quantum Cannot be Cloned,” Nature, vol. 299, no. 5886, pp. 802–803, 1982. Authorized licensed use limited to: Chinese University of Hong Kong. Downloaded 1429on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. [7] W. Kozlowski, A. Dahlberg, and S. Wehner, “Designing a Quantum Network Protocol,” in Proceedings of the 16th International Conference on Emerging Networking EXperiments and Technologies, ser. CoNEXT ’20, 2020, p. 1–16. [8] T. Inagaki, N. Matsuda, O. Tadanaga, M. Asobe, and H. Takesue, “Entanglement distribution over 300 km of fiber,” Optics express, vol. 21, no. 20, pp. 23 241–23 249, 2013. [9] V. Krutyanskiy, M. Meraner, J. Schupp, V. Krcmarsky, H. Hainzer, and B. P. Lanyon, “Light-matter entanglement over 50 km of optical fibre,” npj Quantum Information, vol. 5, no. 1, p. 72, 2019. [10] Y. Yu, F. Ma, X.-Y. Luo, B. Jing, P.-F. Sun, R.-Z. Fang, C.-W. Yang, H. Liu, M.-Y. Zheng, X.-P. Xie et al., “Entanglement of two quantum memories via fibres over dozens of kilometres,” Nature, vol. 578, no. 7794, pp. 240–245, 2020. [11] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels,” Phys. Rev. Lett., vol. 70, pp. 1895–1899, Mar 1993. [12] S. Shi and C. Qian, “Concurrent Entanglement Routing for Quantum Networks: Model and Designs,” in Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication, ser. SIGCOMM ’20, 2020, p. 62–75. [13] Y. Zeng, J. Zhang, J. Liu, Z. Liu, and Y. Yang, “Multi-entanglement routing design over quantum networks,” in IEEE INFOCOM 2022-IEEE Conference on Computer Communications. IEEE, 2022, pp. 510–519. [14] C. Li, T. Li, Y.-X. Liu, and P. Cappellaro, “Effective routing design for remote entanglement generation on quantum networks,” npj Quantum Information, vol. 7, no. 1, pp. 1–12, Jan. 2021. [15] A. Farahbakhsh and C. Feng, “Opportunistic Routing in Quantum Networks,” in IEEE INFOCOM 2022 - IEEE Conference on Computer Communications, 2022, pp. 490–499. [16] M. Żukowski, A. Zeilinger, M. A. Horne, and A. K. Ekert, ““Eventready-detectors” Bell experiment via entanglement swapping,” Phys. Rev. Lett., vol. 71, pp. 4287–4290, Dec 1993. [17] J. Li, M. Wang, K. Xue, R. Li, N. Yu, Q. Sun, and J. Lu, “Fidelityguaranteed entanglement routing in quantum networks,” IEEE Transactions on Communications, vol. 70, no. 10, pp. 6748–6763, 2022. [18] M. Liu, J. Allcock, K. Cai, S. Zhang, and J. C. Lui, “Quantum Networks with Multiple Service Providers: Transport Layer Protocols and Research Opportunities,” IEEE Network, vol. 36, no. 5, pp. 56–62, 2022. [19] Y. Zhao, G. Zhao, and C. Qiao, “E2E fidelity aware routing and purification for throughput maximization in quantum networks,” in IEEE INFOCOM 2022-IEEE Conference on Computer Communications. IEEE, 2022, pp. 480–489. [20] J. Helsen and S. Wehner, “A Benchmarking Procedure for Quantum Networks,” npj Quantum Information, vol. 9, no. 1, p. 17, 2023. [21] J.-Y. Audibert and S. Bubeck, “Best Arm Identification in Multi-Armed Bandits,” in COLT - 23th Conference on Learning Theory - 2010, Jun. 2010, p. 13 p. [22] E. Magesan, J. M. Gambetta, and J. Emerson, “Characterizing quantum gates via randomized benchmarking,” Physical Review A, vol. 85, no. 4, p. 042311, 2012. [23] J. Helsen, J. J. Wallman, S. T. Flammia, and S. Wehner, “Multiqubit randomized benchmarking using few samples,” Physical Review A, vol. 100, no. 3, p. 032304, 2019. [24] M. A. Nielsen, “A simple formula for the average gate fidelity of a quantum dynamical operation,” Physics Letters A, vol. 303, no. 4, pp. 249–252, 2002. [25] D. Gottesman, “The Heisenberg representation of quantum computers,” arXiv preprint quant-ph/9807006, 1998. [26] T. Coopmans, R. Knegjens, A. Dahlberg, D. Maier, L. Nijsten, J. de Oliveira Filho, M. Papendrecht, J. Rabbie, F. Rozp˛edek, M. Skrzypczyk et al., “Netsquid, a network simulator for quantum information using discrete events,” Communications Physics, vol. 4, no. 1, p. 164, 2021. [27] E. Even-Dar, S. Mannor, and Y. Mansour, “Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems,” J. Mach. Learn. Res., vol. 7, p. 1079–1105, dec 2006. [28] Y.-A. Chen, Q. Zhang, T.-Y. Chen, W.-Q. Cai, S.-K. Liao, J. Zhang, K. Chen, J. Yin, J.-G. Ren, Z. Chen et al., “An integrated space-to-ground quantum communication network over 4,600 kilometres,” Nature, vol. 589, no. 7841, pp. 214–219, 2021. [29] D. Stucki, M. Legre, F. Buntschu, B. Clausen, N. Felber, N. Gisin, L. Henzen, P. Junod, G. Litzistorf, P. Monbaron et al., “Long-term performance of the SwissQuantum quantum key distribution network in a field environment,” New Journal of Physics, vol. 13, no. 12, p. 123001, 2011. [30] M. Sasaki, M. Fujiwara, H. Ishizuka, W. Klaus, K. Wakui, M. Takeoka, S. Miki, T. Yamashita, Z. Wang, A. Tanaka et al., “Field test of quantum key distribution in the Tokyo QKD Network,” Optics express, vol. 19, no. 11, pp. 10 387–10 409, 2011. [31] L. Ruan, “Minimization of the estimation error for entanglement distribution networks with arbitrary noise,” Phys. Rev. A, vol. 108, p. 022418, Aug 2023. [32] M. G. De Andrade, J. Navas, I. Montaño, and D. Towsley, “On the Characterization of Quantum Flip Stars with Quantum Network Tomography,” in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 01, 2023, pp. 1260–1270. [33] M. Liu, Z. Li, K. Cai, J. Allcock, S. Zhang, and J. C. Lui, “Quantum BGP with Online Path Selection via Network Benchmarking,” in IEEE INFOCOM 2024 - IEEE Conference on Computer Communications, 2024. [34] T. Lattimore and C. Szepesvári, Bandit algorithms. Cambridge University Press, 2020. [35] S. Bubeck, N. Cesa-Bianchi et al., “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” Foundations and Trends® in Machine Learning, vol. 5, no. 1, pp. 1–122, 2012. [36] G. Gao, J. Wu, M. Xiao, and G. Chen, “Combinatorial multi-armed bandit based unknown worker recruitment in heterogeneous crowdsensing,” in IEEE INFOCOM 2020-IEEE Conference on Computer Communications. IEEE, 2020, pp. 179–188. [37] K. Cai, X. Liu, Y.-Z. J. Chen, and J. C. Lui, “An online learning approach to network application optimization with guarantee,” in IEEE INFOCOM 2018-IEEE Conference on Computer Communications. IEEE, 2018, pp. 2006–2014. [38] X. Liu, J. Zuo, X. Chen, W. Chen, and J. C. S. Lui, “Multi-layered Network Exploration via Random Walks: From Offline Optimization to Online Learning,” in Proceedings of the 38th International Conference on Machine Learning, vol. 139. PMLR, 18–24 Jul 2021, pp. 7057–7066. [39] K. Jamieson and R. Nowak, “Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting,” in 2014 48th Annual Conference on Information Sciences and Systems (CISS). IEEE, 2014, pp. 1–6. [40] A. Garivier and E. Kaufmann, “Optimal Best Arm Identification with Fixed Confidence,” in 29th Annual Conference on Learning Theory, vol. 49. PMLR, 23–26 Jun 2016, pp. 998–1027. [41] M. Simchowitz, K. Jamieson, and B. Recht, “The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime,” in Proceedings of the 2017 Conference on Learning Theory, vol. 65. PMLR, 07–10 Jul 2017, pp. 1794–1834. [42] H. Jiang, J. Li, and M. Qiao, “Practical algorithms for best-k identification in multi-armed bandits,” arXiv preprint arXiv:1705.06894, 2017. [43] S. Bubeck, T. Wang, and N. Viswanathan, “Multiple Identifications in Multi-Armed Bandits,” in Proceedings of the 30th International Conference on Machine Learning, vol. 28, no. 1. PMLR, 17–19 Jun 2013, pp. 258–265. [44] Y. Zhou, X. Chen, and J. Li, “Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing,” in Proceedings of the 31st International Conference on Machine Learning, vol. 32, no. 2. PMLR, 22–24 Jun 2014, pp. 217–225. [45] V. Gabillon, M. Ghavamzadeh, and A. Lazaric, “Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence,” in Advances in Neural Information Processing Systems, vol. 25, 2012. [46] A. K. Bera, “The use of linear approximation to nonlinear regression analysis,” Sankhyā: The Indian Journal of Statistics, Series B, pp. 285– 290, 1984. [47] J. M. Epstein, A. W. Cross, E. Magesan, and J. M. Gambetta, “Investigating the limits of randomized benchmarking protocols,” Phys. Rev. A, vol. 89, p. 062321, Jun 2014. [48] M. R. Jerrum, L. G. Valiant, and V. V. Vazirani, “Random generation of combinatorial structures from a uniform distribution,” Theoretical Computer Science, vol. 43, pp. 169–188, 1986. Authorized licensed use limited to: Chinese University of Hong Kong. Downloaded 1430on August 15,2024 at 02:47:32 UTC from IEEE Xplore. Restrictions apply. この論文「**LINK SELFIE: Link Selection and Fidelity Estimation in Quantum Networks**」（IEEE INFOCOM 2024）が解いている問題の**入力、出力、制約条件、目的関数**は以下のように整理できます。 --- ### 🔶【問題の概要】 量子ネットワークにおいて、**複数の量子リンク（エンタングルメントリンク）**の中から、**最も忠実度（fidelity）が高いリンクを選択**し、その**忠実度を高精度に推定**したい。 ただし、忠実度は事前には不明で、すべてのリンクを均等に評価するにはコスト（量子リソース消費）が高すぎる。 --- ## 🔹1. 入力（Input） * `L = {l₁, l₂, ..., l_L}`： ソースノードSとデスティネーションノードDを結ぶ **L本のエンタングルメントリンク**の集合。それぞれのリンク `lᵢ` は不明な忠実度 `fᵢ ∈ [0, 1]` を持つ。 * `M = {m₁, m₂, ..., m_M}`： **バウンス回数**（リンクを何回往復させるか）の集合。 * `T`： 各バウンス回数ごとの**繰り返し回数（実験回数）**。 * `δ ∈ (0, 1)`： 信頼度（たとえば95%信頼区間などに相当）。 --- ## 🔹2. 出力（Output） * `l*`： 最も忠実度が高いと判断されたリンク `l* ∈ L` * `f̂*`： 選ばれたリンク `l*` の**推定忠実度**。誤差は高確率で小さい。 --- ## 🔹3. 制約条件（Constraints） * **未知の忠実度**： 各リンクの忠実度 `fᵢ` は事前にわからず、ネットワークベンチマーク（qubitを何度も送る）によって推定する必要がある。 * **リソース制限**： 各リンクの評価には\*\*量子リソース（エンタングルメント消費、バウンス数）\*\*がかかる。全リンクを同程度に調査することは非効率。 * **精度要件**： 忠実度の推定誤差 `|f̂ᵢ - fᵢ| < ε` かつ、全体として `1 - δ` の確率で正しい最適リンクを選出することが求められる。 --- ## 🔹4. 目的関数（Objective Function） ### **目的：** 最小のコストで、最も忠実度が高いリンク `l*` を見つけ、その忠実度 `f*` を高精度に推定する。 ### **数式表現：** ```math \min \text{Cost}(A) = \sum_{i \in L} \sum_{m \in M} N_{i,m} \cdot m ``` ここで、 * `N_{i,m}` はリンク `i` に対してバウンス数 `m` を用いてネットワークベンチマークを行った回数。 * `m` は1回の実験あたりの消費リソース。 --- ## 🔸補足（手法の概要） * 問題は「**多腕バンディットにおけるベストアーム識別問題（Best Arm Identification, BAI）**」として定式化されている。 * 提案手法 **LINK SELFIE** は、信頼区間ベースで劣ったリンクを早期に削除し、必要なリンクにだけリソースを集中させる。 * ネットワークベンチマーク結果に対して、非線形回帰（指数モデル）を適用して忠実度を推定。 * コスト（量子リソース消費）に理論的な上限を設け、他の手法より効率が良いことを証明。 --- ご希望であれば、数式付きのLaTeX形式や、ベストアーム識別問題と従来手法との比較表も作成できます。 ** Q. LinkSelfie の論文の問題を拡張したい。 以下のように拡張した問題の入力、出力、制約条件、目的関数を説明して。 ノードS〜ノードD 間のリンク集合 Ｌ だけでなく、 ノードS〜ノードD_n間のリンク集合 L_n (1 <= n <= N, N はノードSの隣接ノード数)がそれぞれ入力される。 ノードS〜ノードD_n間の重要度 I_n (0〜1 の値) が入力として与えられる。 総バウンスコスト C が入力として与えられる。 この時、ノードS〜ノードD_n のノードペアの中で、 K 個のノードペア (S, D_s_1), (S, D_s_2), ... (S, D_s_K) における 忠実度が最大のリンクをそれぞれ発見する。 ただし、発見するリンクのノードペア数 K は、 重要度と忠実度の積の総和、つまり I = \sum_{k = 1}^K I_s_k * F_s_k が最大となるように定める。 ここで F_n は (S, D_n) 間において忠実度の最大のリンクの忠実度である。 A. この拡張問題は、複数のノードペア (S, Dₙ) に対して、限られたリソース（バウンスコスト）の中で、重要なノードペアの 高忠実度リンクを選定する最適化問題です。以下に、この問題の形式的な定義を記述します。 🔶 問題名（例）： Weighted Multi-Pair Link Selection and Fidelity Estimation under Cost Constraint 🔷 1. 入力（Input） 🔸 ネットワーク構成 - N ∈ ℕ⁺： ソースノード S に接続している隣接ノードの数（= ノードペア数） - Lₙ = {lₙ₁, ..., lₙ_Lₙ}： 各ノードペア (S, Dₙ) における量子リンク集合。各リンク lₙⱼ は未知の忠実度 fₙⱼ ∈ [0,1] を持つ。 🔸 メタ情報 - Iₙ ∈ [0, 1]： ノードペア (S, Dₙ) の重要度（重み） - C ∈ ℝ⁺： 使用できる総バウンスコスト（＝量子リソース上限） 🔷 2. 出力（Output） - ノードペア選定集合 S_sel = {n₁, n₂, ..., n_K}（|S_sel| = K） - 各選ばれたノードペア nₖ ∈ S_sel に対して、 最大忠実度リンク lₙₖ* ∈ Lₙₖ とその推定忠実度 f̂ₙₖ* 🔷 3. 制約条件（Constraints） 1 バウンスコスト制約： - 評価にかかった総バウンスコストの合計が C を超えてはならない - すなわち、 ∑n=1N∑l∈LnCostn(l)≤C∑_{n=1}^N ∑_{l ∈ Lₙ} Cost_n(l) ≤ C n=1∑N​l∈Ln​∑​Costn​(l)≤C ※Cost_n(l) はそのリンクにおけるベンチマークのバウンス数（＝リンク評価コスト） 2 忠実度は未知： - 各リンク lₙⱼ の忠実度 fₙⱼ は、ネットワークベンチマーク（複数回バウンス）を通じて推定される 3 忠実度推定精度（信頼性）： - 各推定値 f̂ₙⱼ は、ある信頼度1−δで正確性が保証される 🔷 4. 目的関数（Objective Function） 選んだ K 個のノードペア (S, Dₙₖ) に対して、 各ペア内で最良リンク lₙₖ* を選び、以下の価値関数を最大化する： Itotal=∑k=1KInk∗F^nkI_total = ∑_{k=1}^K I_{n_k} * F̂_{n_k} It​otal=k=1∑K​Ink​​∗F^nk​​ ここで： - I_{n_k} はノードペアの重要度 - F̂_{n_k} はそのノードペア内の最良リンクの推定忠実度 🔷 要約（形式的な最適化問題） mathematica SVG ImageCopySVG ImageEdit 最大化： I_total = ∑_{n ∈ S_sel} I_n * F̂_n* 制約： ∑_{n=1}^N ∑_{l ∈ L_n} BenchmarkCost(l) ≤ C S_sel ⊆ {1, 2, ..., N}, |S_sel| = K（K は自動で決まる） 🔸 この拡張の本質的なポイント - 単一リンク選定（元のLinkSelfie） → 複数ペア×リンクの選定（マルチリンク・マルチペア問題） - 静的な目標（忠実度最大） → 動的な目標（重要度×忠実度最大） - 固定K → Kは結果に応じて最適に変化 🔸 解法に向けた示唆（発展） この問題は以下を融合したリソース制約付きの最適ペア・リンク探索問題として捉えられます： - BAI（Best Arm Identification）× 多目的最適化 - 重要度付き knapsack + adaptive sampling - 各ペアで局所的に BAI をしつつ、ペア間で 重要度×見込み忠実度の期待値を最大化するように選定 必要であれば、これを実装可能な擬似コード設計や、アルゴリズム構成（段階的フェーズスケジューリング）の提案にも進め られます。どうされますか？ ** Q. Weighted Multi-Pair Link Selection and Fidelity Estimation under Cost Constraint 問題の、 比較的単純で、なおかつ良好な解が得られると期待されるアルゴリズムを示して。 アルゴリズムの実行例も示して A. 以下に、あなたの定義した 「Weighted Multi-Pair Link Selection and Fidelity Estimation under Cost Constraint」 に対して、 - 比較的単純 - 実用的に良好な解が期待できる - 逐次的で実装容易なアルゴリズム を提案し、実行例（手計算ベース）も示します。 ✅ アルゴリズム案： Greedy Pairwise BAI with Budget-Aware Scheduling 🔸 アイデア概要 1 各ノードペア (S, Dₙ) ごとに「少しだけ」リンク評価を行い、最良リンクの推定忠実度 f̂ₙ を取得 2 それを基に、Iₙ × f̂ₙ が高い順に並べ、価値効率の良いノードペアから順に精密評価 3 コスト C を超えない範囲で、BAIにより最良リンクを選定していく 🔸 擬似コード python SVG ImageCopySVG ImageEdit Input: - ノードペア集合 {D₁, ..., D_N} - 各ペアのリンク集合 Lₙ と重要度 Iₙ - バウンスコスト予算 C - 初期評価回数 T₀, 信頼度 δ Step 1: 初期推定（各ノードペアにT₀回ずつ均等評価） for each n in 1..N: for each link l in Lₙ: evaluate link l using T₀回ベンチマーク → 推定忠実度 f̂ₙₗ Let l*ₙ = argmax_l f̂ₙₗ Set f̂ₙ = f̂ₙₗ* （最良リンクの忠実度） Compute 価値スコア vₙ = Iₙ × f̂ₙ Step 2: 優先度順にペアを並び替え Sort all pairs by vₙ in descending order → Q = [(n₁,v₁), (n₂,v₂), ...] Step 3: 各ペアに本格BAI実行（予算を消費） RemainingCost = C - InitialCost Result = [] for (n, v) in Q: Estimate cost_required for BAI(n) if cost_required <= RemainingCost: Run BAI to find best link in Lₙ → f̂ₙ* Append (n, f̂ₙ*, Iₙ) to Result RemainingCost -= cost_required else: break Output: - 選ばれたノードペア集合と各最良リンクの忠実度 - 最大化された I_total = Σ Iₙ × f̂ₙ* ✅ 実行例 🔸 前提 n（ノードペア） Iₙ（重要度） リンク候補（忠実度） 1 0.9 [0.85, 0.80] 2 0.5 [0.70, 0.75, 0.60] 3 0.8 [0.60, 0.58] 4 0.3 [0.95, 0.90] - コスト予算 C = 80 バウンス - 初期評価回数 T₀ = 5 per link → 初期コスト = (2+3+2+2) × 5 = 45 バウンス消費 🔸 Step 1：初期推定 n 最良リンク f̂ₙ vₙ = Iₙ × f̂ₙ 1 0.85 0.765 2 0.75 0.375 3 0.60 0.480 4 0.95 0.285 🔸 Step 2：並べ替え（価値順） 順序：1 → 3 → 2 → 4 🔸 Step 3：順次BAI ・ノードペア1にBAI（仮に 20 バウンス消費） → f̂₁* = 0.86（高精度推定） ・ノードペア3にBAI（仮に 10 バウンス） → f̂₃* = 0.62 → 残コスト：80 − 45 − 20 − 10 = 5（終了） 🔸 出力結果 選ばれたペア：n=1, n=3 忠実度と重要度： - (1) I₁ × f̂₁* = 0.9 × 0.86 = 0.774 - (3) I₃ × f̂₃* = 0.8 × 0.62 = 0.496 → 合計目的関数値（I_total） = 1.270 ✅ 特徴・評価 項目 内容 長所 単純で実装容易、初期評価に基づく有望ペアの優先選定 短所 初期評価が粗すぎると誤った選定に陥る可能性あり 改善案 初期ステージを adaptively 決める or BAIの一部予測 ご希望であれば、これを Pythonコード化したものや、BAIのアルゴリズム部分の統合, より効率的な選定戦略（例：価値密 度Iₙ×fₙ/コスト）による拡張版も提供可能です。希望されますか？ ** Q. 共通リソースからとってきているが、リソースはリンクに対してわりあてられている A. ネットワークを運用している人のお金の問題で決まる、GAFA がやるなら、バウンスをたくさん用意できるだろうし…。 段落の一文目をトピックセンテンスとして、段落の主旨を明確にして。 各トピックセンテンスだけを読んで、論文の論旨が理解できるように書いて。 論理が飛躍している箇所は適宜補って。 説明が不足している箇所は説明を追加して。 情報科学分野の学術論文にふさわしい内容にして。 大崎博之氏の文体にできるだけ近づけて。大崎博之氏の論文の PDF ファイルは以下から入手できる。https://lsnl.jp/~ohsaki/papers/list-workshop.html --- 以下の論文を以下の章構成にリライトして。 1. はじめに 背景 量子ネットワークにおいて忠実度を高いリンクを効率的に判定する手法 LinkSelFiE が提案されている 動機 LinkSelFiE は通信需要を考慮していないが、現実には通信需要が高くかつ忠実度の高いリンクの判定が望まれる 目的 少ない計測 (バウンス) により利用率 x 忠実度が高いリンクの判定を可能とする 2. 量子ネットワークにおけるリンク忠実度計測問題を、通信需要を重 み付け要素として組み込む形で定式化する入力、出力、制約条件、目的関 数 3. 提案手法の説明 4. 実験の目的、実験の条件、結果、考察 5. まとめと今後の課題 だ・である調で書いて。「まとめと今後の課題」以外の章は、それぞれ 4 段 落に増やして、各段落は 200 文字程度にして。段落の一文目をトピックセン テンスとして、段落の主旨を明確にして。各トピックセンテンスだけを読んで、 論文の論旨が理解できるように書いて。論理が飛躍している箇所は適宜補って。 説明が不足している箇所は説明を追加して。情報科学分野の学術論文にふさわ しい内容にして。日本語の文体は、大崎博之氏の文体にできるだけ近づけて。 大崎博之氏の論文の PDF ファイルは以下から入手できる。 https://lsnl.jp/~ohsaki/papers/list-workshop.html --- [全文] 7月中にどこまで進めるか 8月1日までに ある程度のスライド完成 だれ向けにスライドをつくるか インターネットアーキテクチャの分野 なにを知らないか考える 学生とかも聞きにくる 分からない人向けに説明する 量子ネットワークを分からない人もくる '何を話したいか'から考える だれに何を伝えたいか 卒研とソサイエティでは内容が異なる アプローチは正しい 25までにスライドのコンパイルをできるようにする orgモードからつくってコンパイルできるようにする 29までにyutoさんにみてもらう 29はおそい 1回目の発表練習にどの程度のものを準備するか 全員に意見がくる 1回目に完璧はもとめられてない yutoさんとスケジュールをきめる yutoさんの力をどう借りるか 共著の先輩方のリソースをどう使うか スライドつくるときは各スライドで何を伝えたいか(主張)決める スライドの何枚にするのかを最初に決める ここを相談する。骨格の部分を相談する 何枚の構成か それぞれのスライドで何を伝えるのか 骨格を ソサイエティの発表までに 何かやっとくといい ソサイエティの内容から発展した結果を得られるようにする 研究は複数枚の原稿になる 国際会議のフィードバックを打診する 雑誌までいけたらいく 卒研の発表は自分でやったことを説明する 国際会議のどこに出したいか geminiやgptでしらべる infocom,icc,compsac すぐcompsacはきつい iccなど6ページの学会にだす 量子ネットワーク専門の学会があるかも iccのフィードバックをもとに出すのがいい 中身 なにをするか ここから進化させるためには 同じ内容で6ページかいてみる 貪欲法をかえる 新しい手法の提案 ニーズがあってそれに答えるような手法が必要 手法を変えることにどういう意味があるのか inputを増やす 手を動かすのと同時並行でおこなう すぐできる実験を動かしたりする 今すぐ論文をかくのが大事(今の論文を6ページにするならどうするか) input3 手をうごかす4 考える3 何を明らかにしているか 測定資源を減らす この研究で何をしたいか 自分の研究が何をする研究なのかを定める ソサイエティのときのストーリーを大事にする これをもとに他の研究は何をしているか、実験はこれでいいのかを考える どういう実験でどういうスコアを出したらいいのかなど 次回 木曜3限以外 時間セットで候補3つくらい30ー1時間くらい yutoさんとうまくやる 研究も yutoさんと話したあとshotaさんとはなす shotaさんとyutoさんはセットで 分担orブラッシュアップ