Chapter 16 (Quantum Network on Graph)
To fully benefit from the advantages of quantum technology, it is necessary to design and implement quantum networks [91, 92] that are able to connect distant quantum processors through remote quantum entanglement distribution. However, despite the tremendous progress of quantum technologies, efficient long‐distance entanglement distribution remains a key problem, due to the exponential decay of the communication rate as a function of distance [93, 94]. A solution to counteract the exponential decay loss is the adoption of quantum repeaters [95, 96]. Instead of distributing entanglement over a long link, entanglement will be generated through shorter links. A combination of entanglement swapping [97] and entanglement purification [98] performed at each quantum repeater enables the entanglement to be extended over the entire channel. Now a simple question arises: “when does a repeater ensure higher entanglement distribution over the direct long link?”
Different from classical information, quantum information (e.g., qubits) cannot be copied due to the no‐cloning theorem [99, 100]. Hence, quantum networks rely on the quantum teleportation process (Chapter 8), [101] as a unique feasible solution, transmitting a qubit without the need to physically move the physical particle storing the qubit. The quantum teleportation of a single qubit between two different nodes requires (i) a classical communication channel capable of sending two classical bits and (ii) the generation of a pair of maximally entangled qubits, referred to as Einstein–Podolsky–Rosen (EPR) pair, with each qubit stored at each remote node. In the following, the generation of an EPR pair at two different nodes is referred to as remote entanglement generation. Under this umbrella, in this chapter we discuss the following specific problems: optimal routing in quantum networks, network model, entanglement, optimal quantum routing, quantum network on symmetric graph, quantum walks, discrete quantum walks on a line (DQWL), Performance study of DQWL, multidimensional quantum walks, the quantum random walk, Channel Entropy, quantum random walks on general graphs, continuous time quantum random walks, and searching large‐scale graphs.
Chapter 17 (Quantum Internet): Finally, in this chapter we discuss current progress in building up a quantum Internet [91, 102–104] intended to enable the transmission of quantum bits (qubits) between distant quantum devices to achieve the tasks that are impossible using classical communication. For example, with such a network we can implement cryptographic protocols like long‐distance QKD [105, 106], which enables secure communication. Apart from QKD, many other applications in the domain of distributed computing and multi‐party cryptography [107] have already been identified at different stages of quantum network development [108].
Like the classical Internet, a quantum Internet consists of network components such as physical communication links, and eventually routers [2, 109–111]. However, due to fundamental differences between classical and quantum bits, these components in a quantum network behave rather differently from their classical counterparts. For example, qubits cannot be copied, which rules out retransmission as a means of overcoming qubit losses [112]. To nevertheless send qubits reliably, a standard method is to first produce quantum entanglement between a qubit held by the sender and a qubit held by the receiver. Once this entanglement has been produced, the qubit can then be sent using quantum teleportation [112, 113]. This requires, in addition, the transmission of two classical bits per qubit from the sender to the receiver. Importantly, teleportation consumes the entanglement, meaning that it has to be re‐established before the next qubit can be sent. When it comes to routing qubits in a network, one hence needs to consider routing entanglement [102, 114–117]. In this chapter, we discuss the Internet system model, routing algorithms, the quantum network on general virtual graph, the quantum network on ring and grid graph, quantum network on recursively generated graph (RGG), recursively generated virtual graphs, the quantum network protocol stack, preliminaries, the quantum network protocol stack, Layer 3 – reliable state linking, and Layer 4 – region routing.
References
1 1 https://www.technologyreview.com/2019/09/18/132956/ibms-new-53-qubit-quantum-computer-is-the-most-powerful-machine-you-can-use/.
2 2 https://fortune.com/2020/09/15/ibm-quantum-computer-1-million-qubits-by-2030/.
3 3 https://www.nature.com/articles/nature.2013.12999.
4 4 Safavin, S.R. and Landgrebe, D. (1991). A survey of decision tree classifier methodology. IEEE Trans. Syst. Man Cybern. 21 (3): 660–674.
5 5 Fodor, I.K. A survey of dimension reduction techniques Lawrence Livermore Natl. Laboratory, 2002
6 6 C.O.S. Sorzano, Vargas, J., Pascual‐Montano, A., et al., A survey of dimensionality reduction techniques, https://arxiv.org/ftp/arxiv/papers/1403/1403.2877.pdf
7 7 Lin, Y.Y., Liu, T.L., and Fuh, C.S. (2011). Multiple kernel learning for dimensionality reduction. IEEE Trans. Pattern Anal. Machine Intell. 33: 1147–1160.
8 8 Jolliffe, I.T. (2002). Principal Component Analysis. Wiley.
9 9 Stanford https://cs231n.github.io/neural‐networks‐1
10 10 Haykin, S. (1999). Neural Networks: A Comprehensive Foundation, 2e. Upper Saddle River, NJ: Prentice‐Hall.
11 11 D. Gunning. Explainable artificial intelligence (XAI), Defense Advanced Research Projects Agency (DARPA). Accessed: Jun. 6, 2018. [Online]. Available: http://www.darpa.mil/program/explainable‐artificialintelligence
12 12 A. Henelius, K. Puolamäki, and A. Ukkonen. (2017). “Interpreting classifiers through attribute interactions in datasets.” [Online]. Available: https://arxiv.org/abs/1707.07576
13 13 Letham, B., Rudin, C., McCormick, T.H., and Madigan, D. (2015). Interpretable classifiers using rules and Bayesian analysis: building a better stroke prediction model. Ann. Appl. Statist. 9 (3): 1350–1371.
14 14 Krening, S., Harrison, B., Feigh, K.M. et al. (2016). Learning from explanations using sentiment and advice in RL. IEEE Trans. Cogn. Develop. Syst. 9 (1): 44–55.
15 15 W. L. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” NIPS 2017, pp. 1024–1034, 2017.
16 16 T. N. Kipf and M. Welling, “Semi‐supervised classification with graph convolutional networks,” ICLR 2017, 2017.
17 17 A. Sanchez‐Gonzalez, N. Heess, J. T. Springenberg, J. Merel, M. Riedmiller, R. Hadsell, and P. Battaglia, “Graph networks as learnable physics engines for inference and control,” arXiv preprint arXiv:1806.01242, 2018.
18 18 P. Battaglia, R. Pascanu, M. Lai, D. J. Rezende et al., “Interaction networks for learning about objects, relations and physics,” in NIPS 2016, 2016, pp. 4502–4510.
19 19 A. Fout, J. Byrd, B. Shariat, and A. Ben‐Hur, “Protein interface prediction using graph convolutional networks,” in NIPS 2017, 2017, pp. 6530–6539.
20 20 T. Hamaguchi, H. Oiwa, M. Shimbo, and Y. Matsumoto, “Knowledge transfer for out‐of‐knowledge‐base entities: A graph neural network approach,” in IJCAI 2017, 2017, pp. 1802–1808.
21 21 H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song, “Learning combinatorial optimization algorithms over graphs,” arXiv preprint arXiv:1704.01665, 2017.
22 22 Borgers, T. and Sarin, R. (1997). Learning through reinforcement and replicator dynamics. J. Econ. Theory 77: 1–14.
23 23 Brown, G. (1951). Iterative solutions of games by fictitious play. In: Activity Analysis of Production and Allocation (ed. T.C. Koopmans), 374–376. New York: Wiley.
24 24