1 Introduction

A quantum walk is by and large a quantum mechanical analogue of a classical random walk [1,2,3,4,5] without having the randomness associated with the dynamics. Quantum walks have served as a basis for development of various quantum algorithms and in modelling the dynamics of many quantum systems. They are also becoming an increasingly relevant topic of interest beyond the conventional quantum information and physics community. We have two well-studied versions of quantum walk, the continuous-time quantum walk (CTQW) and the discrete-time quantum walk (DTQW). The dynamics of the CTQW are defined only on a position Hilbert space, whereas an additional coin Hilbert space along with the position Hilbert space is used to define the dynamics of DTQW. Both the variants have been shown to be effective at performing various quantum computational tasks [6,7,8,9,10,11,12,13]. Beyond computational tasks, CTQW has played an important role in modelling the energy transfer in photosynthetic material [14]. The additional coin degree of freedom in DTQW serves as an extra degree of freedom to control the dynamics and model the physical phenomena, such as topological phases [15,16,17,18,19,20,21], and Dirac equation and its associated dynamics [22,23,24,25,26,27,28,29,30,31,32]. Therefore, in terms of utility, a quantum walk is a very powerful scheme for quantum simulations, in direct analogy to the role of classical random walk in classical simulations over the past few decades. Experimental implementation of quantum walks in a variety of quantum systems, such as nuclear Magnetic Resonance (NMR) systems [33], integrated photonics [34,35,36], ion traps [37, 38], and cold atoms [39], makes it a promising protocol of future quantum technologies.

Complex networks have become a part and parcel of modern life and scientific research. As a consequence, there has been significant research in the field of network analysis, which is applied to not only the World Wide Web [40, 41], but also to social and biological systems [42, 43]. Problems pertaining to communication, storage and transport of information have seen significant interest from the scientific community and have been studied in the form of network analysis. With the recent advances in the field of quantum information and computation, quantum networks are envisioned to dominate the architecture of all aspects of quantum information, communication and computation protocols. Some early versions of these networks have already been created and analysed [44,45,46,47,48,49,50,51,52,53,54,55,56]. Some of the physical models exhibit interesting properties such as long-distance entanglement [57,58,59,60].

A fundamental problem in a vast network of information therefore becomes one of classification, search and retrieval. In this respect, for a complex network, ranking nodes of the network on the basis of relevance of information required becomes a challenge of some importance. A significant development in this field has been the introduction of the PageRank algorithm [61,62,63,64,65,66], which is the heart of Google’s search engine. An important step in this direction for quantum networks has been the successful attempt [67] to quantize the classical protocol, based on Szegedy’s scheme [68] for quantization of Markov chains.

It has been proven that the quantum methods for ranking nodes outperform their classical counterparts  [69,70,71,72] on different kinds of networks, but the quantum protocol tested is based on Szegedy’s scheme. Szegedy’s scheme is a variant of a DTQW that does not require a coin operator, but needs an additional Hilbert space of the same dimension as its position space. Thus, the additional resource requirement makes its physical realization an uphill task compared to a standard single-particle DTQW implementation where the internal degree of freedom of the particle acts as a coin Hilbert space.

To overcome the difficulty of using an additional position space in implementing the existing quantum rank algorithms, we propose a new algorithm based on a directed DTQW (D-DTQW) which will require only a position and a coin Hilbert space to implement the algorithm effectively. This algorithm will be relevant beyond ranking node in networks, to rank active centres on chemical compounds in the order of reactivities, to model dynamics in complex quantum networks and to analyse the connectivity of quantum communication networks and other quantum architectures.

In order to rank the nodes of a quantum network, it becomes essential to preserve some of the quantum properties of the network in an objective, network-independent manner. In the classical protocol, this was visualized by a browser performing a random walk on the Web, which is what made Google’s algorithm a success. Going by the same analogy for a quantum network, our quantum algorithm identifies the nodes of a network as states in a multi-dimensional Hilbert space, and just like its classical counterpart, it performs a D-DTQW on the network. Since a single-particle DTQW has been experimentally implemented in various quantum systems, its directed variant will also be directly implementable on a physical quantum circuit, which makes the algorithm practically scalable for a network as well.

