Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2205.02137 · Physical Review Research

Spatial search by continuous-time quantum walks on renormalized Internet networks

Joonas Malmi, Matteo A. C. Rossi, Guillermo García-Pérez, Sabrina Maniscalco

Published Dec 13, 2022• 8 citations
arXivHTMLPDF

Abstract

We study spatial search with continuous-time quantum walks on real-world complex networks. We use smaller replicas of the Internet network obtained with a recent geometric renormalization method introduced by Garc\'{\i}a-P\'erez et al., Nat. Phys. 14, 583 (2018). This allows us to infer for the first time the behavior of a quantum spatial search algorithm on a real-world complex network. By simulating numerically the dynamics and optimizing the coupling parameter, we study the optimality of the algorithm and its scaling with the size of the network, showing that on average it is considerably better than the classical scaling $\mathcal{O}(N)$, but it does not reach the ideal quadratic speedup $\mathcal{O}(\sqrt{N})$ that can be achieved, e.g. in complete graphs. However, the performance of the search algorithm strongly depends on the degree of the nodes and, in fact, the scaling is found to be very close to optimal when we consider the nodes below the $99\mathrm{th}$ percentile ordered according to the degree.

DOI
10.1103/physrevresearch.4.043185

Related papers

Spatial search by continuous-time quantum walks on complex networks

Joonas Malmi

Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.

•Dec 8, 2020•0 citations

Quantum walk search on Kronecker graphs

Thomas G. Wong, Konstantin Wünscher, Joshua Lockhart +1 more

Kronecker graphs, obtained by repeatedly performing the Kronecker product of the adjacency matrix of an ``initiator'' graph with itself, have risen in popularity in network science due to their ability to generate complex networks with real-world properties. We explore spatial search by continuous-time quantum walk on Kronecker graphs. Specifically, we give analytical proofs for quantum search on first-, second-, and third-order Kronecker graphs with the complete graph as the initiator, showing that search takes Grover's $O(\sqrt{N})$ time. Numerical simulations indicate that higher-order Kronecker graphs with the complete initiator also support optimal quantum search.

arXiv:1804.10560•Physical Review A•Jul 31, 2018•14 citations

Continuous-time quantum-walk spatial search on the Bollobás scale-free network

Tomo Osada, Bruno Coelho Coutinho, Yasser Omar +3 more

The scale-free property emerges in various real-world networks and is an essential property that characterizes the dynamics or features of such networks. In this work, we investigate the effect of this scale-free property on a quantum information processing task of finding a marked node in the network, known as the quantum spatial search. We analyze the quantum spatial search algorithm using a continuous-time quantum walk on the Bollob\'as network, and we evaluate the time $T$ to localize the quantum walker on the marked node starting from an unbiased initial state. Our main finding is that $T$ is determined by the global structure around the marked node, while some local information of the marked node, such as the degree, does not identify $T$. We discuss this by examining the correlation between $T$ and some centrality measures of the network, and we show that the closeness centrality of the marked node is highly correlated with $T$. We also characterize the distribution of $T$ by marking different nodes in the network, which displays a multimode log-normal distribution. Especially on the Bollob\'as network, $T$ is a few orders of magnitude shorter depending on whether the marked node is adjacent to the largest degree hub node. However, as $T$ depends on the property of the marked node, one requires some amount of prior knowledge about such a property of the marked node in order to identify the optimal time to measure the quantum walker and achieve a fast search. These results indicate that the existence of the hub node in the scale-free network plays a crucial role in the quantum spatial search.

arXiv:1912.11243•Physical Review A•Feb 10, 2020•20 citations

Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk

Simon Apers, Shantanav Chakraborty, Leonardo Novo +1 more

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.

arXiv:2112.12746•Physical Review Letters•Oct 14, 2022•65 citations

Optimality of spatial search via continuous-time quantum walks

Shantanav Chakraborty, Leonardo Novo, Jérémie Roland

One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in $O(\sqrt{n})$ time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.

arXiv:2004.12686•Physical Review A•Sep 14, 2020•37 citations

Optimal Quantum Spatial Search on Random Temporal Networks

Shantanav Chakraborty, Leonardo Novo, Serena Di Giorgio +1 more

