Applied Science, Faculty of
Engineering, School of (Okanagan)
DSpace
UBCO
Farahbakhsh, Ali
Master of Applied Science - MASc
University of British Columbia
Unlike classical routing algorithms, quantum routing algorithms make use of entangled states - a type of resources that have a limited lifetime and need to be regenerated after consumption. In a nutshell, quantum routing algorithms have to use these resources efficiently, while optimizing some objectives such as the total waiting time. Current routing algorithms tend to keep a routing request waiting until all of the resources on its path are available. In this thesis, we introduce a new way of managing entanglement resources in an opportunistic fashion: a request can move forward along its path as soon as possible (even if some resources on its path are not ready). We show that this opportunistic approach is fundamentally better than conventional approaches. In particular, our results indicate that this new approach achieves a 30-50% improvement in the average total waiting time and average link waiting time compared with several state-of-the-art routing algorithms. As a by-product of this work, we develop a new simulator for quantum routing, which can be used to evaluate various design choices under different scenarios.
Opportunistic Routing in QuantumNetworksbyAli FarahbakhshB.Sc., Sharif University of Technology, 2019A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Electrical Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)September 2022© Ali Farahbakhsh, 2022The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Opportunistic Routing in Quantum Networkssubmitted by Ali Farahbakhsh in partial fulfilment of the requirementsof the degree of Master of Applied ScienceChen Feng, School of EngineeringSupervisorZheng Liu, School of EngineeringSupervisory Committee MemberJulian Cheng, School of EngineeringSupervisory Committee MemberAlexandra Fedorova, Department of Electrical and Computer EngineeringUniversity of British Columbia, VancouverUniversity ExamineriiAbstractUnlike classical routing algorithms, quantum routing algorithms makeuse of entangled states—a type of resources that have a limited lifetime andneed to be regenerated after consumption. In a nutshell, quantum rout-ing algorithms have to use these resources efficiently, while optimizing someobjectives such as the total waiting time. Current routing algorithms tendto keep a routing request waiting until all of the resources on its path areavailable. In this thesis, we introduce a new way of managing entanglementresources in an opportunistic fashion: a request can move forward alongits path as soon as possible (even if some resources on its path are notready). We show that this opportunistic approach is fundamentally betterthan conventional approaches. In particular, our results indicate that thisnew approach achieves a 30-50% improvement in the average total waitingtime and average link waiting time compared with several state-of-the-artrouting algorithms. As a by-product of this work, we develop a new sim-ulator for quantum routing, which can be used to evaluate various designchoices under different scenarios.iiiLay SummaryQuantum computers have the potential to change our lives profoundly.From drug discovery to digital security, this new type of computation allowsus to tackle some of the most pressing problems of our modern world. Inorder to harness the power of such computers, we require networks that canconnect them all over the globe. In this thesis, we propose a way to designmore efficient networks of quantum computers.ivPrefaceAll of the work presented in this thesis was conducted under the supervi-sion of Prof. Chen Feng. The material presented in Chapter 2, and most ofthe material presented in chapters 3 and 4 were published in the INFOCOMconference [FF22]. I was the lead investigator, responsible for the conceptformation, mathematical analysis, and simulations. Chen Feng was involvedin selecting the field of study, and revising the results and the material. Weare also planning to publish the material of this thesis in a journal extensionto our first paper.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Quantum Networks . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Quantum Routing . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . 9Chapter 2: Opportunistic Routing . . . . . . . . . . . . . . . . 112.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 k-opportunism . . . . . . . . . . . . . . . . . . . . . . . . . . 14Chapter 3: Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 163.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.1.1 Network, Nodes, and Links . . . . . . . . . . . . . . . 16viTABLE OF CONTENTS3.1.2 Entanglement Generation and Swapping . . . . . . . . 163.1.3 Waiting Time . . . . . . . . . . . . . . . . . . . . . . . 173.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.2.1 A Single Request . . . . . . . . . . . . . . . . . . . . . 183.2.2 A Group of Requests in the Same Direction . . . . . . 193.2.3 Transmission Rate . . . . . . . . . . . . . . . . . . . . 253.2.4 Further Investigation . . . . . . . . . . . . . . . . . . . 30Chapter 4: Simulations . . . . . . . . . . . . . . . . . . . . . . . 354.1 Numerical Simulations for Line Networks . . . . . . . . . . . 354.2 QNS-Lite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.3.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.3.2 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 414.3.3 Methodology . . . . . . . . . . . . . . . . . . . . . . . 414.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Chapter 5: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 465.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54Appendix A: Qubit, Entanglement, and Protocols . . . . . . . . . . 54A.1 Qubit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54A.2 Entanglement . . . . . . . . . . . . . . . . . . . . . . . . . . . 56A.3 Teleportation . . . . . . . . . . . . . . . . . . . . . . . . . . . 56A.4 Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59viiList of TablesTable 4.1 Average link waiting time in the MG algorithm . . . . 43viiiList of FiguresFigure 1.1 A quantum network. . . . . . . . . . . . . . . . . . . . 2Figure 1.2 Teleportation. . . . . . . . . . . . . . . . . . . . . . . 3Figure 1.3 Swapping. . . . . . . . . . . . . . . . . . . . . . . . . 4Figure 1.4 Swapping on a chain of nodes. . . . . . . . . . . . . . 4Figure 2.1 A simple opportunistic routing example. . . . . . . . 12Figure 2.2 Another example for opportunistic routing. . . . . . . 13Figure 2.3 An example of the 2-opportunistic approach. . . . . . 14Figure 4.1 Transmission rate in a line network and its bounds. . 36Figure 4.2 Transmission rate for different values of pgen. . . . . . 37Figure 4.3 Transmission rate for different values of M . . . . . . . 38Figure 4.4 Transmission rate based on M and pgen. . . . . . . . 39Figure 4.5 The stochastic convergence of the transmission rate. . 40Figure 4.6 The modular structure of our simulator. . . . . . . . . 41Figure 4.7 Average total waiting time in a grid network, withthe fixed scenario M = 5, N = 20, L = 30, k = 1,and pswap = 1. . . . . . . . . . . . . . . . . . . . . . . 43Figure 4.8 Average total waiting time in a grid network, withthe fixed scenario M = 5, N = 20, L = 6, k = 1, andpswap = 0.8. . . . . . . . . . . . . . . . . . . . . . . . . 44Figure 4.9 Average total waiting time in a grid network, with thefixed scenario N = 20, L = 30, k = 1, pswap = 0.8,and pgen = 0.8. . . . . . . . . . . . . . . . . . . . . . . 45Figure 4.10 Average total waiting time in a grid network acrossdifferent opportunism degrees, with the fixed scenarioN = 20, L = 30, pswap = 0.8, and pgen = 0.8. . . . . . 45ixGlossaryentanglement A special quantum property between two or more qubits. Itis one of the main phenomena that separates quantum physics fromclassical physics. 3GHZ Greenberger-Horne-Zeilinger. 8NISQ Noisy Intermediate-Scale Quantum. 1QKD Quantum Key Distribution. 1qubit The quantum counterpart of a classical bit. 2repeater A quantum device capable of performing teleportation and swap-ping. 4swapping A quantum protocol establishing entanglement between two nodesby consuming their respective entanglement with a third node. 3teleportation A quantum protocol enabling the transfer of quantum infor-mation without using a physical medium during the transmission. 3xAcknowledgementsI want to thank my supervisor, Chen Feng, for his guidance and men-torship during my studies. He helped me take the first steps of being a re-searcher by teaching me important skills that form the basis of a researcher’sprofessional approach. He was kind and considerate, and let me take theprocess at my own pace.I am also grateful of my committee members, who helped me polish thisthesis by asking detailed questions. Finally, I thank Yves Lucet for theLatex template.xiTo my parentsRoqayye and MostafaTo my brotherAmirrezaAnd to my closest friendYasamanxiiChapter 1Introduction1.1 Quantum NetworksOne of the most exciting technologies of our modern world is quantumcomputing. Initially inspired by the physicist Richard Feynman [Fey82],the notion of a quantum computer has evolved to encompass diverse andintriguing avenues of computation. Originally envisioned to provide a moreaccurate simulation of the physical, seemingly quantum world we are liv-ing in, researchers have now designed many computational algorithms thatharness the power of quantum physics. Perhaps the most famous exam-ples of such algorithms are Grover’s search [Gro96] and Shor’s factoring ofprime numbers [Sho94], which enable quadratic and exponential speedupsin comparison with existing classical algorithms, respectively.The benefits of quantum technology are not limited to computation.Starting with the seminal work in [BB14], the notion of Quantum Key Dis-tribution (QKD) has been an important research subject. QKD enables twoparties to establish unconditionally secure communication by sharing a se-cret key, even in the presence of an eavesdropper. This clearly demonstratesthat the underlying quantum principles enable privacy as well as a boost incomputation.Although, as shortly discussed above, a single quantum computer hasnontrivial benefits, its functionality is limited after all. Like a classicalcomputer, there is only so much that a single quantum computer can do.The next step is to extend applications and functionalities to a networkof quantum computers. There are two main motivations for this exten-sion. First, since we are in the Noisy Intermediate-Scale Quantum (NISQ)era [Pre18], current quantum hardware has limited capability to performarbitrary computations. Therefore, to enable applications ranging fromchemistry [MEAG+20] to machine learning [BWP+17], we can think of dis-tributed quantum computing, in which we leverage the power of severalquantum computers [VMD16]. Second, since we would like to extend un-conditional security to a global scale, and therefore to a global QKD system,we require a global network of quantum devices.11.1. Quantum NetworksBuilding on this vision, we can readily think of a quantum internet [Kim08,WEH18], in which quantum devices are communicating in a global scale,providing computational and security-related benefits. Such a massive sys-tem, like any other complex system, has numerous design choices rangingfrom infrastructure to abstract algorithms. In this thesis, we focus on a par-ticular aspect of such networks, which is in itself inherent to designing anynetwork: routing. we will introduce quantum routing in the next section,paving our way to an introduction of our contributions. Before that, weintroduce the fundamentals of quantum networks.Like any other network, quantum networks are composed of nodes andlinks, as shown in Figure 1.1. The nodes of a quantum network are generallyFigure 1.1: A quantum network is composed of nodes (circles) and links(lines).quantum devices, which can be abstracted as devices that can store, com-pute, and communicate quantum information. This information is usuallycaptured by the concept of qubit, which is the quantum counterpart of aclassical bit1.The links of a quantum network are a bit more complex. Physically, wehave the transmission medium, e.g., optical fiber. However, the transmissionquality over a physical link decreases exponentially as the length of the linkincreases [PLOB17, PGPBL09, KMSD19, ABC+21, TGW14]. Therefore,although adequate for qubit transfer between near nodes, physical links fallshort of supporting long-range communication. The classical remedy forthis shortcoming is using repeaters that copy the signal several times, untilit reaches the destination. Unfortunately, qubits cannot be copied due tothe no-cloning theorem [WZ82].1See the Appendix for a mathematical definition.21.1. Quantum NetworksTo enable communication over long distances, researchers have comeup with two main quantum protocols: teleportation [BBC+93] and swap-ping [ZZHE93]. Both of these protocols use quantum entanglement2, whichis a special quantum property shared between two or more qubits. To seethis, we provide a brief explanation of how teleportation and swapping work.In teleportation, entanglement between a pair of qubits is consumedthrough a series of local quantum operations and classical communication,in order to transfer a third data qubit from a node to another node. Notethat in this transfer of quantum information, the physical medium is notused, hence the name teleportation. Figure 1.2 shows a schematic depictionof this protocol.Figure 1.2: A schematic representation of teleportation. The small yellowcircle is the data qubit, and the small green circles represent a pair of en-tangled qubits, each residing in a network node. The black line representsa physical link, and the purple line shows entanglement.The important point about teleportation is the fact that, although itallows two entities to communicate without a physical medium, sharing apair of entangled qubits itself requires such a medium. Therefore, we cannotsolve the problem of communication over a long distance using only telepor-tation. This is where swapping comes into the picture. During swapping,entangled qubits between two nodes with an intermediate node are con-sumed to establish entanglement between the two outer nodes. Figure 1.32See the Appendix for a mathematical introduction of entanglement, teleportation, andswapping.31.1. Quantum Networksshows a simple swapping scenario.Figure 1.3: A schematic representation of swapping. The small green circlesrepresent entangled qubits. The purple line shows entanglement.With swapping in hand, we can achieve long-distance communication.This is accomplished by putting a chain of nodes3 between the endpoints,with entanglement between adjacent nodes. The distance between the ad-jacent nodes is such that physical transmission is suitable for transferringthese entangled qubits. The nodes perform a series of swapping operationsthat result in establishing entanglement between the endpoints. A finalteleportation step can then realize qubit transfer between these endpoints.Figure 1.4 shows this chain of nodes and the resulting entanglement betweenthe endpoints.Figure 1.4: As a result of successive swapping over a chain of nodes, weobtain entanglement between the endpoints.3These intermediate nodes are called repeaters [BDCZ98], in analogy with the classicalcase. For simplicity, we can assume that they are quantum computers as well.41.2. Quantum RoutingBased on these explanations, we can see that the actual links of a quan-tum network are the entangled pairs between the nodes. Entanglement actsas a virtual link in the network, and can be consumed like a resource. Fromnow on, unless explicitly stated otherwise, we use the term link to refer toentanglement between the nodes of a network.Now that we have introduced quantum networks, we finish this sectionby mentioning their main limitations. We list these limitations as follows:− Current prototypes for quantum computers have rather limited stor-age capacity for qubits [BRA+19]. This limits the number of entangle-ments (i.e., links) they can establish with other nodes in the network.− Qubits have different quality metrics, such as fidelity [Wil13]. Gen-erally, the quality of a qubit decreases over time (due to noise andinteraction with the environment). A qubit may become useless aftera certain threshold, which depends on the application (e.g., entangle-ment distillation [KRH+17]). In other words, qubits, and thereforelinks, have finite lifetimes.− The process of generating a link is probabilistic [SQ20, CRDW19,KMSD19]. In each attempt, there is a probability of failure.− Similar to link generation, each swapping attempt is also probabilisticwith a certain failure probability [ABC+21].1.2 Quantum RoutingSwapping allows two nodes on a line network to communicate with eachother. However, a general quantum network may have a much more complextopology, and different pairs of nodes may want to communicate with eachother. There has to be a way to assign the resources, i.e., links, of thisnetwork to different requests. Since swapping on a chain is possible once wehave a path between two nodes, the problem of communicating in a generalquantum network can be reduced to assigning different paths to the requests.This problem is called quantum routing.There are several properties that make quantum routing somewhat unique.First of all, paths are not selected only from the physical links, and theycontain virtual links (i.e., entangled pairs) as well. Second, the dynamicnature of quantum networks causes specific challenges. For instance, thelinks of a selected path may expire during the transmission. Similarly, whenwaiting for a link to get ready, it is possible that an already existing link51.3. Contributionsexpires. All in all, quantum routing should consider this dynamicity whenassigning links to different requests.Based on the these explanations, and by going through the existing lit-erature, a typical routing algorithm conforms to the following structure:1. Reception: First, a number of routing requests are generated in thenetwork.2. Path Selection: Based on certain rules (see, e.g., [VMSL+13]), sev-eral paths are selected for every request, either offline [SQ20] or on thefly. The links of these paths are usually reserved for the correspondingrequest.3. Generation: Links are generated along the paths for every request.4. Forwarding: Finally, once all of the required links are ready alonga path, the corresponding request is forwarded based on a certainswapping pattern.Note that routing algorithms do not necessarily follow this order. For ex-ample, the algorithm proposed in [PKT+19] performs the “Path Selection”stage after the “Generation” stage. Or, more intuitively, the generationprocess can run in parallel to the routing mechanism. The important pointabout this structure is the conceptual framework that it proposes for routingalgorithms in a quantum network.1.3 ContributionsOur main contribution in this thesis is introducing and analyzing op-portunistic routing for quantum networks. In a nutshell, existing routingalgorithms are rather conservative, since they start the forwarding stageonly after all of the links are generated. This unnecessary waiting increasesthe waiting time of the requests, while also risking the expiry of the alreadyestablished links. We show that routing can be more efficient by proposing anew forwarding stage for these algorithms. Briefly, our proposed forwardingstage prompts the requests to start the swapping as soon as it is possible.We demonstrate the superiority of our approach by showing its effects onthe waiting time and transmission rate of requests. Finally, we also pro-vide a simulator that serves as a playground to compare different routingalgorithms.61.4. Related Work1.4 Related WorkThe existing literature on quantum networks is related to our analysis ofopportunism from several perspectives. We go through these perspectiveshere.First, we have the papers that propose different quantum routing algo-rithms. Quantum routing has quickly become a hot topic for research inthe quantum networking community, perhaps partly because of the familiarnature that it has to routing in classical networks. A systematic analysis ofentanglement as a virtual link can be dated back to the paper [SMI+16]. Asexplained in this paper, previous approaches to quantum routing were eitherconcentrated on alternatives of routing, like network coding, or were con-cerned with physical routing, e.g., routing photons over physical links. Theauthors of [SMI+16] proposed a routing on a higher level, which is routingentanglement (virtual links) in the network. Alongside this new perspective,this piece of work proposed ways of distributing entanglement in the ringand sphere topologies, and a decentralized routing protocol. Their analysisis based on the limitations of a quantum network, and they specifically men-tion that their routing algorithm requires only local information about thenetwork state. Based on the dynamic nature of such networks, the tradeoffbetween local and global information is one of the most important challengesof quantum routing.The work proposed in [SMI+16] has led to several papers. In [CRDW19],perhaps as a continuation of [SMI+16], the authors first propose two differentways of constructing a virtual graph (i.e., entangled links) over the physicalnetwork, and then analyze two routing algorithms. These routing algorithmsare inspired by the classical greedy routing, and a local best-effort approach.They also analyze two different approaches of supplying entanglement in thenetwork. In the first approach, entanglement is generated only when there isa request, while in the second approach there exists a continuous generationof entanglement, regardless of the requests. Of course, selecting the patternof generation becomes a challenge in the second approach, while it alsointuitively decreases the waiting time of a new request. Here, once again,the proposed routing algorithms try to use local state information.A similar local best-effort approach is also a topic of study in [PKT+19].Here, the authors analyze using local information in a best-effort approachfor carving a way from the source to the destination. Furthermore, theypropose a multi-path approach, in which several paths are selected for arequest. Their results demonstrate the increased efficiency when assigningseveral paths. Intuitively, this is a correct result, since the links are dynamic71.4. Related Workand a once-suitable path may become stale.A somewhat different approach to routing is proposed in [VMSL+13].Here, the authors use the classical Dijkstra approach [Dij59], shifting thequantum dynamics to the metric used in this algorithm. That is, theypropose several new cost metrics for the links of a quantum network, andthen use these costs during Dijkstra’s algorithm.Another substantial treatment of quantum routing is presented in [SQ20].In this paper the authors first propose an extended Dijkstra approach, usingalso a new cost metric. They then propose two main routing algorithms. Inthe first algorithm, paths are pre-calculated for every possible pair of nodesin the network, while in the second algorithm contention is also considered,and some recovery options are also added to the selected paths.All of these mentioned approaches fit in the structure introduced in Sec-tion 1.2. In this structure, we can see that none of them actually considersthe forwarding stage as we do, and this is precisely the point from whichthis thesis starts. Our treatment of the forwarding stage, and proposing anew, opportunistic approach, opens a new direction in quantum networkingresearch.The second stream of work that is related to our analysis is on funda-mental limits of communication in quantum networks. These papers fallinto two main categories. In the first group, researchers use informationtheory to find the fundamental limits of communication in different net-working settings. Here, the communication process is not fixed like theswap-and-teleport procedure explained in Section 1.1. Instead, any possi-ble quantum or classical operation is considered, and therefore the obtainedbounds are more fundamental, encapsulating swap-and-teleport as well. Themain papers in this direction are [PLOB17, PGPBL09]. In [PGPBL09] theauthors have shown that a certain quantity is an achievable performancefor entanglement distribution over general Gaussian channels (and thereforelossy channels as well). Then, in [PLOB17] the authors have shown thatthis performance is in fact an upper bound as well. Together, they havecharacterized the quantum distribution capacity over lossy channels.In the second branch of this stream, there are the papers that followthe inherently combinatorial approach described in Section 1.1, meaningthat they treat distributing and routing entanglement as a series of steps,each of which is a protocol similar to teleportation and swapping. How-ever, they also try to specify the fundamental limitations of such an ap-proach. For instance, in [PPE+20] the authors have demonstrated thatusing a special entangled state, called as the Greenberger-Horne-Zeilinger81.5. Thesis Organization(GHZ) state [GHZ89], and a series of projective measurements4, entangle-ment can be generated between two endpoints at a rate independent of thedistance between them. Similarly, in [BA17] the authors have analyzed thefundamental limitations of quantum broadcast networks, when using mul-tipartite entanglement5 instead of bipartite entanglement. In a flavor morerelated to our mathematical analysis of opportunistic routing, provided inChapter 3, the papers [KMSD19, BPvL11] analyze the average total waitingtime for a group of links with infinite lifetimes, and Coopmans et al. [CBE21]provide analytical bounds on delivery times of long-distance entanglementin different protocols. Praxmeyer [Pra13] analyzes the average total waitingtime for a group of links with finite lifetimes.In terms of such fundamental approaches, none of the mentioned paperstake the forwarding stage into account, and there is either a theoretical or afundamental gap between the proposed results and the actual possibilities.Our analysis of opportunism decreases this gap by focusing on the forwardingstage of quantum routing.Finally, a third line of research can be indirectly related to this thesis, andthat is designing a quantum network stack. The concept of a network stackis of course a very familiar and fundamental concept for communicationin general, and researchers have tried to fit quantum networks into thistradition. In short, a quantum physical layer has to implement the physicaldevices and protocols required for a successful transmission of entangledqubits over a physical medium, a quantum link layer has to make establishingentangled pairs between adjacent nodes reliable, and a quantum networklayer is needed for routing entanglement around the network. Several suchmodels have been proposed in the literature [KDW20, PD19, VMLMN09].Regardless of the suitability of such an approach, opportunistic routing isindirectly related to this network stack. Inherently, opportunism is a designchoice, and can be applied in different layers of the stack. Therefore, it canbe thought of as a fundamental characteristic of the different algorithmsproposed for different layers of this stack, giving it a vertical nature.1.5 Thesis OrganizationThe contents of this thesis are organized as follows. In Chapter 2, weexplain opportunistic routing. Chapter 3 contains our mathematical anal-ysis of opportunism. In Chapter 4, we provide simulations demonstrating4Measurement is one of the most fundamental elements of quantum physics.5Entanglement between more than two qubits.91.5. Thesis Organizationthe superiority of opportunism. In Chapter 5, we conclude with a summary,discussions on generalizing opportunism, and future work. Finally, we pro-vide an appendix in the end, explaining the mathematical formulations ofqubits, entanglement, and the teleportation and swapping protocols. Notethat reading this appendix is not necessary to understand the contents ofthis thesis, and the appendix is included for the sake of completeness.10Chapter 2Opportunistic RoutingIn this chapter, we give a high-level overview of our opportunistic rout-ing.2.1 OverviewOur key observation is the following: most existing routing protocolsconduct the forwarding stage rather conservatively. More specifically, atypical routing algorithm (e.g., [SQ20, PKT+19, CRDW19]) often waits untilall of the links in a path are ready and then forwards the request by initiatingthe swapping process. We believe that such a conservative approach failsto exploit the highly dynamic nature of quantum networks for the followingreasons.First, since links have finite lifetimes, it is inefficient to wait for all ofthe links of a particular path to get established. For example, some alreadyestablished links may time out even before the remaining links get estab-lished, leading to a waste of resources. Second, when a request reserves thelinks of its path, these links cannot be reserved by other requests. Third,since swapping is also probabilistic and it takes time to finish, by waiting forall of the links to get generated, we unnecessarily lose the opportunity to dosome of the swappings while the generation is still not finished. Therefore,by being less conservative, we can enable two types of gain. By leveragingthe resources more efficiently, we can allow every request to reach its des-tination faster, and at the same time prevent it from being a hindrance toother requests.Based on the above explanations, we propose a modified forwarding stageas follows:4. Forwarding: The request is forwarded along the path as soon as itis possible, even if it is only a single hop.Figure 2.1 shows an example of being opportunistic in a simple scenario.The blue (pink) request is going from the leftmost (rightmost) node to therightmost (leftmost) node. At each step, a random number of links are112.1. Overviewgenerated (green links), and then the requests consume the generated links,restoring them to the non-generated (black) state. Instead of waiting forall of the links to be ready, the requests take the opportunity of movingforward when they can. For simplicity, the intermediate steps in which linksconsecutively fail to get generated are omitted.Figure 2.1: A simple opportunistic routing example. The green color ona link means that it is generated. Note that links support two-way qubittransfer.The gain caused by being opportunistic is worth more explanation. Tothis end, imagine a scenario in which N requests want to go from the samesource to the same destination. Figure 2.2 shows such a scenario. With anordinary, non-opportunistic routing algorithm, each one of these requests hasto wait for all of the links of the path to be ready, and then it gets forwarded.This means that the requests have to wait N times the time needed for asingle request, on average. However, by acting opportunistically, we canexploit the generated links as soon as it is possible for a request to moveforward, and then regenerate the consumed links for the other requests.This clearly demonstrates the two-fold gain of opportunism: 1) each requestreaches the destination sooner because a part of the waiting time for thelink generation is used to perform some of the swappings, and 2) resourcesare freed more quickly, resulting in less waiting time for requests which arewaiting for the prior requests to complete transmission. We call the firstgain as the swapping gain and the second one as the reservation gain.There is a subtle point about the forwarding stage, which is worth men-tioning. Forwarding a request can be interpreted in two ways. First, therequest may actually be forwarded along the path, as a continuation of theswapping process. That is, as soon as a swapping step is successful along the122.1. OverviewFigure 2.2: Another example for opportunistic routing. The swapping andreservation gains can be seen in this figure. The green color on a link meansthat the link is generated.path, the request can be forwarded to the corresponding intermediate nodeusing teleportation. Alternatively, the request can wait until the swappingprocess is completely finished, and then it can be sent from the source tothe destination using a single quantum teleportation step. Both of theseapproaches can be considered opportunistic in the sense explained in theprevious paragraphs, as long as the swapping process is started as soon asit is possible. Indeed, this perspective suggests that opportunism can beleveraged in two layers: first in leveraging the generation time for a part ofswapping, and then in acting opportunistically during the swapping process.Both of these “forwarding” methods have their advantages and disadvan-tages. With the former method, the request does not need to start from thebeginning if a part of the swapping process fails, while on the other hand,it will consume a part of the corresponding intermediate node’s memory,possibly harming the routing of other requests. With the latter method, noextra resources are used for serving the request, but it has to start from thebeginning every time a part of the swapping process fails. For a neat illus-tration, the figures of this thesis demonstrate the former method, so thatrequests are actually moving forward as more links are generated. How-ever, we have chosen the latter method for swapping in the simulations, andrequests have to start from the beginning if their swapping process is notsuccessful.As a final consideration, opportunism is an approach targeting the gen-eral management of quantum networks, and it can be used in any algorithmsince it does not depend on specific details. Details like how the resources132.2. k-opportunismare allocated and the paths are selected are not important at this level. Thepoint is to treat the links of a network as precious resources and use themas soon as possible. This mindset can even be extended to be an integralpart of a quantum network layer protocol (e.g., [KDW20]).2.2 k-opportunismThe opportunism discussed in this chapter is somewhat greedy and ex-treme: a request moves as soon as it can move. This may not be harmful innetworks with a low number of requests, but the more the requests get, theharder it gets for the network to manage the resources. On a large scale,forwarding a request as soon as a link is available may decrease the efficiencyof routing for some other request. Additionally, requests may have differentdegrees of priority. Therefore, the opportunistic approach needs to have adegree of flexibility to provide dynamic routing means for a highly dynamicquantum network.To this end, we introduce k-opportunism. Recall that the proposed for-warding stage required a request to move forward once it is possible, evenfor one hop. We can change this stage as follows:4. Forwarding: The request is forwarded along the path as soon as thefirst k immediate and consecutive hops are available.Figure 2.3: An example of the 2-opportunistic approach. The green coloron a link means that the link is generated.Figure 2.3 shows an example of a 2-opportunistic approach, in which arequest is going from the leftmost node to the rightmost node. Here, the re-quest does not move forward unless the two immediate and consecutive links142.2. k-opportunismare ready. Intuitively, this new opportunism provides us with a spectrumof choices, allowing us to impose a distributed control over every request’sgreediness. Indeed, the extreme opportunism introduced at the beginningof this chapter is a 1-opportunistic approach. Now, this spectrum of oppor-tunism, obtained by changing k, which we call the degree of opportunism,provides natural means for managing requests with different priorities. Thatis, we can assign lower values of k for requests with higher priorities. In thisway, high-priority requests will be able to leverage the links of the networksooner than the other requests, and the higher k gets for a request, the lowerits chances are to use a link for its transmission.15Chapter 3AnalysisIn this chapter we provide our mathematical analysis of opportunism ina line network. We demonstrate the effects of opportunism by analyzing twoof the main metrics in a network: waiting time and transmission rate.3.1 System Model3.1.1 Network, Nodes, and LinksWe model a quantum network as a graph. The nodes of the graph arequantum computers, and the edges of the graph are the links (i.e., entangledpairs). For simplicity, we assume that at most one link can exist between anytwo adjacent nodes, because such a simple setup is sufficient to demonstratethe advantage of our opportunistic routing. Unlike [SMI+16, CRDW19], wedo not use virtual links, i.e., entanglement between non-adjacent nodes, asa primary resource. The reason for this choice is also similar. We wantto demonstrate that links are precious resources and have to be consumedopportunistically, and it does not matter if they are between adjacent ornon-adjacent nodes.We use (s, d) to denote a request. Here, s is the source and d is thedestination. When it is clear from the context, we may also use r for asingle request, and {ri}ni=1 for a group of requests.We denote the lifetime of an entangled pair (i.e., a link) as L. We assumethat quantum nodes have infinite memories.3.1.2 Entanglement Generation and SwappingWe assume that every entanglement generation attempt between adja-cent nodes succeeds with probability pgen = p. Entanglement generation fora link is continuously attempted until the link is generated. Furthermore,once a link is consumed or timed out, it starts the generation process again.Finally, we assume that every swapping attempt succeeds with probabilitypswap.163.2. Results3.1.3 Waiting TimeWe divide the waiting time of a request into two parts as follows.− Swapping: It is the time required for a swapping process over a givennumber of links.− Generation: It is the amount of time it takes for all of the linksrequired for the path of the request to get generated.We consider a discrete-time model, in which every time step is equal to thetime it takes to attempt an entanglement generation between two adjacentnodes. Furthermore, we also assume that a single swapping step takes placeat the end of each time slot. That is, each request has a chance of oneswapping step at the end of each slot. The waiting times are explained inthe following sections.Swapping waiting timeDifferent algorithms have been suggested for entanglement swapping(e.g., [ZDB12]). Any algorithm can be selected for this process, and eachwould lead to a certain formula for the waiting time. We denote the totaltime it takes to swap over M links as tswap(M).Generation waiting timeWe denote the amount of time required for a path with M links tobe generated as W (M,p). We also denote the time required for link i ofthis path to get established by Ti. Note that {Ti} are i.i.d. and they fol-low a geometric distribution with parameter p. Note also that W (M,p) isa random variable, and we denote R(M,p) = E{W (M,p)}. It is shownin [KMSD19, BPvL11] that, if L =∞,R(M,p) =M∑k=1(Mk)(−1)k+11− (1− p)k . (3.1)Also, note that W (M,p) = maxi{Ti}.3.2 ResultsWe focus on the swapping and reservation gains in this section. Ourgoal is to show that the opportunistic approach improves performance by173.2. Resultsdecreasing the average total waiting time. We also show the spectrum prop-erty of opportunism by analyzing k-opportunism.To make our analysis tractable, we mainly focus on a line network here(which will be relaxed in the simulation chapter). More specifically, weassume a number of quantum nodes in a single line, in which every nodehas two neighbors (except the endpoints, which have one). We will call theendpoints of this network as A and B throughout this chapter. We assumethat this line network has M links.In addition, we introduce several simplifying assumptions for our analy-sis. First, we assume L = ∞. That is, a generated link remains intact for-ever, until a request consumes it, after which the link has to be regenerated.Second, following [CRDW19, BPvL11, ABC+21] we assume that pswap = 1.Finally, we have used a simple swapping algorithm in which the swappingoperations are carried out on a one-by-one basis, starting from the sourcetowards the destination. For this simple scheme, we have tswap(M) = M−1.3.2.1 A Single RequestWhen sending a single request, the opportunistic approach helps to re-duce the total waiting time by mixing the swapping and generation waitingtimes. In the conventional approach, the request has to wait for the gener-ation to finish, then it can begin the swapping process. The opportunisticapproach enables swapping and generation to happen simultaneously, lever-aging the time the request has to wait for link generation to do a part ofswapping. This is the swapping gain mentioned in Chapter 2. For this part,let us show the waiting time of a single request in the non-opportunistic andopportunistic settings with Q and Qopp, respectively.We consider a single request r = (A,B). With the opportunistic ap-proach, r will be somewhere in the middle of the network6 once all of thelinks have been generated (i.e, after W (M,p)). The number of links r hasbeen able to swap along the way until all of the links are generated is howopportunism shows itself, and indeed this number can be interpreted as theswapping gain caused by opportunism. Let us denote the position of r afterW (M,p) by K. We are interested in E{K}.Let us use W to show W (M,p), for brevity. Furthermore, let us defineWi = maxj≤i{Tj}. To calculate E{K}, we have E{K} =∑Mk=1 P (K ≥ k).Note that K ≥ k implies that the first k − 1 links were not the last linksto get generated, and W ≥ k since every swapping attempt takes one time6The request is actually in the source, but the swapping process has reached the middleof the network. See Chapter 2.183.2. Resultsstep. We thus have P (K ≥ k) = P (W > Wk−1,W ≥ k). Let us define W˜ =maxi>k−1{Ti}. W > Wk−1 implies W˜ > Wk−1, and vice versa. Therefore,it is easy to see that P (W > Wk−1,W ≥ k) = P (W˜ > Wk−1, W˜ ≥ k). Wecan decompose this event as follows P (W˜ > Wk−1, W˜ ≥ k) =∑∞i=k P (W˜ >Wk−1, W˜ = i), which can further be expressed as P (W˜ > Wk−1, W˜ ≥k) =∑∞i=k P (Wk−1 < i, W˜ = i). Now, since Wk−1 and W˜ are relatedto two disjoint sets of links, they are independent of each other, and wehave P (W˜ > Wk−1, W˜ ≥ k) =∑∞i=k P (Wk−1 < i)P (W˜ = i). We can nowevaluate each part separately. First, we have P (Wk−1 < i) = P (∩k−1j=1{Tj <i}) = ∏k−1j=1 P (Tj < i) = P (T1 < i)k−1. Here we have used the fact that theTj are i.i.d. It is easy to see that P (T1 < i) = 1 − (1 − p)i−1, and lettingq = 1−p, we have P (Wk−1 < i) = (1−qi−1)k−1. Now, we have P (W˜ = i) =P (W˜ ≤ i)−P (W˜ < i), which can be calculated very similar to the procedureabove, and one would have P (W˜ = i) = (1− qi)M−k+1 − (1− qi−1)M−k+1.Combining these results leads us to P (K ≥ k) = ∑∞i=k(1 − qi−1)k−1[(1 −qi)M−k+1 − (1− qi−1)M−k+1]. Therefore, we haveE{K} =M∑k=1∞∑i=k(1− qi−1)k−1[(1− qi)M−k+1 − (1− qi−1)M−k+1].(3.2)Now, we have P (K > 0) > 0. Furthermore, r has to swap along M −Klinks after W (M,p), and tswap(M − K) < tswap(M). We have Qopp =R(M,p) + E{tswap(M − K)}. Thus it is easy to see that Qopp < Q =R(M,p) + tswap(M). This proves the following theorem.Theorem 3.1. For a single request S = {(A,B)}, we have Qopp < Q.3.2.2 A Group of Requests in the Same DirectionHere, we demonstrate the reservation gain caused by opportunism. Todo this, we will assume N requests going from A to B. Note that to showopportunism decreases the total waiting time in this scenario, all one has todo is to leverage the swapping gain, as explained in Section 3.2.1, for everyrequest. However, as discussed in Chapter 2, opportunism enables anothergain, which we call the reservation gain, and this gain has a different naturethan the swapping gain.To fully demonstrate the reservation gain, we will assume that swappingtakes no time (i.e., tswap(M) = 0). This way, a request can perform asmany swapping steps as it can in a single time step. In this new setting,193.2. Resultsthe swapping gain will vanish, and in the case of a single request, oppor-tunism will not improve the performance. However, when having multiplerequests, we can show that opportunism decreases the total waiting time,thus demonstrating the existence of what we call the reservation gain.Let us use Tij (where i ≤ M and j ≤ N) to show the time it takes togenerate the i-th link for the j-th time (i.e., for the j-th request), once ithas been consumed for the (j − 1)-th request. Each Tij follows a geomet-ric distribution with parameter p, and Tij are independent. Furthermore,changing the notation for a bit, let us show the amount of time required forN requests to reach their destinations using opportunism with WN .Let us express {Tij} in a more compact matrix form:D =T11 T21 . . . TM1T12 T22 . . . TM2....... . ....T1N T2N . . . TMN . (3.3)Note that Dij = Tji. This allows us to have the links on the rows of thematrix, making it look similar to a line network. In particular, each row jof D shows the j-th generation times for the links of the network.In order to analyze WN , we need to introduce a few intermediate vari-ables. Let us define:Wij ={maxk≤i Tkj j = 1maxk≤i{Wk,j−1 + Tkj} j > 1. (3.4)This recursive structure allows us to have the following proposition.Proposition 3.2. The total waiting time in the opportunistic setting isWN = WMN .Proof. Let us show the N requests with {ri}Ni=1. First, we show that theproposition holds for N = 2. Link i will start generation for r2 once it hasbeen generated and consumed by r1. It will be consumed once all of the firsti links are generated for r1, so that r1 can take the opportunity (rememberthat swapping takes no time). Hence, link i can start its generation for r2at time Wi1 = maxk≤i Tk1. Once this generation has taken place, now linki takes Ti2 time steps to get generated for r2, which means r2 should wait atotal amount of Wi1 +Ti2 time slots for the i-th link to get generated. Sincethere is no swapping gain, we thus conclude that the total waiting time isequal to maxi≤M{Wi1 + Ti2}, which is the formula for WM2. This meansthat W2 = WM2.203.2. ResultsWe now assume that the lemma is true for i ≤ N − 1, and prove it isalso true for N . The proof is similar. Request rN has to wait for rN−1 toconsume link i, and then link i can start the generation process for the N -thtime. Request rN−1 can consume link i once it can consume all of the first ilinks, and this takes Wi,N−1 by the induction hypothesis. It takes TiN timeslots for the N -th generation of link i to succeed. Thus, link i is ready forrN at time Wi,N−1 + TiN , which means rN will have all of the links readyand reach the destination at time maxi≤M{Wi,N−1 + TiN}. This is exactlythe definition of WMN , and leads us to WN = WMN .We also have the following lemma, which proves to be useful in theproofs.Lemma 3.3. Wij are ascending for every fixed j. That is, if k < i, thenWkj ≤Wij.Proof. This lemma is an immediate result of the fact that for two finite setsU ⊂ V and a function f on these sets, we have maxu∈U f(u) ≤ maxv∈V f(v).We now proceed and prove that opportunism indeed decreases the totalwaiting time. In the following, W upN is the total waiting time in the non-opportunistic approach.Proposition 3.4. Opportunism decreases the total waiting time. That is,we have WN ≤W upN .Proof. In the non-opportunistic approach, each request has to wait for allof the links to get established. Therefore, the j-th request has to wait formaxi Tij steps. After each such step, all of the links are consumed, and thenext request starts from scratch. We thus conclude that:W upN =∑j≤Nmaxi≤MTij . (3.5)We now use induction on the number of requests to prove the theorem. IfN = 1, then the two waiting times coincide, since a single request has towait for all of the links, no matter what. Now, assume that the claim holdsfor N − 1. The induction hypothesis then tells us that WN−1 ≤W upN−1. Wehave:WN = maxi≤N{Wi,N−1 + TiN} ≤ maxi≤NWi,N−1 + maxi≤NTiN(i)= WM,N−1 + maxi≤NTiN(ii)≤ W upN−1 + maxi≤NTiN(iii)= W upN ,213.2. Resultsin which equality (i) comes from Lemma 3.3, inequality (ii) is based on theinduction hypothesis and Proposition 3.2, and equality (iii) is just Equa-tion (3.5).As explained in Chapter 2, it turns out that opportunism has a spectrumof degrees, leading all the way to non-opportunism. Put simply, instead offorwarding a request as soon as an immediate link is available, we can for-ward the request once there are k immediate and consecutive links available.In order to analyze the k-opportunistic setting in a coherent way, we definethe following variables:W kij ={maxm≤min{i+k−1,M} Tmj j = 1maxm≤min{i+k−1,M}{W km,j−1 + Tmj} j > 1. (3.6)Note that Equation (3.4) is a special case of Equation (3.6) for k = 1.Based on this definition, we also denote the total waiting time in the k-opportunistic setting by W kN . The following proposition is a straightforwardgeneralization of Proposition 3.2.Proposition 3.5. The total waiting time in the k-opportunistic setting isW kN = WkMN .Proof. Let us show the N requests with {ri}Ni=1. First, we show that theproposition holds for N = 2. Link i will start generation for r2 once it hasbeen generated and consumed by r1. It will be consumed once all of the firsti links, and the next k − 1 links, are generated for r1, so that r1 can takethe opportunity (remember that swapping takes no time). To see this, notethat there are two possibilities. Either the next k − 1 links will take lesstime than the i-th link, or they will take more. In the former case the claimis trivially correct. In the latter case, since r1 will get stuck right behindlink i and will not consume it unless the next k − 1 links are available, r1has to wait for all of those links. Hence, link i can start its generation forr2 at time Wki1 = maxs≤min{i+k−1,M} Ts1. Note that we take a minimumin the index since we have M total links. Once this generation has takenplace, now link i takes Ti2 time steps to get generated for r2, which meansr2 should wait a total amount of Wki1 +Ti2 time slots for the i-th link to getgenerated. Quite similar to the first time, now r2 should also wait for all ofthe next k − 1 links to get generated again for it to move. Therefore, link ican be consumed for this request after maxs≤min{i+k−1,M}{W ks1 + Ts2}. Wethus conclude that the total waiting time is equal to maxi≤M{W ki1 + Ti2},which is the formula for W kM2. This means that Wk2 = WkM2.223.2. ResultsWe now assume that the lemma is true for i ≤ N − 1, and prove it isalso true for N . The proof is very similar. Request rN has to wait for rN−1to consume link i, and then link i can start the generation process for theN -th time. Request rN−1 can consume link i once it can consume all of thefirst i + k − 1 links, and this takes W ki,N−1 by the induction hypothesis. Ittakes TiN time slots for the N -th generation of link i to succeed. Thus, linki is ready for rN at time Wki,N−1 + TiN , which means rN will have all of thelinks ready and reach the destination at time maxi≤M{W ki,N−1 +TiN}. Thisis exactly the definition of W kMN , and leads us to WkN = WkMN .Similarly, Lemma 3.3 can also be extended. The proof is exactly thesame, and is omitted for brevity.Lemma 3.6. W kij are ascending for fixed j and k. That is, if m < i, thenW kmj ≤W kij.The important point about opportunism is the fact that the waitingtimes form an ascending order based on the opportunism degree. This iscaptured by the next proposition.Proposition 3.7. We have W kN ≤W k+1N .Proof. To prove this proposition, we prove a stronger claim. We prove thatfor every m ≤M we have W kmN ≤W k+1mN . Using Proposition 3.5, this provesthe current proposition. We use induction on the number of requests. ForN = 1, the claim follows immediately from the fact that for W k+1m1 , we takethe maximum over a set larger than that of W km1. We now assume that theclaim is true for N − 1, which means W km,N−1 ≤W k+1m,N−1 for every m ≤M .The proof proceeds as follows:W kN = maxm≤min{M,i+k−1}{W km,N−1 + TmN}(i)≤ maxm≤min{M,i+k}{W km,N−1 + TmN}(ii)≤ maxm≤min{M,i+k}{W k+1m,N−1 + TmN} = W k+1N ,in which (i) holds since the set over which we take the maximum is enlarged,and (ii) is based on the induction hypothesis.Although WN is itself lower than WupN , opportunism has a lower boundand cannot arbitrarily decrease the total waiting time. Indeed, a simplelower bound W lowN for WN can be achieved as follows.233.2. ResultsProposition 3.8. The opportunistic waiting time is bounded from below,and we have W lowN = maxi≤M∑j≤N Tij ≤WN .Proof. If we replace maxm≤i{Wm,j−1 + Tmj} with Wi,j−1 + Tij in the def-inition of Wij in Equation (3.4), this will not increase the value of WMN ,since we shrink the set we take the maximum on. We therefore define W˜ijas follows:W˜ij ={Tij j = 1W˜i,j−1 + Tij j > 1. (3.7)We define W lowN = maxm≤M W˜mN . Based on the definition above, we haveW lowN = maxi≤M∑j≤N Tij . Since this procedure cannot increase the wait-ing time, we conclude W lowN ≤WN .Just as the k-opportunistic settings form a spectrum between 1-opportunismand non-opportunism, i.e., WN and WupN , one can wonder if there is such aspectrum between W lowN and WN . It turns out that such a spectrum exists,and W lowN and WN are the two extremes of it. We can demonstrate thisspectrum with the following new definition:Wˆ rij ={maxmax{0,i−r}≤k≤i Tkj j = 1maxmax{0,i−r}≤k≤i{Wˆ rk,j−1 + Tkj} j > 1. (3.8)We now define Wˆ rN = maxi≤M WˆriN . Note that for r = 0 we have Wˆ0N =Wlow, and for r = M we have WˆMN = WN , which shows that Wlow and WNare members of the same family, with parameter r. Since this parameterspecifies how many links we go back when searching for the maximum value,we call it the search depth.We now show that, similar to k-opportunism, the new family of Wˆ rNform an ascending order based on r.Proposition 3.9. We have Wˆ rN ≤ Wˆ r+1N .Proof. We use induction on the number of requests, N , to show that forevery i we have Wˆ riN ≤ Wˆ r+1iN . This way, since Wˆ rN = maxi≤M Wˆ riN andWˆ r+1N = maxi≤M Wˆr+1iN , the claim is proved. First assume that N = 1. Inthis case, the induction claim follows from the fact that taking maximumover a larger group does not decrease the maximum value. Therefore, sincewhen we go back r + 1 links to search for maximum in calculating Wˆ r+1i1 ,while we go back only r links when calculating Wˆ ri1, the claim is proved.243.2. ResultsLet us now assume that the induction claim is true for N − 1. We have:Wˆ riN = maxmax{0,i−r}≤k≤i{Wˆ rk,N−1 + TkN}≤ maxmax{0,i−(r+1)}≤k≤i{Wˆ rk,N−1 + TkN}(i)≤ maxmax{0,i−(r+1)}≤k≤i{Wˆ r+1k,N−1 + TkN} = Wˆ r+1iN .Inequality (i) follows from the induction hypothesis.We have now established two families of “waiting times”, and have shownthat WN is in fact sandwiched between these two families. From below, itis bounded by the different search depths, and from above it is bounded bydegrees of opportunism. Note that, in contrast to degrees of opportunism,different search depths do not have a real counterpart in the algorithm,and are mere mathematical tools to have a better understanding of themathematical structure of the problem. We can gather the results of thissection in the following theorem.Theorem 3.10. In a line network, depths of search and degrees of oppor-tunism sandwich the total waiting time in the opportunistic setting frombelow and above, respectively:maxj≤N∑i≤MTij =Wˆ0N ≤ Wˆ 1N · · · ≤ WˆMN= WN= W 1N ≤W 2N · · · ≤WMN =∑j≤Nmaxi≤MTij .3.2.3 Transmission RateA natural question to ask is the effect of opportunism on the transmissionrate between A and B. The rate of interest is the number of requests sentfrom A to B per step. Similar to our analysis of the reservation gain, we onceagain assume that swapping takes no time, in order to capture the generationand reservation dynamics of the transmission rate. To characterize this rate,we define the random variable NT to be the number of requests deliveredfrom A to B up to time T ∈ N. Based on this definition, we define thetransmission rate between A and B to be:R = limt→∞E{Nt}t. (3.9)253.2. ResultsThe first thing we have to do is to prove such a limit exists. In order to doso, we will use the following lemma [Fek23].Lemma 3.11. (Fekete’s Lemma) For every superadditive (subadditive) se-quence {an}, the limit limn→∞ a{n}n is equal to sup ann (inf ann ).To use this lemma, we need to prove the following proposition.Proposition 3.12. The sequence E{Nt} is superadditive. That is, for twointegers t1 and t2 we have E{Nt1+t2} ≥ E{Nt1}+ E{Nt2}.Proof. Without loss of generality, let us assume t1 ≤ t2. After t1 time stepshave passed, a total of Nt1 requests have been sent to B. Let us show thenumber of requests sent in the remaining t2 time steps with X. Then wehave Nt1+t2 = Nt1 +X, which means E{Nt1+t2} = E{Nt1}+ E{X}. Now,note that after t1 time steps, some of the links of the network are alreadyestablished, and some of the pending requests are somewhere between Aand B. Therefore, if we compare X to a situation in which the networkstarts from scratch and runs for t2 seconds, we can see that in expectation,E{X} ≥ E{Nt2}. This leads us to E{Nt1+t2} ≥ E{Nt1} + E{Nt2}, andfinishes the proof.We can now prove the existence of R as defined in Equation (3.9).Proposition 3.13. The limit R = limt→∞E{Nt}t exists and is finite.Proof. The existence follows immediately from Lemma 3.11 and Proposi-tion 3.12. To show that R is finite, note that for every t ∈ N we haveNt ≤ t. This is true because the only case in which we can have Nt = t iswhen all of the links succeed consecutively in generation, up until time t,so that in each step a single request is able to use all of the links to reachB. Therefore, no more than t requests can be sent, since this is the bestcase. We can thus see that for every t ∈ N we have E{Nt}t ≤ 1, which meansR ≤ 1.Although the convergence of E{Nt}t to a constant is desirable enough, itwould be better if we could say more, specially about the dynamics of Ntt .In fact, using the standard bounded difference method [Ste97], we show thatNtt converges almost surely to R. We need to introduce some more structurebefore proving this claim. The following construction is a straightforwardapplication of the procedure described in [Ste97].We start by introducing a new group of random variables, inspired by anidea from [DDHE09]. Let us show the state of link j ∈ {1, . . . ,M} at time263.2. Resultsi ∈ {1, . . . , t} by Xji ∈ {0, 1}, where Xji = 1 (Xji = 0) means that link j isgenerated (not generated) at time i. Notice that {Xji} are not independent.Based on these variables, let Fji be the sigma-field generated by the Xabvariables up to a = j and b = i, i.e., Fji = σ(X11, X21, . . . , Xji). Note thatthese sigma-fields “grow” based on a lexicographic order.We define dji = E{Nt|Fji} − E{Nt|Fα(j,i)}, in which α(j, i) gives theprevious (j′, i′) in the lexicographic order, i.e., α(j, i) = (j − 1, i) if j >1 and α(1, i) = (M, i − 1). The purpose of this formality is to ensurethe dji grow based on the order of the Fji. Note that we have Nt =Nt(X11, X21, . . . , XMt), which means E{Nt|FMt} = Nt. This leads us to∑i,j dji = Nt − E{Nt}.We now proceed to prove that the {dji} are bounded. Let us introducea new set of variables {N (ji)t }. For every j and i, N (ji)t is the same as Nt,except that it forgets the actual value of Xji, and assumes Xji = 1. Thatis, we have:N(ji)t (X11, X21, . . . , Xji, . . . XMt)= Nt(X11, X21, . . . , 1, . . . XMt). (3.10)The following lemma is essential to our path towards the convergence of Ntt .Lemma 3.14. For every i and j we have:|Nt(X11, X21, . . . , Xji, . . . XMt)−N (ji)t (X11, X21, . . . , Xji, . . . XMt)| ≤ 1.Proof. If Xji = 1, then based on Equation (3.10) we have Nt−N (ji)t = 0. IfXji = 0, then the best case scenario is when all of the links are consecutivelygenerated, except for link j at time i. In this case, flipping Xji to one allowsone more request to pass, and increases Nt by one. Therefore, having alink active at a certain time can increase Nt by at most one amount, whichmeans |Nt −N (ji)t | ≤ 1.We now use Lemma 3.14 to bound ||dji||∞. This will allow us to lever-age a version of Azuma’s inequality [Ste97]. We start with showing thatE{Nt|Fji} ≤ E{N (ji)t |Fα(j,i)}. Because of the discrete nature of the prob-lem, we can think of E{Nt|Fji} as a function of a tuple (x11, . . . , xα(j,i), xji),in which xab is a realization of Xab [JP12]. We can take each one of suchtuples and change it to (x11, . . . , xα(j,i), 1), which is in a bijective corre-spondence with the tuple (x11, . . . , xα(j,i)). In order to use this, we name273.2. ResultsG = E{Nt|Fji}, H = E{N (ji)t |Fα(j,i)}, and H ′ = E{N (ji)t |Fji}. This allowsus to form a bridge between G and H, as follows. First, note that giventhe knowledge of Fα(j,i), N (ji)t is totally decoupled from Xji, and the futurestate of the links is independent from this variable. Therefore, we have:H(x11, . . . , xα(j,i)) = H′(x11, . . . , xα(j,i), xji). (3.11)Second, based on the reasoning in the proof of Lemma 3.14, we see that:G(x11, . . . , xα(j,i), xji) ≤ H ′(x11, . . . , xα(j,i), xji). (3.12)Since Equation (3.12) holds for every tuple (x11, . . . , xα(j,i), xji), we concludethat G ≤ H, which means:E{Nt|Fji} ≤ E{N (ji)t |Fα(j,i)}. (3.13)Quite similarly, if we define G′ = E{Nt|Fα(j,i)}, we have:G′(x11, . . . , xα(j,i)) ≤ H(x11, . . . , xα(j,i))= H ′(x11, . . . , xα(j,i), xji), (3.14)which means:E{Nt|Fα(j,i)} ≤ E{N (ji)t |Fji}. (3.15)Combining Inequalities (3.13) and (3.15) we achieve:E{Nt −N (ji)t |Fji} ≤ dji ≤ E{N (ji)t −Nt|Fα(j,i)}. (3.16)Now, we know from Lemma 3.14 that |Nt −N (ji)t | ≤ 1. We also know thatconditional expectation cannot increase the ||.||∞ norm. Therefore, fromInequality (3.16) we conclude that for every i and j we have ||dji||∞ ≤ 1.We are now ready to prove our claim.Proposition 3.15. With probability one, Ntt converges to R.Proof. Using a version of Azuma’s inequality [Ste97], we can establish thefollowing tail bound. Note that we have replaced∑i,j dji with Nt−E{Nt}:P (|Nt − E{Nt}| ≥ λ) ≤ 2 exp(−λ22∑i,j ||dji||2∞). (3.17)283.2. ResultsUsing the fact that for every i and j we have ||dji||∞ ≤ 1, we can changethis inequality to:P (|Nt − E{Nt}| ≥ λ) ≤ 2 exp(−λ22Mt). (3.18)For every t ∈ N, and a fixed 0 <  ∈ R let us define λt =√2Mt(log t)(1 + ),and the corresponding event At = {|Nt − E{Nt}| ≥ λt}. Using Inequal-ity (3.18) we have: ∑tP (At) ≤∑t1t1+<∞. (3.19)Therefore, based on the Borel-Cantelli lemma we have P (At, i.o.) = 0. Thismeans that with probability one we have Nt − E{Nt} = O(√t log t), orNtt − E{Nt}t = O(√log tt ). Therefore, sinceE{Nt}t tends to R as t → ∞, weconclude that Ntt should also tend to R.Based on the analysis of the waiting time in Section 3.2.2, we can readilyobtain a lower and an upper bound for R. To see this, first notice that basedon the definition of Nt, we have the following equality:Nt = max{n ∈ N |Wn ≤ t}. (3.20)Let us define Nlowt and Nupt in a similar fashion:Nupt = max{n ∈ N |W upn ≤ t} (3.21)Nlowt = max{n ∈ N |W lown ≤ t}. (3.22)Now, since we knowW lown ≤Wn ≤W upn , we can see that Nlowt ≥ Nt ≥ Nupt .This allows us to have the following proposition, which we just proved.Proposition 3.16. Let us define (notice the reversal of the low and upsubscripts):Rlow = limt→∞E{Nupt }t(3.23)Rup = limt→∞E{Nlowt }t. (3.24)We then have Rlow ≤ R ≤ Rup.293.2. ResultsThe same reasoning can be used to define the corresponding rates for thek-opportunistic waiting times, as well as the different search depths. Thus,the spectrum shown in Theorem 3.10 can be directly turned into a spectrumof rates. We do not repeat the process for brevity.It turns out that there exists another interesting upper bound for R. Thisupper bound stems from a slightly different definition for the transmissionrate in the opportunistic setting. Let us define:R˜ = limn→∞nE{Wn} . (3.25)Similar to Proposition 3.13, one first has to show R˜ exists and is finite. Thiscan be done in the same manner, as can be seen from the next proposition.Proposition 3.17. The limit R˜ = limt→∞ nE{Wn} exists and is finite.Proof. The procedure is very similar to that of Proposition 3.13. We firstshow that the sequence E{Wn} is subadditive. Assume two integers n1 ≤ n2,and let us start with Wn1+n2 . After the first n1 requests have been sent, Wn1time steps have passed. Let us show the remaining time steps until all n1+n2requests have been sent with Y . We thus haveWn1+n2 = Wn1+Y . AfterWn1time steps, some of the links are established and some requests are alreadytravelling through the network. Therefore, E{Y } cannot be more than thecase in which the network starts from scratch, leading to E{Y } ≤ E{Wn2}.We thus conclude that E{Wn1+n2} ≤ E{Wn1}+ E{Wn2}.The existence of R˜ follows immediately from Lemma 3.11. To see thatR˜ is also finite, it is sufficient to note that for every n ∈ N we always haven ≤ Wn. This happens because the lowest Wn can get is when all of thelinks succeed consecutively in generation, up until request n, so that in eachstep a single request is able to use all of the links to reach B. Therefore, wealways have nE{Wn} ≤ 1, which means R˜ is finite.Although quite similar in nature, simulations indicate that R and R˜are different, and we have R ≤ R˜. We do not have a proof for this yet,and postpone a demonstration of this curious point to the simulations inChapter 4.3.2.4 Further InvestigationLet us get back to the matrix D, defined in Equation (3.3). As ex-plained in Section 3.2.2, we can introduce different degrees of opportunism303.2. Resultsand searching depths when analyzing the waiting times. There is a mathe-matical waiting time associated with every one of these cases. Thinking ofthese waiting times as mere functions of matrices, it turns out that they havean interesting property. Put simply, these waiting times act as norms forgeneral matrices. Furthermore, the ||.||∞ matrix norm is a natural memberof this family of norms, as we will show here.To analyze the waiting time functions as norms, we need to define themin a different, more systematic manner. The following definition introducesthe building blocks of such a systematic approach.Definition 3.18. For every 0 ≤ r ≤ M and 1 ≤ k ≤ M , and for vectorsa, b ∈ RM , we define the function Θkr : RM × RM → RM as follows:Θkr (a, b) = (v1, . . . , vM )vi = maxmax{0,i−r}≤j≤min{i+k−1,M}{|aj |+ |bj |}.Based on this definition, we have the following lemma.Lemma 3.19. For every 0 ≤ r ≤ M and 1 ≤ k ≤ M , every α ∈ R,and for vectors a, b ∈ RM , the function Θkr (a, b) satisfies the following twoproperties:1. If Θkr (a, b) = 0, then a = 0 and b = 0.2. Θkr (αa, αb) = Θkr (−αa, αb) = Θkr (αa,−αb) = |α|Θkr (a, b).Proof. We first prove the first property. Based on Definition 3.18, Θkr (a, b) =0 means that for every i and every j between max{0, i− r} and min{i+ k−1,M}, we have |aj |+ |bj | ≤ 0, which means aj = bj = 0. Since we can coverall 1 ≤ j ≤M by sliding i, we conclude that a = b = 0.We now prove the second property. Assuming Θkr (a, b) = (v1, . . . , vM )and Θkr (αa, αb) = (u1, . . . , uM ), for every i we have:ui = maxmax{0,i−r}≤j≤min{i+k−1,M}{|αaj |+ |αbj |}= maxmax{0,i−r}≤j≤min{i+k−1,M}{|α|(|aj |+ |bj |)}= |α| maxmax{0,i−r}≤j≤min{i+k−1,M}{|aj |+ |bj |}= |α|vi.We thus conclude that Θkr (αa, αb) = |α|Θkr (a, b). The other equalities areproved in the exact same way.313.2. ResultsLet us show the standard basis vectors for RM with {ei}1≤i≤M . That is,ei is the vector with a one in its i-th coordinate, and a zero in the rest. Fora given matrix D, we define the vectors Di as follows:Di = Θkr (Di−1, eTi D). (3.26)With the initial vector D0 = (0, . . . , 0). We are now ready for the followingtheorem.Theorem 3.20. For any matrix D ∈ RN×M , and every 0 ≤ r ≤ M and1 ≤ k ≤M , the following function is a norm:Λkr (D) = ||DN ||∞, (3.27)in which DN is based on Equation (3.26).Proof. We prove this theorem by checking the three conditions a real func-tion on matrices should satisfy in order to be a matrix norm. First, weshow that if Λkr (D) = 0, then D is the zero matrix. Since Λkr (D) = 0, then||DN ||∞ = 0. This means that DN = 0. Now, based on Lemma 3.19, wehave eTND = 0 and DN−1 = 0. The first equality means that the last rowof D is equal to the zero vector, and the second equality can be used in arecursive manner (based on Definition 3.18). Each step i reveals that thei-th row of D is the zero vector. Therefore, we have D = 0.We now show that, for any α ∈ R, we have Λkr (αD) = |α|Λkr (D). Letus denote Dˆ = αD. By using induction, we show that for every i we haveDˆi = |α|Di. This way, we have DˆN = |α|DN , which directly leads toΛkr (αD) = |α|Λkr (D). For i = 1, based on Lemma 3.19 we have Dˆ1 =Θkr (0, αeT1D) = |α|Θkr (0, eT1D) = |α|D1. Now, assuming the claim is true fori, we have:Dˆi+1 = Θkr (Dˆi, αeTi+1D) = Θkr (|α|Di, αeTi+1D)= |α|Θkr (Di, eTi+1D) = |α|Di+1,in which we have used the induction hypothesis and Lemma 3.19.Finally, we have to prove that Λkr satisfies the triangle inequality. We willdo so by showing that for the two matrices C and D we have Λkr (C +D) ≤Λkr (C)+Λkr (D). Let us name G = C+D. Also, let us show the j-th elementof a vector Ci with (Ci)j . In order to do prove the triangle inequality, we firstuse induction to prove that for every i and j we have (Gi)j ≤ (Ci)j + (Di)j .323.2. ResultsOnce we have proved this, we have:Λkr (G) = ||GN ||∞ = maxj{(GN )j} ≤ maxj{(CN )j + (DN )j}≤ maxj{(CN )j)}+ maxj{(DN )j}= Λkr (C) + Λkr (D),which is the triangle inequality. Now, in order to prove our claim based oninduction, we first start with the base case of i = 1. Let us show the elementin the i-th row and the j-th column of a matrix C with Cij . We have:(G1)j = maxmax{0,j−r}≤s≤min{j+k−1,M}{|G1s|}= maxmax{0,j−r}≤s≤min{j+k−1,M}{|C1s +D1s|}≤ maxmax{0,j−r}≤s≤min{j+k−1,M}{|C1s|+ |D1s|}≤ maxmax{0,j−r}≤s≤min{j+k−1,M}{|C1s|}+ maxmax{0,j−r}≤s≤min{j+k−1,M}{|D1s|}= (C1)j + (D1)j .Now we assume that our claim is true for i− 1. We have:(Gi)j = maxmax{0,j−r}≤s≤min{j+k−1,M}{|(Gi−1)s|+ |Gis|}= maxmax{0,j−r}≤s≤min{j+k−1,M}{|(Gi−1)s|+ |Cis +Dis|}≤ maxmax{0,j−r}≤s≤min{j+k−1,M}{(|Gi−1)s|+ |Cis|+ |Dis|}(i)≤ maxmax{0,j−r}≤s≤min{j+k−1,M}{|(Ci−1)s|+ |(Di−1)s|+ |Cis|+ |Dis|}≤ maxmax{0,j−r}≤s≤min{j+k−1,M}{|(Ci−1)s|+ |Cis|}+ maxmax{0,j−r}≤s≤min{j+k−1,M}{|(Di−1)s|+ |Dis|}= (Ci)j + (Di)j .Inequality (i) is based on the induction hypothesis. This finishes our proof.We have thus proved that the function Λkr is indeed a matrix norm.333.2. ResultsIt is straightforward to see that for specific combinations of the valuesof r and k, the function Λkr can be equal to any of the waiting times inthe spectrum analyzed in Section 3.2.2. Specifically, the function Λ1M isthe waiting time in the opportunistic routing setting. This establishes thelink between the waiting times and a family of matrix norms. Finally, it iseasy to see that the function Λ10 is equal to the ||.||∞ norm. This serves asevidence in favor of these norms, justifying further research to reveal theirproperties.34Chapter 4SimulationsWe demonstrate our experimental results in this chapter. These resultscan be divided to two main categories, each serving its own purpose. Wefirst present simulation results for the line network analyzed in Chapter 3,in which we demonstrate the proved claims numerically. Second, using thesimulator we have built, we present the effect of opportunism on a morecomplex network, under different design choices. Our simulation setup in thesecond part is much more general than our analysis setup in Chapter 3. Forinstance, we use the grid topology for simulation, which automatically coversmany complex routing scenarios. We have also relaxed the assumptions ofthe analysis section in the second part of the simulations.4.1 Numerical Simulations for Line NetworksWe start with verifying our analytical results. The analysis in Chap-ter 3 has three main themes. The first is the fact that opportunism inducesa spectrum of choices and corresponding waiting times. The main pointhere is that opportunism decreases the total waiting time. We postponedemonstrating these to Section 4.3, in which we use a much more complexnetwork. The second theme is about the asymptotic behavior of the trans-mission rate, whether in expectation or as a random variable. Finally, thelast theme is about bounding the transmission rate from above and below.In the numerical simulations of this section, we focus on the transmissionrate, and demonstrate the second and third themes of our analysis.Figure 4.1 shows the transmission rate when we have M = 20, for twovalues of pgen. Here, the rate variables correspond exactly to the rates in-troduced in Section 3.2.3, except for Rlowt , which is a constant equal tothe average rate in the non-opportunistic setting (there is a slight abuse ofnotation here). This approximation is not in conflict with our analyticalresults, and we have chosen this demonstration to emphasize the improve-ment caused by opportunism in terms of asymptotic rate. We can see thatfor every t, Rt is more than Rlowt . Now, we know from Equations (3.21)and (3.23) that Rlowt corresponds to non-opportunism, which means that in354.1. Numerical Simulations for Line Networks0 200 400 600Time (steps)0.00.10.2Transmissionrate(reqssteps)RtR˜tRuptRlowt0 200 400 600Time (steps)0.00.20.40.6Transmissionrate(reqssteps)RtR˜tRuptRlowtFigure 4.1: Transmission rate and its different bounds. In the figures on theleft and the right we have pgen = 0.3 and pgen = 0.7, respectively.a line network, opportunism increases the transmission rate when comparedto non-opportunism. As we mentioned in Chapter 3, R˜t seems to act as anupper bound to Rt, and we can see this as well in Figure 4.1.We now demonstrate the behavior of Rt based on the two main variablesof the setting in our analysis, which are pgen and M . We first fix the sizeof the network at M = 20, and plot the transmission rate Rt for differentvalues of pgen. The result is shown in Figure 4.2, in which the value ofpgen ranges from 0.1 to 1. Similarly, we can fix pgen = 0.8, and plot thetransmission rate for different network sizes. The results are demonstratedin Figure 4.3, in which M ranges from 11 to 20.These figures suggest that M has a linear effect on the transmissionrate, while pgen has a nonlinear one. We can verify these observations byplotting the rate based on these variables, and not based on the time. Todo this, we select a time in which the rate has safely converged, and plotthe rate in that time based on varying M and pgen values. The resultingplots are shown in Figure 4.4. This figure also shows that the rate is notvery sensitive to the length of the line. This is intuitively correct, becauseonce enough requests have entered the network, the rate with which theyreach the destination is not much related to the length of the network, andthe generation probability is the main factor.We finally demonstrate the stochastic behavior of the transmission rate.As we proved in Chapter 3, the transmission rate almost surely converges tothe limit of its expectation. Figure 4.5 shows this convergence for a numberof simulated runs.364.2. QNS-Lite0 50 100 150 200 250 300Time (steps)0.00.20.40.60.81.0Transmissionrate(reqssteps)0.10.20.30.40.50.60.70.80.91.0Figure 4.2: Transmission rate for different values of pgen. These values arespecified in the legend. We have M = 20.4.2 QNS-LiteBefore presenting the evaluation results, we first provide a brief expla-nation of the simulator we developed during our research on opportunism,QNS-Lite [QNS]. We do so by explaining the logical, modular structure ofthe simulator, shown in Figure 4.6. We go through the modules one by one:− Graph: This module provides the necessary abstractions (e.g., nodesand links) for the topology of the network.− Quantum: The Quantum module captures the quantum behaviourof the system. This is done through a number of mathematical ab-stractions that represent the physical behaviour of the system. Forinstance, every generation attempt is modeled by a biased coin toss.− Request: The necessary components of a simulated request are packedin the Request module.− Config: This module contains the generic parameters of the system(e.g., pgen), and allows the designer to specify these parameters in oneplace.374.2. QNS-Lite0 50 100 150 200 250 300Time (steps)0.00.10.20.30.40.50.60.7Transmissionrate(reqssteps)11121314151617181920Figure 4.3: Transmission rate for different values of M . These values arespecified in the legend. We have pgen = 0.8.− PathFinder: The functionality of the PathFinder module is to find anumber of (recovery) paths for the requests, based on different designchoices. Different routing algorithms can have different PathFindermodules.− Profile: This is the main module of the system. Here, a networktopology and a specific routing algorithm are determined, and thesimulation starts to run. Each combination of different networks androuting algorithms gives a different profile, and this module enables thecommon functionalities (e.g., forwarding) required for such algorithmsto run.− Benchmarker: The Benchmarker module handles the creation of therequests, and then runs the profile module. Furthermore, the metricsof the simulation are gathered by this module.Following the existing literature on quantum routing (e.g., [CRDW19,SQ20]), we have adopted the practice of dividing time into time slots, andfurthermore, based on the structure explained in Section 1.2, each timeslot is divided to several stages. Because of our focus on demonstrating384.2. QNS-Lite12 14 16 18 20Network size0.650.660.670.680.69Transmissionrate(reqssteps)0.2 0.4 0.6 0.8 1.0Generation probability0.00.20.40.60.81.0Transmissionrate(reqssteps)Figure 4.4: Transmission rate based on M and pgen. The value of pgen inthe figure on the left is 0.8, and the value of M in the figure on the right is20.the essential superiority of opportunism, we have kept some aspects of thedesign simple, and improving these aspects is a part of our future work.This being said, most of the design choices required for creating and fine-tuning a quantum routing algorithm are crafted into the simulator, hencemaking it a suitable tool for research and development. Finally, to havea more realistic evaluation, we have relaxed the assumption that swappingtakes no time. At the end of each time slot, we allow every request asingle swapping opportunity. We use an ordinary chain swapping from thesource to the destination. Note that, although there are better swappingmethods, this choice does not harm our goal of demonstrating the superiorityof opportunism.In order to verify the results of our simulator, we have compared theresults for a simple line network with those of a numerical simulation. Inother words, we have used the validation of the results for a line network asa basis for the correctness of the simulator in the more general grid topology.We have also studied its behaviour in several representative scenarios fromthe grid topology, and compared the results with the expected behavior.This latter group of comparisons are qualitative and not quantitative. Amore complete verification would involve numerical simulations for the gridtopology as well.394.3. Evaluation0 50 100 150 200 250 300Time (steps)0.00.10.20.30.40.5Transmissionrate(reqssteps)RtFigure 4.5: The stochastic convergence of the transmission rate. The valuesof M and pgen are 20 and 0.7, respectively.4.3 EvaluationIn order to provide and explain our experimental results, we first explainour setup, metrics, and methodology, as follows.4.3.1 SetupIn our setup, the source and the destination of each request are randomlyselected, based on a uniform distribution on the nodes. Once the requestsare generated, the runtime of the simulator starts, and it finishes when allof the requests have reached their destinations. This can be thought ofas giving an impulse as the input to a system and measuring its impulseresponse. All of the metrics are measured during the runtime.Each configuration of interest for this thesis can be shown as the tuple(pgen, pswap, L,N,M, k), in which pgen is the generation success probability,pswap is the swapping success probability, L is the lifetime of a link, N is thenumber of requests, M is a parameter determining the size of the network,and k is the opportunism degree. In a grid network, the nodes are arrangedin an M ×M mesh.404.3. EvaluationConfigBenchmarkerGraph PathFinderProfile QuantumRequestFigure 4.6: The modular structure of our simulator.4.3.2 MetricsThe main metric for our evaluations is the average total waiting timefor requests, as explained in Chapter 3. The lower this metric becomes, thesooner (on average) the requests reach their destinations, and the higher theaverage throughput of the network. In addition to this metric, we brieflyevaluate the average link waiting time. The lower this metric gets, the moreefficient resource consumption becomes. We only demonstrate that in all ofthe implemented algorithms, opportunism helps reduce these metrics, andwe do not provide a full comparison of the algorithms.4.3.3 MethodologyFor every (pgen, pswap, L,N,M, k) configuration, we first generate N re-quests in the network and then run each algorithm 100 times. We measureeach metric in every runtime and calculate its average across the 100 iter-ations. Then, we repeat this procedure another 50 times, each time witha different set of requests. Each one of these outer iterations produces anaverage total waiting time for its corresponding N requests, and an averagelink waiting time for the links. We calculate the average of these aver-age values, and then compare them across the different algorithms we haveimplemented. This allows us to assess the essence of the overall effect of op-portunism on the performance of a given network, by including many groups414.4. Resultsof requests in many scenarios.4.4 ResultsWe have implemented three state-of-the-art algorithms alongside theiropportunistic versions. These algorithms are Modified Greedy (MG) [CRDW19],Nonoblivious Local (NL, we have chosen this name for this algorithm forease of use) [PKT+19], and QPASS (QP) [SQ20]. It is worth mentioningthat our version of the QP protocol is slightly modified, and to be more ex-act, it is a combination of the QPASS and QCAST algorithms from [SQ20].Furthermore, the original QP algorithm in [SQ20] uses a novel metric, EXT,when finding paths for requests in arbitrary networks. Due to the completehomogeneity of the grid topology, the EXT metric is equivalent to the hopdistance, in terms of the preference it induces on different paths. Thuswe have used the ordinary hop distance for our path selection in all of thethree algorithms. In all of the figures, NOPP and OPP correspond to thenon-opportunistic and opportunistic approaches, respectively.Opportunism is Better. We start by fixing M = 5, N = 20, L = 30,k = 1, and pswap = 1, and compare the average total waiting time basedon pgen. Figure 4.7 shows the result of this comparison. The figure onthe right shows the ratio of the improvement caused by opportunism to thenon-opportunistic approach, which is obtained by dividing their difference bythe non-opportunistic values. It is clear that opportunism has improved theperformance of the network by almost 30%, and up to 45%. Furthermore,it can be seen that the QP algorithm provides better performance in thissetup.We now change the setup to another configuration, in which M , N andk stay the same, while we have L = 6 and pswap = 0.8. This new setup hasmuch more dynamism than the previous one. The results of comparing theaverage total waiting time of the three algorithms, based on pgen, is shownin Figure 4.8. We can see that in a high dynamism of the quantum network’sstate, the opportunistic approach enables significantly better performance,and this improvement is around 50%.Now we increase the network size and analyze the effect of opportunismin bigger networks. Figure 4.9 shows the average total waiting time basedon the network size, for the three algorithms, in a grid network. The setupis N = 20, L = 30, k = 1, pswap = 0.8, and pgen = 0.8. This setup issomehow an intermediate setup that is neither stable nor highly dynamic.We can see that just like small networks, opportunism significantly improves424.4. Results0.2 0.4 0.6 0.8 1.0Generation probability050100150Average total waiting time (slots)MG_NOPPMG_OPPNL_NOPPNL_OPPQP_NOPPQP_OPP0.2 0.4 0.6 0.8 1.0Generation probability0.20.30.4Improvement ratioMGNLQPFigure 4.7: Average total waiting time in a grid network, with the fixedscenario M = 5, N = 20, L = 30, k = 1, and pswap = 1. The figure onthe right shows the ratio of the improvement caused by opportunism to thenon-opportunistic approach.Table 4.1: Average link waiting time in the MG algorithmpgen 0.1 0.3 0.5 0.7 0.9NOPP 12.9 8.8 7.18 6.3 5.3OPP 11.5 6.15 4.16 3.6 3.13Improv. 11% 30% 41% 43% 41%performance in bigger networks as well.We finally present Table 4.1, in which we have shown the effect of op-portunism on the average link waiting time. The bottom row shows theimprovement with respect to the non-opportunistic approach. We have onlyincluded the MG algorithm. Nonetheless, the improvement is similar in theother two algorithms. The results clearly demonstrate the fact that oppor-tunism decreases the average link waiting time, thus increasing the efficiencyof resource consumption. The setup in this part is N = 20, M = 10, L = 30,pswap = 1, and k = 1.Degrees of Opportunism. In this part, we demonstrate the effect ofchanging the degree of opportunism. The results verify our analysis, andas we can see in Figure 4.10, opportunism has a spectrum of choices foralgorithm design. For a reason similar to the case of link waiting time, wehave only included the MG protocol here. In Figure 4.10, the number after434.4. Results0.2 0.4 0.6 0.8 1.0Generation probability0200400600Average total waiting time (slots)MG_NOPPMG_OPPNL_NOPPNL_OPPQP_NOPPQP_OPP0.2 0.4 0.6 0.8 1.0Generation probability0.20.40.60.8Improvement ratioMGNLQPFigure 4.8: Average total waiting time in a grid network, with the fixedscenario M = 5, N = 20, L = 6, k = 1, and pswap = 0.8. The figure onthe right shows the ratio of the improvement caused by opportunism to thenon-opportunistic approach.OPP is the opportunism degree.444.4. Results6 8 10 12 14Size10152025303540Average total waiting time (slots)MG_NOPPMG_OPPNL_NOPPNL_OPPQP_NOPPQP_OPP6 8 10 12 14Size0.200.250.300.350.400.450.500.55Improvement ratioMGNLQPFigure 4.9: Average total waiting time in a grid network, with the fixedscenario N = 20, L = 30, k = 1, pswap = 0.8, and pgen = 0.8. The figure onthe right shows the ratio of the improvement caused by opportunism to thenon-opportunistic approach.0.2 0.4 0.6 0.8 1.0Generation probability0255075100125150175Average total waiting time (slots)MG_OPP1MG_OPP2MG_OPP3Figure 4.10: Average total waiting time in a grid network across differentopportunism degrees, with the fixed scenario N = 20, L = 30, pswap = 0.8,and pgen = 0.8. The number after OPP is the opportunism degree.45Chapter 5Conclusion5.1 SummaryWe have introduced opportunistic routing, and proposed it as an ap-proach to increase the efficiency of quantum routing algorithms. We haveanalyzed this improvement in efficiency by checking two of the main met-rics in any given network: waiting time and transmission rate. Our results,whether mathematical or experimental, demonstrate our claims, and pavethe way for a more involved analysis of opportunism and similar conceptsin quantum networks.Specifically, we show that opportunism introduces two gains in the wait-ing time of requests in a given network. The first gain is the swapping gain,and is inherent in the fact that entanglement generation and swapping canbe done in parallel. The second gain is the reservation gain, showing theeffect of opportunism on the group delay of a number of requests, even whenthe swapping gain vanishes. Furthermore, we demonstrate that opportunis-tic routing increases the transmission rate in line networks, and providelower and upper bounds for this rate. Finally, we introduce and analyze k-opportunism as a flexible framework for applying the opportunism principlein general quantum routing algorithms.Our mathematical results are followed by experimental verification, inwhich we both show some numerical results related to the line networkanalyzed in Chapter 3, and demonstrate the effect of opportunism in moregeneral scenarios in a grid network.5.2 DiscussionWe use the discussion section to present a reflective view on oppor-tunism, and then to discuss the limitations of our proposal. We begin witha reflective view, in light of the related literature introduced in Section 1.4.In terms of routing, our results can be applied to any given routing al-gorithm. Both of our analysis and experiments hide the details of the path465.2. Discussionselection part, and apply the opportunism principle on top of the routing.Therefore, opportunism can be coupled to any given routing algorithm as aguiding principle for the forwarding stage. In fact, this can even be general-ized to more involved protocols. For instance, swapping is not the only wayto consume the distributed entanglement, just as pairwise entanglement isnot the only possible resource to consume in quantum networks. Whateverthe underlying resource and the consumption pattern are, the overall pro-cess can still be divided to several steps, each with a success probability.Opportunism can readily fit into this framework as it promotes performingthese steps as soon as possible, so that the dynamic state of the network isused more efficiently.In terms of fundamental analysis, our mathematical treatment of trans-mission rate in the opportunistic case exposes the combinatorial structure ofthe underlying problem in a more accurate way. This structure rises from thefact that the overall process consists of steps with success probabilities, andtherefore the actual achievable rate is lower than the promised value. As wehave seen, in some cases the best one can do is to perform the steps as soonas possible. This can be extended to different distribution and consumptionpatterns.We now discuss the limitations of our approach. Some of these limita-tions are operational, and some are more fundamental. We start with theoperational limitations. First, we have not considered the limited memory ofa quantum computer in our modelling and simulations. Imposing this con-straint to the problem will definitely change the performance for the worse,and a complete analysis of opportunism must take this limitation into ac-count. Second, our simulations are limited to the grid topology. A morecomplete evaluation of opportunism should consider different, maybe ran-dom topologies, so that we can have more confidence in the improvementscaused by opportunistic routing. Finally, our mathematical analysis is lim-ited to a line network. It is good to extend this to more general networktopologies, both in terms of the waiting time and the transmission rate.In terms of fundamental limitations, the main point is our neglect of thetradeoff between local and global network state information. Our analysis,specially in the k-opportunistic part, does not consider the effect of wait-ing for the network state information to propagate through the network.Therefore, a more complete analysis of opportunism must take this delayinto account as well, and demonstrate its effects on the resource consump-tion efficiency.475.3. Future Work5.3 Future WorkBased on the discussion presented in Section 5.2, we can point to severaldirections for future work. In terms of resolving our limitations, the roadahead is clear, and the future work includes extending the analysis andthe simulations to more generic network topologies, while also consideringthe finite memory constraint. Furthermore, including the propagation ofnetwork state information in the k-opportunistic setting is a suitable stepfor future work.Aside from our current limitations, our analysis can be readily extendedto include more general protocols and resource types. This extension canhave two flavors. First, opportunism can be used to design new algorithmsfor different tasks in a quantum network. Second, it can be more theoretical,and delve into the combinatorial limits of communication in a quantumnetwork.48Bibliography[ABC+21] Koji Azuma, Stefan Ba¨uml, Tim Coopmans, David Elkouss,and Boxi Li. Tools for quantum network design. AVS QuantumScience, 3(1):014101, 2021. → pages 2, 5, 18[BA17] Stefan Ba¨uml and Koji Azuma. Fundamental limitation onquantum broadcast networks. Quantum Science and Technol-ogy, 2(2):024004, 2017. → pages 9[BB14] Charles H. Bennett and Gilles Brassard. Quantum cryptogra-phy: Public key distribution and coin tossing. Theor. Comput.Sci., 560:7–11, 2014. → pages 1[BBC+93] Charles H. Bennett, Gilles Brassard, Claude Cre´peau, RichardJozsa, Asher Peres, and William K. Wootters. Teleportingan unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Phys. Rev. Lett., 70:1895–1899,1993. → pages 3[BDCZ98] H.-J. Briegel, W. Du¨r, J. I. Cirac, and P. Zoller. Quantum re-peaters: The role of imperfect local operations in quantumcommunication. Phys. Rev. Lett., 81:5932–5935, 1998. →pages 4[BPvL11] Nadja K. Bernardes, Ludmi la Praxmeyer, and Peter vanLoock. Rate analysis for a hybrid quantum repeater. Phys.Rev. A, 83:012323, 2011. → pages 9, 17, 18[BRA+19] C. E. Bradley, J. Randall, M. H. Abobeih, R. C. Berrevoets,M. J. Degen, M. A. Bakker, M. Markham, D. J. Twitchen,and T. H. Taminiau. A ten-qubit solid-state spin register withquantum memory up to one minute. Phys. Rev. X, 9:031045,2019. → pages 5[BWP+17] Jacob Biamonte, Peter Wittek, Nicola Pancotti, PatrickRebentrost, Nathan Wiebe, and Seth Lloyd. Quantum ma-49Bibliographychine learning. Nature, 549(7671):195–202, 2017. → pages1[CBE21] Tim Coopmans, Sebastiaan Brand, and David Elkouss. Im-proved analytical bounds on delivery times of long-distanceentanglement. arXiv e-print arXiv:2103.11454, 2021. → pages9[CRDW19] Kaushik Chakraborty, Filip Rozpedek, Axel Dahlberg, andStephanie Wehner. Distributed routing in a quantum internet.CoRR, abs/1907.11630, 2019. → pages 5, 7, 11, 16, 18, 38, 42[DDHE09] Theodoros K. Dikaliotis, Alexandros G. Dimakis, Tracey Ho,and Michelle Effros. On the delay of network coding over linenetworks. 2009 IEEE International Symposium on Informa-tion Theory, pages 1408–1412, 2009. → pages 26[Dij59] E. W. Dijkstra. A note on two problems in connexion withgraphs. Numer. Math., 1(1):269–271, dec 1959. → pages 8[Fek23] M. Fekete. ¨U¨ber die verteilung der wurzeln bei gewissen al-gebraischen gleichungen mit ganzzahligen koeffizienten. Math-ematische Zeitschrift, 17:228–249, 1923. → pages 26[Fey82] Richard P Feynman. Simulating physics with computers.International Journal of Theoretical Physics, 21(6):467–488,1982. → pages 1[FF22] Ali Farahbakhsh and Chen Feng. Opportunistic routing inquantum networks. In IEEE INFOCOM 2022 - IEEE Con-ference on Computer Communications, pages 490–499, 2022.→ pages v[GHZ89] Daniel M. Greenberger, Michael A. Horne, and AntonZeilinger. Going beyond bell’s theorem. Bell’s Theorem,Quantum Theory and Conceptions of the Universe, pages 69–72, 1989. → pages 9[Gro96] Lov K Grover. A fast quantum mechanical algorithm fordatabase search. In Proceedings of the twenty-eighth annualACM symposium on Theory of computing, pages 212–219,1996. → pages 150Bibliography[JP12] Jean Jacod and Philip Protter. Probability essentials. SpringerScience & Business Media, 2012. → pages 27[KDW20] Wojciech Kozlowski, Axel Dahlberg, and Stephanie Wehner.Designing a quantum network protocol. Proceedings of the16th International Conference on Emerging Networking EX-periments and Technologies, page 1–16, 2020. → pages 9, 14[Kim08] H Jeff Kimble. The quantum internet. Nature,453(7198):1023–1030, 2008. → pages 2[KMSD19] Sumeet Khatri, Corey T. Matyas, Aliza U. Siddiqui, andJonathan P. Dowling. Practical figures of merit and thresh-olds for entanglement distribution in quantum networks. Phys.Rev. Research, 1:023032, 2019. → pages 2, 5, 9, 17[KRH+17] N. Kalb, A. A. Reiserer, P. C. Humphreys, J. J. W. Baker-mans, S. J. Kamerling, N. H. Nickerson, S. C. Benjamin, D. J.Twitchen, M. Markham, and R. Hanson. Entanglement dis-tillation between solid-state quantum network nodes. Science,356(6341):928–932, 2017. → pages 5[MEAG+20] Sam McArdle, Suguru Endo, Ala´n Aspuru-Guzik, Simon CBenjamin, and Xiao Yuan. Quantum computational chem-istry. Reviews of Modern Physics, 92(1):015003, 2020. →pages 1[NC02] Michael A Nielsen and Isaac Chuang. Quantum computationand quantum information, 2002. → pages 54[PD19] Alexander Pirker and Wolfgang Du¨r. A quantum networkstack and protocols for reliable entanglement-based networks.New Journal of Physics, 21(3):033003, 2019. → pages 9[PGPBL09] Stefano Pirandola, Raul Garc´ıa-Patro´n, Samuel L. Braunstein,and Seth Lloyd. Direct and reverse secret-key capacities of aquantum channel. Phys. Rev. Lett., 102:050503, Feb 2009. →pages 2, 8[PKT+19] Mihir Pant, Hari Krovi, Don Towsley, Leandros Tassiulas,Liang Jiang, Prithwish Basu, Dirk Englund, and Saikat Guha.Routing entanglement in the quantum internet. npj QuantumInformation, 5, 2019. → pages 6, 7, 11, 4251Bibliography[PLOB17] Stefano Pirandola, Riccardo Laurenza, Carlo Ottaviani, andLeonardo Banchi. Fundamental limits of repeaterless quantumcommunications. In Nature Communications, volume 8, 2017.→ pages 2, 8[PPE+20] Ashlesha Patil, Mihir Pant, Dirk Englund, Don Towsley, andSaikat Guha. Entanglement generation in a quantum networkat distance-independent rate. arXiv e-print arXiv:2005.07247,2020. → pages 8[Pra13] Ludmi la Praxmeyer. Reposition time in probabilistic imper-fect memories. arXiv e-print arXiv:1309.3407, 2013. → pages9[Pre18] John Preskill. Quantum computing in the nisq era and beyond.Quantum, 2:79, 2018. → pages 1[QNS] https://github.com/QuantumLite/QNS-Lite. → pages 37[Sho94] Peter W Shor. Algorithms for quantum computation: discretelogarithms and factoring. Proceedings of 35th annual sympo-sium on foundations of computer science, pages 124–134, 1994.→ pages 1[SMI+16] Eddie Schoute, Laura Mancinska, Tanvirul Islam, IordanisKerenidis, and Stephanie Wehner. Shortcuts to quantum net-work routing. CoRR, abs/1610.05238, 2016. → pages 7, 16[SQ20] Shouqian Shi and Chen Qian. Concurrent entanglement rout-ing for quantum networks: Model and designs. Proceedings ofthe Annual Conference of the ACM Special Interest Group onData Communication on the Applications, Technologies, Ar-chitectures, and Protocols for Computer Communication, page62–75, 2020. → pages 5, 6, 8, 11, 38, 42[Ste97] J. Michael Steele. Probability Theory and Combinatorial Op-timization. Society for Industrial and Applied Mathematics,1997. → pages 26, 27, 28[TGW14] Masahiro Takeoka, Saikat Guha, and Mark M. Wilde. Funda-mental rate-loss tradeoff for optical quantum key distribution.In Nature Communications, volume 5, 2014. → pages 252Bibliography[VMD16] Rodney Van Meter and Simon J Devitt. The path to scal-able distributed quantum computing. Computer, 49(9):31–42,2016. → pages 1[VMLMN09] Rodney Van Meter, Thaddeus D. Ladd, W. J. Munro, andKae Nemoto. System design for a long-line quantum repeater.IEEE/ACM Trans. Netw., 17(3):1002–1013, jun 2009. →pages 9[VMSL+13] Rodney Van Meter, Takahiko Satoh, Thaddeus D. Ladd,William J. Munro, and Kae Nemoto. Path selection for quan-tum repeater networks. Networking Science, 3(1-4):82–95,2013. → pages 6, 8[WEH18] Stephanie Wehner, David Elkouss, and Ronald Hanson. Quan-tum internet: A vision for the road ahead. Science, 362(6412),2018. → pages 2[Wil13] Mark M Wilde. Quantum information theory. CambridgeUniversity Press, 2013. → pages 5[WZ82] W. K. Wooters and W. H. Zurek. A single quantum cannotbe cloned. Nature, 299:802–803, 1982. → pages 2[ZDB12] M. Zwerger, W. Du¨r, and H. J. Briegel. Measurement-basedquantum repeaters. Phys. Rev. A, 85:062326, 2012. → pages17[ZZHE93] M Zukowski, A Zeilinger, MA Horne, and AK Ekert. “Event-ready-detectors” Bell experiment via entanglement swapping.Physical review letters, 71(26):4287–4290, 1993. → pages 353Appendix AQubit, Entanglement, andProtocolsIn this appendix we introduce some elementary concepts of quantum in-formation. The material here is mostly a reformulation of the textbook [NC02].This material is not necessary to understand the main body of the thesis,and is brought here for the sake of completeness.A.1 QubitThe state of physical particles is often captured by the concept of aqubit (quantum bit). Examples include the polarization of a photon andthe alignment of a nuclear spin in a uniform magnetic field. All of thedifferent examples can be gathered in a single mathematical formulation, asfollows. A qubit is a two dimensional vector in the complex Hilbert vectorspace, with an amplitude equal to one. Using the Dirac notation, if we showthe computational basis states of this space with |0〉 and |1〉, a qubit |φ〉 isdefined as:φ = α|0〉+ β|1〉,such that α and β are complex numbers and α2+β2 = 1. In vector notation,we have the following representation:|0〉 =(10), |1〉 =(01), |φ〉 =(αβ).This definition shows that, unlike classical bits, qubits can be in a super-position of the |0〉 and |1〉 states. Since the Hilbert space also has an innerproduct, we can define this inner product for quantum states as well. Theinner product of the two states |ψ〉 and |φ〉 is shown with 〈ψ|φ〉, in which〈ψ| is the conjugate transpose of the vector |ψ〉.This formulation can be extended to higher dimensions in two ways.First, a general quantum state of a single entity can be a vector in a d-dimensional complex Hilbert space with the basis vectors |0〉, |1〉, . . . , |d−1〉.54A.1. QubitSuch a state |φ〉 = ∑d−1i=0 ai|i〉 is called a qudit. We do not consider qudits,and use qubits for our system.The second way of going to higher dimensions is when we look at systemswith multiple qubits. The quantum state of n qubits is a vector belongingto the span of the tensor products of the basis vectors of individual qubitspaces, meaning that the resulting state is a vector in the 2n-dimensionalcomplex Hilbert space. For instance, in the two-dimensional case, the stateof two qubits in the systems A and B is a vector with amplitude equal toone, belonging to the span of the vectors |0〉A⊗|0〉B, |0〉A⊗|1〉B, |1〉A⊗|0〉B,and |1〉A ⊗ |1〉B, which are defined as follows:|0〉A ⊗ |0〉B =1000 , |0〉A ⊗ |1〉B =0100|1〉A ⊗ |0〉B =0010 , |1〉A ⊗ |1〉B =0001 .For simplicity, we write the joint state of the qubits |φ1〉, |φ2〉, . . . , |φn〉 as|φ1φ2 . . . φn〉. For instance, we write the joint state of the two qubits |0〉Aand |1〉B as |01〉AB, and we omit the AB subscript when the context is clear.The reader should keep in mind that a tensor product is hidden in the |01〉notation.The evolution of a qubit is captured by Schro¨dinger’s equation. Solvingthis equation leads to unitary operators over the Hilbert space. That is,for every evolution there exists a unitary matrix U such that the state ofthe qubit |φ〉 after the evolution is U |φ〉. The unitary constraint forcesthe resulting state to have an amplitude equal to one, and therefore it isa valid state. Similar to qubits, operators on individual qubit systems canbe combined via the tensor product to obtain the overall operator on thejoint state. For instance, the result of applying U to |φ〉A and V to |ψ〉B isequivalent to the result of applying U ⊗ V to |φψ〉AB.A very important concept in interacting with quantum systems is mea-surement. Generally, we can measure the state of a qubit in a given basis.After the measurement, the state of the qubit is mapped to each one ofthese basis states with a corresponding probability. For instance, measuringthe qubit |φ〉 = α|0〉 + β|1〉 in the computational basis {|0〉, |1〉} maps thequbit to the states |φ〉 = |0〉 and |φ〉 = |1〉 with probability equal to α2 and55A.2. Entanglementβ2, respectively. This is the reason for the constraint α2 + β2 = 1. Thisis a special case of the more general projective measurements, in which themeasurement is represented by the operators {Πi}mi=1 such that for every i, jwe have ΠiΠj = δijΠi and∑mi=1 Πi = I, in which δij is the Kronecker deltafunction and I is the identity matrix. The outcome of the measuring thestate |φ〉 will be i with probability pi = 〈φ|Πi|φ〉, and then the state will be:Πi|φ〉√pi.Note that the denominator is a normalization factor to make the amplitudeof the resulting state equal to one.A.2 EntanglementEntanglement is a special property existing between two or more qubits.In order to define entanglement, we have to first define separable states. Astate |φ〉 of n qubits is called separable if there exist qubits |φ1〉, |φ2〉, . . . , |φn〉in the constituent systems such that |φ〉 = |φ1〉 ⊗ |φ2〉 ⊗ · · · ⊗ |φn〉. A statethat is not separable is called entangled.Entanglement is the bedrock of many interesting phenomena. The mainreason for this is the non-local correlations that it provides. We show thisby going through an example. Perhaps the most famous entangled state isthe following state:|ψ〉 = |00〉+ |11〉√2.Measuring the first qubit of this state in the computational basis maps thegeneral state to one of the states |00〉 and |11〉, each with a probabilityequal to 0.5. Whatever the result of this measurement is, measuring thesecond qubit in the computational basis after that will yield the same result.That is, if measuring the first qubit results in 0, then the second qubitwill deterministically yield a result of 0 after measurement. This non-localcorrelation has led to many useful and counter-intuitive applications, as wewill see in the teleportation example.A.3 TeleportationIn this section we provide the mathematics of the teleportation protocol.Before we start, we introduce the following orthogonal basis for the two-qubit56A.3. Teleportationspace:|ψ+〉 = |00〉+ |11〉√2, |ψ−〉 = |00〉 − |11〉√2|φ+〉 = |01〉+ |01〉√2, |φ−〉 = |01〉 − |10〉√2.These states are all entangled, and this basis is called the Bell basis. It playsan important role in teleportation.Imagine the two parties B and C who share the state |ψ+〉. Also assumethat the system B has a qubit |λ〉 = α|0〉+ β|1〉 in an ancilla system A andwants to teleport it to the system C. We can write the joint state of thesesystems as |λψ+〉ABC :|λψ+〉ABC = 1√2(α|0〉+ β|1〉)A(|00〉+ |11〉)BC =1√2(α|000〉+ α|011〉+ β|100〉+ β|111〉)ABC .We will omit the ABC subscript in the rest of this section. Since the Bellstates form a basis, we can use them to create any two-qubit state. Specifi-cally, we have the following equations:|00〉 = |ψ+〉+ |ψ−〉√2, |11〉 = |ψ+〉 − |ψ−〉√2|01〉 = |φ+〉+ |φ−〉√2, |10〉 = |φ+〉 − |φ−〉√2.We now use these equations to rewrite the AB part of the joint ABC state:|λψ+〉 = 1√2(α|000〉+ α|011〉+ β|100〉+ β|111〉) =12(α(|ψ+〉+ |ψ−〉)|0〉+ α(|φ+〉+ |φ−〉)|1〉+β(|φ+〉 − |φ−〉)|0〉+ β(|ψ+〉 − |ψ−〉)|1〉) =12(|ψ+〉(α|0〉+ β|1〉) + |ψ−〉(α|0〉 − β|1〉)+|φ+〉(β|0〉+ α|1〉)) + |φ−〉(−β|0〉+ α|1〉)).We can see that a simple reformulation allows us to mathematically push theinformation of the |λ〉 state to the system C. Now, since B holds both of AB57A.3. Teleportationsystems, he can perform a measurement in the Bell basis. The operatorscorresponding to this measurement are Π1 = |ψ+〉〈ψ+|, Π2 = |ψ−〉〈ψ−|,Π3 = |φ+〉〈φ+|, Π4 = |φ−〉〈φ−|. One can verify to see that these operatorssatisfy the conditions mentioned in Section A.1. These operators will mapthe AB system to one of the Bell states, each with a probability equal to 14 .To see this, we only demonstrate one possible outcome, since the other casesare completely similar. First, observe that measuring Π1 on the AB systemis equivalent to measuring Π1 ⊗ I on the ABC system. The probability ofobtaining the outcome 1 is equal to:p1 = 〈λψ+|Π1 ⊗ I|λψ+〉 =12〈λψ+|(Π1|ψ+〉 ⊗ I(α|0〉+ β|1〉) + Π1|ψ−〉 ⊗ I(α|0〉 − β|1〉)+Π1|φ+〉 ⊗ I(β|0〉+ α|1〉) + Π1|φ−〉 ⊗ I(−β|0〉+ α|1〉)) =12〈λψ+|(|ψ+〉(α|0〉+ β|1〉)) = 14(〈ψ+|ψ+〉(α〈0|+ β〈1|)(α|0〉+ β|1〉)+〈ψ−|ψ+〉(α〈0| − β〈1|)(α|0〉+ β|1〉) + 〈φ+|ψ+〉(β〈0|+ α〈1|)(α|0〉+ β|1〉)+〈φ−|ψ+〉(−β〈0|+ α〈1|)(α|0〉+ β|1〉)) = 14,in which we have used the fact that the Bell states are orthogonal. Thisanalysis also shows that the post-measurement state in this case is:12 |ψ+〉(α|0〉+ β|1〉)√14= |ψ+〉AB(α|0〉+ β|1〉)C = |ψ+〉AB|λ〉C .We can see that the state λ has effectively been teleported from A to C,which means B and C have managed to perform a teleportation. In thegeneral case, since the outcome of the measurement has four possibilities,a similar analysis shows that the state of C depends on the measurementoutcome as follows:1 : α|0〉+ β|1〉, 2 : α|0〉 − β|1〉, 3 : β|0〉+ α|1〉, 4 : −β|0〉+ α|1〉.We can see that the outcome in the general case is not completely equal tothe initial state |λ〉. However, we can see that in each case, applying thefollowing operators to the remaining state at C takes us to the desired state:1 :(1 00 1), 2 :(1 00 −1), 3 :(0 11 0), 4 :(0 1−1 0).58A.4. SwappingTherefore, all B has to do is to inform C of the result of the measurement.Since we have four possible outcomes, this can be done by sending twobits of classical information on a classical channel. Once C receives thisinformation, she can apply the corresponding operation and obtain the state|λ〉 at her side. Note that all of these operations are unitaries, and thereforevalid quantum operations. This concludes the teleportation protocol.A.4 SwappingThe swapping protocol is very similar to the teleportation protocol innature. Assume that A and B share the state |ψ+〉AB, and B and D sharethe state |ψ+〉CD. Note that B holds both of the systems B and C, andtherefore we have the three separate entities A and B and D. The goal isto consume these entangled states to establish entanglement between A andD in the form of state |ψ+〉.We can write the joint state of the system as follows:|ψ+ψ+〉ABCD = 12(|00〉+ |11〉)AB(|00〉+ |11〉)CD =12(|0000〉+ |0011〉+ |1100〉+ |1111〉)ABCD.Similar to the teleportation protocol, we can rewrite the BC part of thisstate as the superposition of the Bell basis states, as follows:|ψ+ψ+〉ABCD = 12(|0〉A(|ψ+〉+ |ψ−〉)BC |0〉D + |0〉A(|φ+〉+ |φ−〉)BC |1〉D+|1〉A(|φ+〉 − |φ−〉)BC |0〉D + |1〉A(|ψ+〉 − |ψ−〉)BC |1〉D),which can be reorganized as:12(|ψ+〉BC(|00〉+ |11〉)AD+ |ψ−〉BC(|00〉−|11〉)AD+ |φ+〉BC(|01〉+ |10〉)AD+|φ−〉BC(|01〉 − |10〉)AD) =12(|ψ+〉BC |ψ+〉AD + |ψ−〉BC |ψ−〉AD + |φ+〉BC |φ+〉AD + |φ−〉BC |φ−〉AD),in which we have also reorganized the systems for better demonstration.Now, B measures the BC systems in the Bell basis. Similar to the analysisin Section A.3, the resulting state will be one of the Bell states with equalprobability. More importantly, the remaining state at the AD systems will59A.4. Swappingalso be in the same state, as can be seen from the reorganized joint statebefore the measurement. Therefore, B can inform A and D about the mea-surement outcome through classical channels, and they can perform a jointoperation to transform the remaining Bell state in the AD systems backto the |ψ+〉AD state. This is once again a valid operation since transform-ing basis states to one another is a unitary operation. This concludes theswapping protocol.60
Thesis/Dissertation
eng
Electrical Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Feng, Chen
Opportunistic routing in quantum networks
Text