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

Spatial search by continuous-time quantum walks on complex networks

Joonas Malmi

Published Dec 8, 2020• 0 citations
OpenAlex

Abstract

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.

Related papers

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

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

Spatial search on Johnson graphs by discrete-time quantum walk

Hajime Tanaka, Mohamed Sabri, Renato Portugal

Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.

arXiv:2112.03744•Journal of Physics A Mathematical and Theoretical•May 12, 2022•9 citations

Quantum spatial search with multiple excitations

Lewis, Dylan, Leonardo Banchi, Sougato Bose

Spatial search is the problem of finding a marked vertex in a graph. A continuous-time quantum walk in the single-excitation subspace of an $n$ spin system solves the problem of spatial search by finding the marked vertex in $O(\sqrt{n})$ time. Here, we investigate a natural extension of the spatial search problem, marking multiple vertices of a graph, which are still marked with local fields. We prove that a continuous-time quantum walk in the $k$-excitation subspace of $n$ spins can determine the binary string of $k$ marked vertices with an asymptotic fidelity in time $O(\sqrt{n})$, despite the size of the state space growing as $O(n^k)$. Numerically, we show that this algorithm can be implemented with interactions that decay as $1/r^α$, where $r$ is the distance between spins, and an $α$ that is readily available in current ion trap systems.

arXiv:2410.05945•Oct 8, 2024•0 citations

Spatial search via non-linear quantum walk

Mahdi Ebrahimi Kahou

One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.

•Jan 1, 2013•1 citation

Engineering the success of quantum walk search using weighted graphs

Thomas G. Wong, Pascal Philipp

Continuous-time quantum walks are natural tools for spatial search, where one searches for a marked vertex in a graph. Sometimes the structure of the graph causes the walker to get trapped, such that the probability of finding the marked vertex is limited. We give an example with two linked cliques, proving that the captive probability can be liberated by increasing the weights of the links. This allows the search to succeed with probability 1 without increasing the energy scaling of the algorithm. Further increasing the weights, however, slows the runtime, so the optimal search requires weights that are neither too weak nor too strong.

arXiv:1605.04862•Physical Review A•Aug 4, 2016•12 citations
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.
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.
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.
Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.
Spatial search is the problem of finding a marked vertex in a graph. A continuous-time quantum walk in the single-excitation subspace of an nnn spin system solves the problem of spatial search by finding the marked vertex in O(n)O(\sqrt{n})O(n​) time. Here, we investigate a natural extension of the spatial search problem, marking multiple vertices of a graph, which are still marked with local fields. We prove that a continuous-time quantum walk in the kkk-excitation subspace of nnn spins can determine the binary string of kkk marked vertices with an asymptotic fidelity in time O(n)O(\sqrt{n})O(n​), despite the size of the state space growing as O(nk)O(n^k)O(nk). Numerically, we show that this algorithm can be implemented with interactions that decay as 1/rα1/r^α1/rα, where rrr is the distance between spins, and an ααα that is readily available in current ion trap systems.
One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.
Continuous-time quantum walks are natural tools for spatial search, where one searches for a marked vertex in a graph. Sometimes the structure of the graph causes the walker to get trapped, such that the probability of finding the marked vertex is limited. We give an example with two linked cliques, proving that the captive probability can be liberated by increasing the weights of the links. This allows the search to succeed with probability 1 without increasing the energy scaling of the algorithm. Further increasing the weights, however, slows the runtime, so the optimal search requires weights that are neither too weak nor too strong.