To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the spatial search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs G(n,p), where p is the probability that any two given nodes are connected: After every time interval τ, a new graph G(n,p) replaces the previous one. We prove analytically that, for any given p, there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O(sqrt[n]), even when search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal search on them. From this first study of quantum spatial search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.

arXiv:1701.04392•Physical Review Letters•Nov 28, 2017•49 citations
We study spatial search with continuous-time quantum walks on real-world complex networks. We use smaller replicas of the Internet network obtained with a recent geometric renormalization method introduced by Garc'{\i}a-P'erez et al., Nat. Phys. 14, 583 (2018). This allows us to infer for the first time the behavior of a quantum spatial search algorithm on a real-world complex network. By simulating numerically the dynamics and optimizing the coupling parameter, we study the optimality of the algorithm and its scaling with the size of the network, showing that on average it is considerably better than the classical scaling O(N)\mathcal{O}(N)O(N), but it does not reach the ideal quadratic speedup O(N)\mathcal{O}(\sqrt{N})O(N​) that can be achieved, e.g. in complete graphs. However, the performance of the search algorithm strongly depends on the degree of the nodes and, in fact, the scaling is found to be very close to optimal when we consider the nodes below the 99th99\mathrm{th}99th percentile ordered according to the degree.
Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.
Kronecker graphs, obtained by repeatedly performing the Kronecker product of the adjacency matrix of an ``initiator'' graph with itself, have risen in popularity in network science due to their ability to generate complex networks with real-world properties. We explore spatial search by continuous-time quantum walk on Kronecker graphs. Specifically, we give analytical proofs for quantum search on first-, second-, and third-order Kronecker graphs with the complete graph as the initiator, showing that search takes Grover's O(N)O(\sqrt{N})O(N​) time. Numerical simulations indicate that higher-order Kronecker graphs with the complete initiator also support optimal quantum search.
The scale-free property emerges in various real-world networks and is an essential property that characterizes the dynamics or features of such networks. In this work, we investigate the effect of this scale-free property on a quantum information processing task of finding a marked node in the network, known as the quantum spatial search. We analyze the quantum spatial search algorithm using a continuous-time quantum walk on the Bollob\'as network, and we evaluate the time TTT to localize the quantum walker on the marked node starting from an unbiased initial state. Our main finding is that TTT is determined by the global structure around the marked node, while some local information of the marked node, such as the degree, does not identify TTT. We discuss this by examining the correlation between TTT and some centrality measures of the network, and we show that the closeness centrality of the marked node is highly correlated with TTT. We also characterize the distribution of TTT by marking different nodes in the network, which displays a multimode log-normal distribution. Especially on the Bollob\'as network, TTT is a few orders of magnitude shorter depending on whether the marked node is adjacent to the largest degree hub node. However, as TTT depends on the property of the marked node, one requires some amount of prior knowledge about such a property of the marked node in order to identify the optimal time to measure the quantum walker and achieve a fast search. These results indicate that the existence of the hub node in the scale-free network plays a crucial role in the quantum spatial search.
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e^{-tH^{2}}|ψ⟩, which, for a given Hamiltonian H, only requires evolving H for time scaling as sqrt[t]. This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our Letter thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.
One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of nnn nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in O(n)O(\sqrt{n})O(n​) time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
To investigate the performance of quantum information tasks on networks whose topology changes in time, we study the spatial search algorithm by continuous time quantum walk to find a marked node on a random temporal network. We consider a network of n nodes constituted by a time-ordered sequence of Erdös-Rényi random graphs G(n,p), where p is the probability that any two given nodes are connected: After every time interval τ, a new graph G(n,p) replaces the previous one. We prove analytically that, for any given p, there is always a range of values of τ for which the running time of the algorithm is optimal, i.e., O(sqrt[n]), even when search on the individual static graphs constituting the temporal network is suboptimal. On the other hand, there are regimes of τ where the algorithm is suboptimal even when each of the underlying static graphs are sufficiently connected to perform optimal search on them. From this first study of quantum spatial search on a time-dependent network, it emerges that the nontrivial interplay between temporality and connectivity is key to the algorithmic performance. Moreover, our work can be extended to establish high-fidelity qubit transfer between any two nodes of the network. Overall, our findings show that one can exploit temporality to achieve optimal quantum information tasks on dynamical random networks.