This paper is organized as follows: in Sect. 2, we present an overview and brief analysis of our D-DTQW algorithm and how it ranks the nodes on a graph. We also make some note on physical realization of some operators in our algorithm. Section 3 presents an overview of the classical page ranking algorithm and Szegedy’s walk. It also highlights key differences between our scheme and the scheme based on Szegedy’s walk. In Sect. 4, we present the results of our simulations and comparisons with the classical PageRank algorithm on some networks. We collate all our results and conclude with remarks in Sect. 5.

2 Directed discrete-time quantum walk algorithm for ranking nodes

2.1 Discrete-time quantum walk

The DTQW for a single-particle walker on a one-dimensional lattice is defined as an evolution in the Hilbert space \({{\mathcal {H}}} = {{\mathcal {H}}}_C \otimes {{\mathcal {H}}}_P\), where \({{\mathcal {H}}}_C\) and \({{\mathcal {H}}}_P\) are coin and position Hilbert spaces, respectively. The coin space is taken to have the basis states \(\left\{ {|{\uparrow }\rangle }, {|{\downarrow }\rangle } \right\} \) which represents the internal states of the walker. The position space is defined by the basis states \({|{x}\rangle }\), where \(x \in {{\mathbb {Z}}}\). The initial state of the walker is a combination of the coin and position space state of the form,

$$\begin{aligned} {|{\psi }\rangle }_0 = \left( \alpha {|{\uparrow }\rangle } + \beta {|{\downarrow }\rangle }\right) \otimes {|{x=0}\rangle } \quad ;\quad |\alpha |^2 + |\beta |^2 = 1. \end{aligned}$$
(1)

Here, \(\alpha \) and \(\beta \) are the amplitudes of the coin states. The evolution operator is defined by the action of a coin operator on the coin space, followed by the action of a coin state-dependent position shift operator on the entire system. The coin operator may be a U(2) matrix, but is mostly used in the single-parameter form,

$$\begin{aligned} C_\theta = \begin{bmatrix} ~~~\cos (\theta ) &{} -i\sin (\theta ) \\ -i\sin (\theta ) &{} ~~~\cos (\theta ) \end{bmatrix} \otimes \sum _x {|{x}\rangle } {\langle {x}|}. \end{aligned}$$
(2)

The shift operator shifts different components of the probability amplitude in different directions and is given by

$$\begin{aligned} S_x = \sum _{x \in {{\mathbb {Z}}}} \left[ {|{\uparrow }\rangle }{\langle {\uparrow }|} \otimes {|{x-1}\rangle } {\langle {x}|} + {|{\downarrow }\rangle }{\langle {\downarrow }|} \otimes {|{x+1}\rangle }{\langle {x}|} \right] . \end{aligned}$$
(3)

In general, the state of the walker after n steps of evolution is given as

$$\begin{aligned} {|{\psi }\rangle }_n = \left( S_x C_\theta \right) ^n {|{\psi }\rangle }_0. \end{aligned}$$
(4)

2.2 Directed discrete-time quantum walk algorithm

In the D-DTQW [72], the shift operator allows shifting in only one direction and can be written as the \(S_+\) or \(S_-\), depending on the direction in which evolution is directed towards. Thus, the D-DTQW shift operator is given by,

