Quantum computing is a new field of computer science that leverage the quan-tum properties of atomic and subatomic particles for solving computational tasks.However, quantum computing provides very little intuition on how it works. Thismakes the identification of computational tasks with a potential quantum speedupand the elaboration of quantum algorithms for said tasks very difficult. In this context,this thesis focuses on a quantum dynamical system called Discrete Time QuantumWalk (DTQW). DTQWs are dynamical systems with discrete time and space whichare inspired from random walks. This thesis focuses on the problem of searchingan element in an unstructured database. It is known in the literature that searchingpan element with a DTQW on a grid has a quasi-square-root (i.e. O( n poly-log n))complexity in the dataset size n. This provides a significant quantum speedup overthe linear complexity of classical brute-force or random walk based algorithms. A firstcontribution of this thesis shows that, when two elements are searched, the worst casecomplexity becomes quasi-linear while the average case complexity remains quasi-square-root. Moving on from grids to arbitrary topologies, a second contributionintroduces a new model of DTQW onto the edges of an arbitrary graph. This modelunique features are: (i) the position which is on the edges; (ii) a polarity on each edgethat generalizes the notion of right and left we have on a line. A third contributionintroduces a model of quantum distributed computing and shows how this model onan arbitrary graph can reproduce the dynamic of a DTQW on the same graph.
Quantum computing is a new field of computer science that leverage the quan-tum properties of atomic and subatomic particles for solving computational tasks.However, quantum computing provides very little intuition on how it works. Thismakes the identification of computational tasks with a potential quantum speedupand the elaboration of quantum algorithms for said tasks very difficult. In this context,this thesis focuses on a quantum dynamical system called Discrete Time QuantumWalk (DTQW). DTQWs are dynamical systems with discrete time and space whichare inspired from random walks. This thesis focuses on the problem of searchingan element in an unstructured database. It is known in the literature that searchingpan element with a DTQW on a grid has a quasi-square-root (i.e. O( n poly-log n))complexity in the dataset size n. This provides a significant quantum speedup overthe linear complexity of classical brute-force or random walk based algorithms. A firstcontribution of this thesis shows that, when two elements are searched, the worst casecomplexity becomes quasi-linear while the average case complexity remains quasi-square-root. Moving on from grids to arbitrary topologies, a second contributionintroduces a new model of DTQW onto the edges of an arbitrary graph. This modelunique features are: (i) the position which is on the edges; (ii) a polarity on each edgethat generalizes the notion of right and left we have on a line. A third contributionintroduces a model of quantum distributed computing and shows how this model onan arbitrary graph can reproduce the dynamic of a DTQW on the same graph.
Quantum computation is a new computational paradigm which can provide fundamentally faster computation than in the classical regime. This is dependent on finding efficient quantum algorithms for problems of practical interest. One of the most successful tools in developing new quantum algorithms is the quantum walk. In this thesis, we explore two applications of the discrete time quantum walk. In addition, we introduce an experimental scheme for generating cluster states, a universal resource for quantum computation. We give an explicit construction which provides a link between the circuit model of quantum computation, and a graph structure on which the discrete time quantum walk traverses, performing the same computation. We implement a universal gate set, proving the discrete time quantum walk is universal for quantum computation, thus confirming any quantum algorithm can be recast as a quantum walk algorithm. In addition, we study factors affecting the efficiency of the quantum walk search algorithm. Although there is a strong dependence on the spatial dimension of the structure being searched, we find secondary dependencies on other factors including the connectivity and disorder (symmetry). Fairly intuitively, as the connectivity increases, the efficiency of the algorithm increases, as the walker can coalesce on the marked state with higher probability in a quicker time. In addition, we find as disorder in the system increases, the algorithm can maintain the quantum speed up for a certain level of disorder before gradually reverting to the classical run time. Finally, we give an abstract scheme for generating cluster states. We see a linear scaling, better than many schemes, as doubling the size of the generating grid in our scheme produces a cluster state which is double the depth. Our scheme is able to create other interesting topologies of entangled states, including the unit cell for topological error correcting schemes.
The task of finding an entry in an unsorted list of N elements famously takes O(N) queries to an oracle for a classical computer and O(N) queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large N, the random walks converge to the same evolution, both taking Nln(1/ϵ) time to reach a success probability of 1−ϵ. In contrast, the discrete-time quantum walk asymptotically takes πN/22 timesteps to reach a success probability of 1/2, while the continuous-time quantum walk takes πN/2 time to reach a success probability of 1.
Quantum computing is a developing field that applies the properties of quantum mechanics to develop solutions to complex problems that the most powerful classical computers cannot solve or cannot solve efficiently. Solving difficult tasks requires sophisticated and efficient algorithms that can utilize stochastic processes as the primary techniques. The typical models of these stochastic processes include discrete-time random walks and continuous ones. Quantum walks represent a quantum extension of discrete random walks, whose demonstrated utility in algorithm design has motivated signi cant interest in quantum computational research. Therefore, the purpose of this thesis is to explore the potential of discrete-time coined quantum walks using the Python package with high-performance computing (HPC) compared to classical walks by conducting a literature review. To supplement this research, some simulations are implemented to analyze the spreading behavior of coined quantum walks, compare them with classical walks, and demonstrate their application in search tasks, such as binary hypercube search algorithm. These simulations aim to clarify the extent to which quantum walks can be effectively modeled and applied in computational contexts. The results gained show that coined quantum walks exhibit faster spreading than classical random walks, which contributes to a deeper understanding of potential applications of quantum walks, such as quantum simulation, in the future.
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.
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.
This paper explores the application of quantum walk algorithms to graph traversal and search problems. Classical algorithms often struggle with the computational complexity of traversing and searching large graphs, leading to significant time and resource limitations. Quantum walks, utilizing superposition and interference, offer a potential pathway to achieve exponential speedups. This work details the theoretical framework for applying quantum walks to graph problems, specifically focusing on traversal and search tasks. We present a generalized approach for mapping graph structures onto quantum walk systems and discuss the key mathematical formulations involved. The core of our investigation revolves around the construction of quantum walk operators that mimic the movement and interaction rules inherent in graph traversal. We analyze the evolution of the quantum walk state and derive expressions for the probability of reaching a specific node in the graph. Furthermore, we examine the impact of graph topology on the performance of the quantum walk, highlighting the potential for tailored algorithms to exploit specific graph structures. The results demonstrate the theoretical feasibility of quantum walk algorithms for significantly accelerating graph traversal and search operations, contributing to advancements in areas such as network analysis, database management, and artificial intelligence.