STORY OF THE MONTH
(Ship-)wrecked networking: an intuition of network switching techniques and their application in entanglement-based communication.
During my months of adventurous navigation through the oceans of the world, I found a very interesting diary, supposedly belonging to a telecommunications engineer, Alice Doe, who years ago disappeared while on her way to a conference somewhere in the Polynesia. The diary reads like so:
Day 1: Our ship! The cruise I was on just hit a big rock and sank into the sea, leaving me stranded in a deserted island in a small, peculiar archipelago. I can see that my friend Charlie is on a nearby island, close enough that we can hear each other, but the water is infested with sharks, so we cannot get together! I wonder if my dear husband Bob is alright, somewhere in this archipelago.
Day 2: After getting a small refuge ready and collecting some food and water, I chatted with Charlie. We have been trying to reach out to whoever’s island is near our own, and now we have reached a consensus about how everyone is disposed over these islands. Bob is fine, but he is quite far, so it is quite hard to communicate with him. Through Charlie, I have recruited Denise and Erik, in islands between us and Bob, to help me create a chain of voice so that my husband and I can exchange a few words, and we have been able to tell each other about our respective situations. What a relief!
Figure 1. Diagram of the circuit switching-based communication between Alice and Bob.
Day 4: Other people within the archipelago have heard about our little chain of voice trick, and have started using it too. Now I am constantly finding that Charlie and everyone close by is busy because they have been asked to relay chitchat for other guys. It sucks! But luckily, I have an idea.
Day 6: My idea is working wonders on the efficiency of our inter-island communication. I have convinced everyone to switch to a different mechanism: throwing rocks. Anyone that wants to send a message just has to somehow carve it into one of the rocks that fill the beaches of the archipelago, together with the destination of the message. Then, they can throw the rock to a nearby island that is closer to the destination, deciding which island based on information that they may have about the busyness of its inhabitants. At some point, those guys will find the rock in their beach, and just relay it to another island making sure that it gets closer to the destination. Because the islands are not that close, sometimes the rock will fall into the sea, but we can just carve a copy for backup before throwing it. It has been working like a charm. Now I can always send my messages to Bob without waiting for anyone, and without first appointing a direct path of islanders. It can take some time to receive the responses, though!
Figure 2. Diagram of the packet switching-based communication between Alice and Bob.
Day 11: Following discussion with Bob, we have agreed that I should try to send him some drugs that I found in my island, hidden under debris from the shipwreck. To do this, I do not want to just throw them island to island like we do with the rocks, since this would risk losing the valuable drugs. Therefore, I have once again recruited Charlie, Denise and Erik for a new technique. We will use some vines to prepare ropes, attach a rock to one end of the rope and hold the other end. Then, we will throw the rock to the next island, like we do for hop-by-hop messaging, and if we are successful, each islander will hold one end of the previous rope and one end of the next rope (except from Bob and me). Then, Charlie, Denice and Erik can each tie their ends together, and Bob and me will each hold one end of the same continuous rope. At this point, I just need to tie the drugs to my end (in a watertight container) and let Bob know that he can pull to get them. We do not care in which order the ropes are linked from one island to another, so we can all start throwing the rocks at the same time. This is convenient, because the sharks may get entangled with ropes that are tended for a long time, breaking them, so we need to act fast.
Day 15: My scheme for transmission of valuable items has become popular among islanders, and a sort of trade system is being established. Sadly, this once again requires constant attention of people in the path, leading to conflicts between transmissions. I wonder if some island-to-island solution would be worth exploring. On one hand, it could improve the efficiency of our little archipelago-network, but it could also increase the time ropes are floating between islands, leading to most of them breaking due to the sharks. In any case, for now I will focus on upgrading my refuge. I think a big storm is coming…
Figure 3. Diagram of the rope-based communication between Alice and Bob.
The diary suddenly ends there. After learning of this great optimization problem, I decided to focus my research on exploring connectionless, entanglement-based quantum networks… Well, in reality, I have not found a diary like this, nor have I spent months living intrepid adventures overseas. It makes me sound cool, though.
Never mind. This silly story tries to convey how different switching techniques evolved in the classical Internet that we use every day, and how we are still trying to figure out how to apply these concepts to quantum networks. At the beginning of network design, circuit switching was used, which we exemplify here in Figure 1. For Alice and Bob to communicate, they first incur in a channel establishment phase, where they discuss with other islanders (nodes) the path of the “voice link”. This result in a situation where the words from Alice to Bob and backwards can be exchanged with constant and known delay, but relying on the entire attention of Charlie, Denise and Erik. Once more users start using this mechanism, the shortcomings of this approach soon become apparent: poor resource utilization.
To remedy this, the packet-switched paradigm was introduced. Now, data is split into one or more packets of (possibly) variable length which contain a header with some routing. In our example, this corresponds to the rocks being thrown, which get a carving with the destination island. Then, these packets are transmitted hop-by-hop, where each node may store them in a queue and send them when the channels are available. This technique is known as store-and-forward, and it allows each node to select the next hop based on traffic information. In Figure 2, for example, Alice may choose to throw the first rock either to Charlie, or to another islander, which we may call Francis, depending on how busy they are. In general, packet switching improves the resource utilization within the network, and therefore leads to better performance overall, at the cost of less predictable parameters for each round of communication.
Finally, the case where ropes are used to pull unique resources from one island to another tries to simulate an entanglement-based quantum network. Differently from classical bits, arbitrary qubits cannot be copied at will, and therefore sending the qubit directly through the network risks losing its information (this can be prevented with quantum repeaters that implement complex quantum error correction, but this is out of the scope of this month’s story). A solution is to distribute entanglement across the nodes in the network. This is just a resource which can later be used to transmit the desired state, e.g. through quantum teleportation[1], and because the entangled pairs are a known quantum system, an arbitrary number of copies can be prepared. After each pair of neighbouring nodes has generated an entangled link (rope) between them, these elementary links can be connected (tied) through what is called entanglement swapping.
As in the example, where sharks may break our ropes, quantum states naturally decohere inside quantum memories, and thus latency is a critical factor in entanglement-based communication. Moreover, entanglement distribution is not an orderly process, as it does not matter what link (rope) is completed first. For these reasons, up until this point most schemes assume a circuit switching-like approach, where a path is first established and then the nodes in the path attempt entanglement distribution all at the same time. In figure 3, Alice will try to connect with rope to Charlie, Charlie to Denice, Denice to Erik and, finally, Erik to Bob. Once any of the intermediate nodes are holding two ends of a rope, they can tie them up, eventually resulting in a single rope connecting Alice and Bob. Once again, this implies an establishment phase where all of the participants are made aware of the connection being attempted, and moreover, they need to be prepared to receive and connect the ropes.
My research focuses on finding out how we can extract value from the ideas of packet switching in classical networks, namely connectionless, hop-by-hop communication, and apply them to quantum networks. This can help improve their efficiency, as well as boost their integrability with existing infrastructure. To read more on the topic of entanglement-based quantum repeaters, one can see [2,3].
[1] C.H. Bennet et al. “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels”. Phys. Rev. Lett. 70.1895 (1993).
[2] H.J. Briegel et al. “Quantum repeaters: The role of imperfect local operations in quantum communication”. Phys. Rev. Lett. 81.5932 (1998).
[3] W.J. Munro et al. “Inside quantum repeaters”. IEEE Journal of Selected Topics in Quantum Electronics, vol. 21, no. 3, pp. 78-90 (2015).