$$\begin{aligned} S_\pm = {\left\{ \begin{array}{ll} \sum _x {|{\uparrow }\rangle }{\langle {\uparrow }|} \otimes {|{x\pm 1}\rangle }{\langle {x}|} + {|{\downarrow }\rangle }{\langle {\downarrow }|} \otimes {|{x}\rangle }{\langle {x}|} &{} {\text {or}}, \\ \sum _x {|{\uparrow }\rangle }{\langle {\uparrow }|} \otimes {|{x}\rangle }{\langle {x}|} + {|{\downarrow }\rangle }{\langle {\downarrow }|} \otimes {|{x\pm 1}\rangle }{\langle {x}|}. \end{array}\right. } \end{aligned}$$
(5)

To construct an algorithm for ranking the nodes on a digraph, the D-DTQW operators used for defining the standard directed evolution need to be modified. The coin and position shift operators must be made dependent on the properties of the graph or network. Therefore, the redefined node-dependent coin operation takes the form,

$$\begin{aligned} C = \sum _x \begin{bmatrix} \sqrt{\frac{1}{\alpha _x+1}} &{} \sqrt{\frac{\alpha _x}{\alpha _x+1}} \\ \sqrt{\frac{\alpha _x}{\alpha _x+1}} &{} -\sqrt{\frac{1}{\alpha _x+1}} \end{bmatrix} \otimes {|{x}\rangle }{\langle {x}|}. \end{aligned}$$
(6)

Here, \(\alpha _x\) represents the proportion of the incoming weight compared to the total incoming and outgoing weights at the node represented by \({|{x}\rangle }\), i.e. \(\alpha _x = \frac{d_i}{d_i+d_o}\), where \(d_i\) is the indegree and \(d_o\) is the outdegree of node \({|{x}\rangle }\). It is trivial to verify that C is unitary. The shift operator takes the form,

$$\begin{aligned} S = \sum _x \left[ {|{\uparrow }\rangle }{\langle {\uparrow }|} \otimes {|{x}\rangle }{\langle {x}|} + \sum _k \left( {|{\downarrow }\rangle }{\langle {\downarrow }|} \otimes U_{kx} {|{k}\rangle }{\langle {x}|} \right) \right] . \end{aligned}$$
(7)

Here, the matrix U is unitary, so that S is also unitary. The algorithm is encoded directly into the operators as follows: The coin operator is defined at each node and essentially rotates the state depending on how much proportion of the data throughput at the particular node is incoming data. The incoming proportion is then ’stored’ in the \({|{\uparrow }\rangle }\) coin state, and the outgoing information is sent to all nodes \({|{k}\rangle }\) to which the node \({|{x}\rangle }\) is connected, in a proportion that is determined by the matrix U, which will be defined below.

For a directed graph, in general, the adjacency matrix A is not symmetric. Therefore, we transform A into a scattering matrix by considering the singular value decomposition of A as,

$$\begin{aligned} A = P\Lambda Q, \end{aligned}$$
(8)

where P and Q are the left and right singular eigenvectors of A. The matrix \(\Lambda \) is a diagonal matrix consisting of the singular values of A, which essentially contains information about how much information goes through each node, and in this sense, acts like a transfer matrix. The \(\Lambda \) is Hermitian and is converted into a unitary form as \(S = e^{i\Lambda }\). Since A was a square matrix, P, Q and S are all square matrices of the order of A. In addition, it may be verified that all the three matrices P, Q and S are unitary by themselves, and thus, the operator

$$\begin{aligned} U = P e^{i\Lambda } Q, \end{aligned}$$
(9)

will also be unitary. Physically, this makes the walk behave as if the \({|{\downarrow }\rangle }\) component of the probability amplitude is being scattered off each node and being redistributed among the directed edges. The coin operation defined here shifts some of the probability amplitude between the \({|{\uparrow }\rangle }\) and \({|{\downarrow }\rangle }\) states of the coin space. However, the amount of shift is dependent on the indegree of the particular node. If the relative importance of the node is high, it will tend to accumulate amplitude, while a node with lesser importance will tend to lose amplitude over multiple iterations of the walk.

So far, we have not mentioned anything about the weights of the edges connecting the nodes. In a more general case when the edges are weighted, the adjacency matrix A takes care of the weights as its definition changes, and so the shift operator is left unchanged. The coin operator is changed slightly so that the total weights of the incoming and outgoing edges are multiplied to the indegrees and outdegrees of each node,

$$\begin{aligned} \begin{aligned} C&= \sum _x \begin{bmatrix} \sqrt{\frac{1}{\alpha _x+1}} &{} \sqrt{\frac{\alpha _x}{\alpha _x+1}} \\ \sqrt{\frac{\alpha _x}{\alpha _x+1}} &{} -\sqrt{\frac{1}{\alpha _x+1}} \end{bmatrix} \otimes {|{x}\rangle }{\langle {x}|} \\ \text {where}\,\, \alpha _x&= \frac{\sum _j w_j e_{i_{j}}}{\sum _j w_j e_{i_{j}} + \sum _j w_j e_{o_{j}}}. \\ \end{aligned} \end{aligned}$$
(10)

Here, \(e_{i_{j}}\) represents the \(j\mathrm{th}\) incoming edge that has the weight \(w_j\). Similarly, \(e_{o_{j}}\) is the \(j\mathrm{th}\) outgoing edge with the corresponding weight \(w_j\).

2.3 Summary of algorithm

For any step at each node, the probability amplitude simultaneously evolves through connecting edges, and hence, the nodes with a higher weight of outgoing edges will end up having lower amplitudes on average. A summary of steps involved in our algorithm for ranking nodes in order of implementation is given below:

  1. 1.

    Initial state preparation: The initial state of the system is set to one of equal superposition, i.e. \({|{\psi }\rangle }_0 = \left( \frac{{|{\uparrow }\rangle } + {|{\downarrow }\rangle }}{\sqrt{2}} \right) \otimes \sum _{x=1}^{N} \frac{1}{\sqrt{N}} {|{x}\rangle } \).

  2. 2.

    Coin operation: The coin operation [Eq. (6)] is performed on the state.

  3. 3.

    Shift operation: The shift operation [Eq. (7)] is performed on the system.

  4. 4.

    Repetition and measurement:

    One step is defined as a single application of the coin operator followed by the shift operator. The system is initially allowed to run for 50 steps independent of network size so that the convergence of ranks hierarchy is seen. See appendix for our analysis on convergence of the quantum ranks. It is then probed for probability values after each step, reset, and run again for a higher number of steps. The normalized average of the probability values of each node gives its relative importance, considered to be the ’quantum rank’ of that node.

2.4 Physical realization

The mathematical framework of the unitary operator which describes the algorithm opens up questions on its physical realization. A given physical system may not allow a direct realization of all parts of unitary operators in the algorithm. However, physical realization of the unitary operators of the DTQW in the form of Hamiltonians has been explored in [73]. It requires us to find eigenvalues and eigenvectors of a large matrix which is an open problem at the moment. A hybrid quantum-classical approach has been suggested and demonstrated in [74]. Since the adjacency matrix of the network to be simulated is known a priori, its spectral decomposition can be obtained before creating the Hamiltonian for the physical system.

Unlike the standard DTQW implementation, the coin operator in this algorithm changes depending upon how the entire network is physically modelled. For example, in an implementation involving a system of photons travelling through waveguides, if the coin space is represented by the polarization (L. circular or R. circular) of the photons, the coin operator for each node may be realized by modifying the polarizations appropriately at each node of the network.

Before proceeding with the results of testing our algorithm on various networks, for the purpose of comparison we present below classical page rank algorithm and rank algorithm using Szegedy’s quantum walk.

3 Discussion and comparison with other algorithms

3.1 Classical page ranking algorithm

The classical PageRank is calculated by a power method. Consider a digraph \(\Gamma (V,E)\), with nodes described by the set V and edges by the set E. The adjacency matrix of \(\Gamma \) is denoted as A. We assume that the digraph \(\Gamma \) has N nodes, and thus, A is of size \(N\times N\).

The list of ranks of nodes is prepared in an initial state V given by

$$\begin{aligned} V = \frac{1}{N} \begin{bmatrix} 1\\ 1 \\ \vdots \\ 1 \end{bmatrix}. \end{aligned}$$
(11)

The Google matrix is defined as the column stochastic matrix G such that

$$\begin{aligned} G = (1-p)A + \frac{p}{N}B, \end{aligned}$$
(12)

where B is a square matrix of size N such that all its elements are 1 and p is a real number lying in [0, 1]. In this case, we have chosen \(p=0.85\).

The classical algorithm iteratively computes \(V^* = G^k V\) with \(k=1,2,3,...\). This may be expressed algorithmically as

  1. 1.

    Compute \(V^* = G^k\, V\),

  2. 2.

    Assign \(V = V^*\),

  3. 3.

    Go to 1.

At the point when the value of \(V^*\) is the same for \(k=k'\) and \(k=k'+1\), the program stops. At this point, the vector represented by \(V^*\) is an eigenvector of G, and the elements of \(V^*\) give the classical ranks for the nodes of the network.

An interesting way to look at this algorithm is its formulation as a random walk. We assign the importance of a node by the fraction of time a walker spends at that node while diffusing on a graph. Thus, if \(T_i\) is defined as the amount of time spent by the walker at a node, then

$$\begin{aligned} T_i = \sum _j G_{ij} \, T_j. \end{aligned}$$
(13)

In terms of a Markov chain formalism, this enables us to recast the Google matrix as representing the conditional probability linking one time step to another. Consider a sequence of random variables \(X^{(i)}\), where \(i=1,2,3,...\), one for each time step. Each random variable can take a value in the set of nodes \(\{n_i\}\) in the network. Thus, mathematically,

$$\begin{aligned} \begin{aligned}&P \left( n_i=X^{(n+1)} \right) = \sum _j G_{ij} P \left( n_j=X^{(n)} \right) , \\ \implies&G_{ij} = P \left( n_i = X^{(n+1)} | n_j = X^{(n)} \right) . \end{aligned} \end{aligned}$$
(14)

3.2 Algorithm based on Szegedy’s walk

Consider a Hilbert space that is defined as the span of all vectors that correspond to \(N \times N\) edges of a digraph \(\Gamma \), which has N nodes. Thus, the Hilbert space may be represented as,

$$\begin{aligned} {{\mathcal {H}}} = \text {span}\left\{ {|{x}\rangle }_1{|{y}\rangle }_2, \,\, x,y \in N\times N\right\} = {{\mathbb {C}}}^N \otimes {{\mathbb {C}}}^N. \end{aligned}$$
(15)

Now, define the vectors \({|{\psi _j}\rangle }\) in \({{\mathcal {H}}}\) as,

$$\begin{aligned} {|{\psi _j}\rangle } := {|{j}\rangle }_1 \otimes \sum _{k=1}^{N} \sqrt{G_{jk}} {|{k}\rangle }_2. \end{aligned}$$
(16)

where the subindices 1 and 2 represent the subspace of \({{\mathcal {H}}}\) to which the vector belongs. Eq. (16) represents a superposition of vectors representing outgoing edges from the node j.

It is easily verifiable that since G is stochastic, \({|{\psi }\rangle }_j\) are normalized. Thus, the operator \(\Pi = \sum _{j=1}^{N} {|{\psi }\rangle }_j{\langle {\psi }|}_j\) represents a projection onto the subspace generated by the vectors \({|{\psi }\rangle }_j\). A single step of Szegedy walk is then defined to be

$$\begin{aligned} U = S(2\Pi - \mathbb {1}), \end{aligned}$$
(17)

where S is the swap operator, that is,

$$\begin{aligned} S = \sum _{j,k=1}^{N} {|{j,k}\rangle } {\langle {k,j}|}. \end{aligned}$$
(18)

Each time a swap occurs, the edges are swapped, and hence, to maintain the directedness of the graph after each step, only an even number of steps must be taken. A simple approach to take care of this is to define a single step to be the application of the operator \(U^2\). A detailed description of the algorithm and the steps involved may be found in [69].

3.3 Comparison with our scheme

The classical algorithm is simply an eigenvalue-finding problem, and does not account for quantum interference at all. It is thus expected to give the incorrect results upon being used for quantum networks.

The key difference between our scheme and the one based on Szegedy’s walk is space complexity. Our scheme is based on a D-DTQW, which uses a Hilbert space of dimension 2N, as there is a N-node position space and a coin space of two dimensions at each node. The Szegedy walk requires a Hilbert space of dimension \(N^2\), as it requires two copies of the N-node position space and does not require a coin space. This additional resource requirement of a second position space makes physical realization unwieldy. In case of a D-DTQW, however, an internal degree of freedom of the walker can be used to model the coin Hilbert space.

4 Ranking nodes on various networks using D-DTQW

In this section, we present the results of testing our algorithm on various networks. We have compared the quantum ranks using D-DTQW with the classical ranks obtained by applying the Google PageRank algorithm [61,62,63,64,65,66] on different networks.

Fig. 1
figure 1

The seven-node random network used for testing the algorithm. This network is identical to the one used for presenting quantum PageRank in [67]

Full size image

In Fig. 1, we have shown a cyclic digraph network with seven nodes. This network is identical to the one used for presenting quantum PageRank algorithm based on quantization of Markov chains in [67]. In Table 1, the results obtained using classical ranking algorithm and D-DTQW algorithm after 500 steps are shown. Plot with the values at each node for the network is shown in Fig. 2. Though the corresponding values at each node are different for classical and quantum algorithms, the returned ranks are identical.

Table 1 Results of our scheme on the network shown in Fig. 1
Full size table
Fig. 2
figure 2

Quantum Ranks of a random seven-node network shown in Fig. 1 as calculated by the D-DTQW algorithm after 500 steps. As can be seen, the algorithm can identify various levels of the ranks. The order of the nodes within the levels may, however, be different, as visible here. For the case of this graph, the node with least classical importance is also the node with the least quantum rank

Full size image
Fig. 3
figure 3

The five-level binary tree network used for testing our algorithm

Full size image

We have simulated our algorithm on a tree network of different levels. An example of five-level binary tree network with 63 nodes is shown in Fig. 3. This algorithm gives very accurate results on this type of network model and demonstrates a very nice scalability as it identifies the levels extremely well. The quantum and classical ranks of the different levels are shown in Tables 2 and 3, and corresponding plots are shown in Figs. 4, and  5.

Table 2 Results of our scheme on the network shown in Fig. 3
Full size table
Table 3 Results of our scheme on a 5-level tree of branching ratio 3
Full size table
Fig. 4
figure 4

Quantum rank at each node on a five-level binary tree network. Quantum rank is consistent with the classical ranking and it efficiently identifies each level of the tree. As expected, the quantum ranks of the nodes in the same level are all equal

Full size image
Fig. 5
figure 5

Quantum ranks for a five-level tree with branching ratio 3. As with the binary tree, our algorithm is able to successfully discern different levels of this tree. The nodes on the same level have the same ranks, as expected

Full size image
Fig. 6
figure 6

The 32-node scale-free network used for testing

Full size image
Fig. 7
figure 7

Quantum ranks obtained by our algorithm on a 32-node scale-free network, plotted against the classical rankings. The network we have tested it on is shown in Fig. 6. While the highest ranked node in the quantum protocol is also the highest classically ranked node, the ranks of the intermediate nodes violate the classical orderings

Full size image

The scheme also gives reasonable output for scale-free networks. Testing was done on a 32-node network shown in Fig. 6, and the results are shown in Table 4 and Fig. 7. Even though the quantum ranks do not match the classical ones as exactly as in the case of directed tree networks, they still are able to correctly find the most important node, which, in this case, is node 3.

The algorithm is also able to successfully identify the classical nodes with relatively smaller importances, namely nodes 1, 2, 22, 5, 9 and 11. The quantum ranks of these nodes are different from their classical counterparts, and the classically expected hierarchy is also violated in this case due to quantum fluctuations.

To demonstrate scalability on a scale-free network, we have tested our algorithm on a 64-node scale-free network as shown in Fig. 8, and again, as for the 32-node network case, it violated the classical hierarchy to some extend as Fig. 9, but it identified the most important node to be the same as the classical case, i.e. node 3. It may be observed that at places where the classical ranks show only a very minuscule change, the quantum ranks have a more exaggerated result, highlighting the importance of the node. This can also be seen from Table 5.

Fig. 8
figure 8

The 64-node scale-free network used for testing

Full size image
Fig. 9
figure 9

Quantum ranks of a 64-node scale-free network. The network is shown in Fig. 8. As with the 32-node case, the classically highest ranked node is also the highest ranked node in the quantum protocol, but the milder fluctuations in classical ranks are enhanced in the quantum case, and the intermediate-ranked nodes again violate the classically determined hierarchy

Full size image
Fig. 10
figure 10

The 50-node GNC network used for testing

Full size image

The algorithm also performs well on other types of digraphs, such as growing networks with copying [75]. Figure 10 presents one such example. The results are shown in Fig. 11. Again, the most important nodes are the same as identified in the classical case, but the hierarchy is violated for other nodes of intermediate and low importances. The classical and quantum ranks for the top-ranked nodes are shown in Table 6. It can be seen that the order in this case was not violated for very important nodes.

Fig. 11
figure 11

Plot of the quantum and classical ranks of nodes in a 50-node GNC network, shown in Fig. 10. The quantum ranks in this case follow the classical ranks fairly closely and identify the highest ranked node very quickly. The quantum ranks of nodes of nearly similar importances show a violation of the classically determined order

Full size image

In our results, for all the networks we have chosen, we have run this algorithm for 500 iterations. However, we have found that the order of the nodes does not change after about 200 steps. Any number of steps done post this point only serves to reduce the standard deviation of the quantum rank of the node (See “Appendix”).

5 Conclusions

In this work, we have presented a new algorithm to generate a ranking of the nodes of a network by using a D-DTQW on a network. We use a scattering form of the shift operator, which is derived from the Google matrix used for the PageRank algorithm [40, 41, 61,62,63,64,65,66]. The Google matrix is derived from the adjacency matrix of the graph and therefore contains information inherent to the structure of the network within itself. We have shown the results obtained after iterating our algorithm on different networks, and the conclusions that we draw from them are as follows:

  1. 1.

    Directed tree networks :

    The D-DTQW algorithm is instantaneously able to figure out the root node; however, the instantaneous values of the quantum ranks for the nodes on larger network violate the expected classical hierarchy (from Google’s PageRank algorithm). This is expected as the violation arises as a consequence of quantum fluctuations in the system. Also, since quantum walks do not have steady-state solutions, the instantaneous ranks will never converge. The mean values of the quantum ranks, however, obey the classically expected hierarchy (See Appendix). The hierarchy within a particular level is not violated for this case. However, for networks used for quantum communication and quantum processing the hierarchy of nodes returned by the D-DTQW algorithm will be more relevant over the classical hierarchy. The D-DTQW dynamics takes into account all the quantum interference and fluctuations from the quantum dynamics in network.

    Table 4 Results of our scheme on the network shown in Fig. 6
    Full size table
    Table 5 Results of our scheme on the network shown in Fig. 8
    Full size table
    Table 6 Some of the ranks obtained from applying our scheme on the network shown in Fig.10
    Full size table
  2. 2.

    Other random networks:

    Our quantum algorithm also works well for scale-free networks, GNC networks and other random networks (the results are shown only for the scale-free and GNC digraphs in this work) identifies the well-connected (i.e. most important) nodes very quickly. The internal order of the hubs and the other nodes on the network may differ from what is classically expected, but the algorithm can separate the two types of nodes. As with the case of the trees, the instantaneous quantum ranks do not converge; however, the averaged values of these instantaneous ranks do. There are nodes, however, for which the averaged quantum ranks also violate the classically expected hierarchy. This deviation is due to quantum interference and fluctuations at the nodes of the network. Such kind of interference is not seen in acyclic networks and seems to only occur when some part of a probability is caught in a loop in the network.

From the results listed above, it is clear that our algorithm shows some non-trivial features that are also found in the classical PageRank algorithm. For non-trivial networks, some deviations of quantum rank from the classical rank highlight the role of quantum interference and quantum fluctuations. From this, we can say that the ranking of nodes for network with quantum and classical processing of information may not be identical and quantum scheme is very much required for analysis of architecture and network for quantum processes.

The quantum scheme, however, can be mapped to a dynamics on quantum systems, and the computation can be experimentally performed on it. This quantum algorithm can inspire applications in data sciences and other areas where there exists a need to generate a ranking of nodes and analyse the networks.