Quantum Spatial Search Algorithm on Random Temporal Networks
What if we lost in a very complex labyrinth and it changes its topology with time dynamically？ There is a Greek hero called Theseus searching for the Minotaur, this labyrinth puzzled Theseus so much. In order to help him to find the fastest way and get Minotaur, we can take advantage of the superposition principle giving rise to parallelism in quantum computers.
It was known to be affirmative that Theseus can find Minotaur in various regularity and symmetry of labyrinths. For the extremely disordered structure like Fig.1b is also discovered to be solvable by using quantum spatial search.
Erdös-Rényi model of random graph evolution
As we can see from the image above, the graph evolves to have more and more nodes tend to connect to each other, information transfer is possible. However, as the network gets more complex, the performance of bit transfer becomes essential. Therefore, the more complicated connection between various node communication, however, also makes the decision of which way should be the fastest harder.
Shown are three Erdös-Rényi networks with edge density
There is another graph showing as the number of nodes increases in a graph, the network becomes a spyder web. It also encounters a similar problem as the image above. The denser the node indicates the more complex the network.
This triggers a solution to optimally find the fastest path in the complex network by spatial search algorithm based on the continuous-time quantum walk (CTQW). However, this classical algorithm can only solve several regularities and symmetries of the complex graph, like some of the Erdös-Renyi random graphs. The graphs of n vertices where each edge exists with probability p is searched by CTQW is quite optimal for certain values of p (log n)3/2/n. For a more general solution, the quantum spatial search can be optimal for nearly all graphs, it means that the fraction of graphs of n vertices for which this holds to 1 in the asymptotic limit. This can be proven where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1.
In every node of a random network, high fidelity quantum communication can be established by quantum bit transfer and entanglement generation. This strongly enhances the highly disordered systems with optimal performance in quantum information.
Now let’s make the problem more complex, we have n nodes where each pair of them can connect only if a head is tossed by a biased coin. Image Minotaur is at one of the far ends of the node and has the power to decide when to toss the coin to connect pairs of nodes and eventually change the labyrinth structure. As discussed above, the probability above a certain value would offer the fastest way for Theseus to find Minotaur.
Let’s now put it another way, image Thesus has the power to replace the entire labyrinth at regular time intervals. At each time interval, Thesus can delete the connection of which pair of nodes on his will and connect the pair of nodes randomly by tossing the biased coin. Formally speaking, a network of n nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs G(n,p), where the probability is that any two given nodes are connected. After a time interval, a new GRaph will appear and replace the previous one.
Thus, this effectively generates a new labyrinth structure. While the number of nodes keeps constant, and Minotaur is still the one deciding how the nodes are connected or new random labyrinth overall. What advantage does Theseus has is that he can regenerate the labyrinth as frequently as he wants. For a given probability, the range of values of, the running time of the algorithm should be optimal even when the search on individual static graphs constituting the temporal network is subtemporal. There is a phenomenon in another way that the regimes of time intervals are suboptimal even when each of the node connections can be searched optimally. Therefore, the temporary and connectivity play an important role in algorithm performance.
From the graph, we observe that the average running time decrease gradually towards the optimal one after the time peak at =1, when the temporality coincides with the energy scale of the search Hamiltonian.
In reality, we emerge ourselves into a digital network, like Facebook, Google, the database gains or loses its links from time to time. The network becomes more and more complex. Some may expect that the quantum advantage will lose in such fragile scenarios. However, it is out of our expectation that quantum search algorithms still have the cutting edge for random networks over time. The temporal feature can act as a control for the full-speed performance of quantum computation, and this can be exploited for networked quantum communication. This shows that the sender and receiver do not require a direct link to communicate quantumly.