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:1804.10560 · Physical Review A

Quantum walk search on Kronecker graphs

Thomas G. Wong, Konstantin Wünscher, Joshua Lockhart, Simone Severini B

Published Jul 31, 2018• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.98.012338

Related papers

Optimal quantum-walk search on Kronecker graphs with dominant or fixed regular initiators

Adam Glos, Thomas G. Wong

In network science, graphs obtained by taking the Kronecker or tensor power of the adjacency matrix of an initiator graph are used to construct complex networks. In this paper, we analytically prove sufficient conditions under which such Kronecker graphs can be searched by a continuous-time quantum walk in optimal $\mathrm{\ensuremath{\Theta}}\left(\sqrt{N}\right)$ time. First, if the initiator is regular and its adjacency matrix has a dominant principal eigenvalue, meaning its unique largest eigenvalue asymptotically dominates the other eigenvalues in magnitude, then the Kronecker graphs generated by this initiator can be quantum searched with probability 1 in $\ensuremath{\pi}\sqrt{N}/2$ time, asymptotically, and we give the critical jumping rate of the walk that enables this. Second, for any fixed initiator that is regular, nonbipartite, and connected, the Kronecker graphs generated by it are quantum searched in $\mathrm{\ensuremath{\Theta}}\left(\sqrt{N}\right)$ time. This greatly extends the number of Kronecker graphs on which quantum walks are known to optimally search. If the fixed, regular, connected initiator is bipartite, however, then search on its Kronecker powers is not optimal, but is still better than a classical computer's $O(N)$ runtime if the initiator has more than two vertices.

arXiv:1809.01249•Physical Review A•Dec 27, 2018•6 citations

Spatial Search by Nonlinear Quantum Walk

David A. Meyer, Thomas G. Wong

Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size $Θ(N)$, for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.

quant-pharXiv:2606.01403•Jun 2, 2026•0 citations

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

Joonas Malmi, Matteo A. C. Rossi, Guillermo García-Pérez +1 more

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.

arXiv:2205.02137•Physical Review Research•Dec 13, 2022•8 citations

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

Multimarked Spatial Search by Continuous-Time Quantum Walk

Pedro H. G. Lugão, Renato Portugal, Mohamed Sabri +1 more

The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is \(O(\sqrt {N})\) with an asymptotic probability of 1+ o (1), where N is the number of vertices.

arXiv:2203.14384•ACM Transactions on Quantum Computing•Nov 27, 2024•5 citations

On the quantum simulation of complex networks

Duarte Magano, João P. Moutinho, Bruno Coelho Coutinho

Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.

arXiv:2212.06126•SciPost Physics Core•Aug 24, 2023•6 citations
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.
In network science, graphs obtained by taking the Kronecker or tensor power of the adjacency matrix of an initiator graph are used to construct complex networks. In this paper, we analytically prove sufficient conditions under which such Kronecker graphs can be searched by a continuous-time quantum walk in optimal $\mathrm{\ensuremath{\Theta}}\left(\sqrt{N}\right)$ time. First, if the initiator is regular and its adjacency matrix has a dominant principal eigenvalue, meaning its unique largest eigenvalue asymptotically dominates the other eigenvalues in magnitude, then the Kronecker graphs generated by this initiator can be quantum searched with probability 1 in $\ensuremath{\pi}\sqrt{N}/2$ time, asymptotically, and we give the critical jumping rate of the walk that enables this. Second, for any fixed initiator that is regular, nonbipartite, and connected, the Kronecker graphs generated by it are quantum searched in $\mathrm{\ensuremath{\Theta}}\left(\sqrt{N}\right)$ time. This greatly extends the number of Kronecker graphs on which quantum walks are known to optimally search. If the fixed, regular, connected initiator is bipartite, however, then search on its Kronecker powers is not optimal, but is still better than a classical computer's O(N)O(N)O(N) runtime if the initiator has more than two vertices.
Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size Θ(N)Θ(N)Θ(N), for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.
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.
The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is O(N)O(\sqrt {N})O(N​) with an asymptotic probability of 1+ o (1), where N is the number of vertices.
Quantum walks provide a natural framework to approach graph problems with quantum computers, exhibiting speedups over their classical counterparts for tasks such as the search for marked nodes or the prediction of missing links. Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. It is known that such can be simulated efficiently if the underlying graph is row-sparse and efficiently row-computable. While this is sufficient for many applications, it limits the applicability for this class of algorithms to study real world complex networks, which, among other properties, are characterized by the existence of a few densely connected nodes, called hubs. In other words, complex networks are typically not row-sparse, even though the average connectivity over all nodes can be very small. In this work, we extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse. Hopefully, our results may lead to new applications of quantum computing to network science.