Quantum walks are the quantum mechanical counterpart to classical random walks. Similarly to random walks, in quantum walks a walker moves on a graph structure from one node to another governed by some stochastic process. Unlike random walks, quantum walks exhibit quantum superposition. This allows the walker to be in multiple nodes simultaneously. Due to quantum superposition quantum walks have been applied to cryptography, optimization, graph theory and spatial search problems. The goal of a spatial search problem is to find a target node from a graph structure by moving from one node to another along the edges of the graph. On certain graph structures quantum walks are able to find the target node of the search faster than classical random walks. However, determining the speedup provided by the quantum walk can be difficult to do analytically, especially when there are multiple target nodes. Therefore, it is of importance to investigate numerical approaches for approximating the dynamics of quantum walks. This Bachelor's thesis concerns a heuristic method for analyzing the dynamics of discrete-time coined quantum walk (DTCQW) search algorithms used for finding a specific node or a set of nodes on a two-dimensional lattice graph. Instead of simulating the walk fully, the heuristic method uses the eigenvectors and eigenvalues of a unitary evolution operator that governs the walk dynamics to approximate the probability of the DTCQW search algorithm finding a node that is a target of the search. This work goes over two slightly different DTCQW search algorithms. One of these is a instance of the DTCQW search algorithm that has been investigated in previous literature (referred to as the standard DTCQW search algorithm). The other one is a slightly modified version of the standard DTCQW search algorithm (referred to as the modified DTCQW search algorithm) In this work, the method was first applied to the standard DTCQW search algorithm to compare the results to previously known analytical results. The goal of this was to showcase that by using the method one can arrive at similar results as with analytical approaches. In addition, the method was used to investigate the modified DTCQW search algorithm. This was done to give numerical showing that the modified DTCQW search algorithm is able to find certain target node formations with a higher probability than the standard DTCQW search algorithm. The results of this work show that the method can approximate the analytical results using only a couple of eigenvector-eigenvalue pairs of the unitary evolution operator. Therefore, it can be considered as a cost-efficient alternative for simulating the complete quantum walk. Using the method it can be seen that the modified search algorithm finds target nodes that are adjacent to each other in the graph structure with a high probability. Additionally, the results show that the modified search algorithm only has a small chance of finding target nodes that are not adjacent to other target nodes. This gives numerical showing that the modified search algorithm behaves differently from the standard search algorithm and could therefore be used for different applications.
Quantum walks are the quantum mechanical counterpart to classical random walks. Similarly to random walks, in quantum walks a walker moves on a graph structure from one node to another governed by some stochastic process. Unlike random walks, quantum walks exhibit quantum superposition. This allows the walker to be in multiple nodes simultaneously. Due to quantum superposition quantum walks have been applied to cryptography, optimization, graph theory and spatial search problems. The goal of a spatial search problem is to find a target node from a graph structure by moving from one node to another along the edges of the graph. On certain graph structures quantum walks are able to find the target node of the search faster than classical random walks. However, determining the speedup provided by the quantum walk can be difficult to do analytically, especially when there are multiple target nodes. Therefore, it is of importance to investigate numerical approaches for approximating the dynamics of quantum walks. This Bachelor's thesis concerns a heuristic method for analyzing the dynamics of discrete-time coined quantum walk (DTCQW) search algorithms used for finding a specific node or a set of nodes on a two-dimensional lattice graph. Instead of simulating the walk fully, the heuristic method uses the eigenvectors and eigenvalues of a unitary evolution operator that governs the walk dynamics to approximate the probability of the DTCQW search algorithm finding a node that is a target of the search. This work goes over two slightly different DTCQW search algorithms. One of these is a instance of the DTCQW search algorithm that has been investigated in previous literature (referred to as the standard DTCQW search algorithm). The other one is a slightly modified version of the standard DTCQW search algorithm (referred to as the modified DTCQW search algorithm) In this work, the method was first applied to the standard DTCQW search algorithm to compare the results to previously known analytical results. The goal of this was to showcase that by using the method one can arrive at similar results as with analytical approaches. In addition, the method was used to investigate the modified DTCQW search algorithm. This was done to give numerical showing that the modified DTCQW search algorithm is able to find certain target node formations with a higher probability than the standard DTCQW search algorithm. The results of this work show that the method can approximate the analytical results using only a couple of eigenvector-eigenvalue pairs of the unitary evolution operator. Therefore, it can be considered as a cost-efficient alternative for simulating the complete quantum walk. Using the method it can be seen that the modified search algorithm finds target nodes that are adjacent to each other in the graph structure with a high probability. Additionally, the results show that the modified search algorithm only has a small chance of finding target nodes that are not adjacent to other target nodes. This gives numerical showing that the modified search algorithm behaves differently from the standard search algorithm and could therefore be used for different applications.
Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification:
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.
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(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.
Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.
The field of quantum information applies the concepts of quantum physics to problems in computer science, and shows great potential for allowing efficient computation. \nIn this thesis I concentrate on a particular quantum information theoretic tool known as the quantum walk. There are two widely studied versions of the quantum walk, the continuous time walk, and the discrete time walk. The discrete time walk is particularly amenable to investigation using numerical methods, from which most of the results in this thesis are derived, and is the main focus of the work presented. Two aspects of the discrete time walk are investigated: their transport properties \nand their interpretation as quantum computers. I investigated the transport properties in two ways, by looking for a particular type of transport known as perfect \nstate transfer, and examining the transport properties of a new type of coin operator. \nThe search for perfect state transfer concentrated on modifications of small cycles. I found that perfect state transfer is rare for the choices of coin operators \ntested. The structures tested for perfect state transfer were based on cycles, and it appears that the type of modification has more of an effect than the size of the \ncycle. This makes intuitive sense, as the modifications found to lead to walks exhibiting perfect state transfer affected only the initial and target node of the cycle. \nI then investigated a new type of coin operator which does not allow amplitude to return to the node it has come from. This effectively simulates a dimer. Using the general form of this type of operator and random variables for each parameter, I found that the expected distance of the walker from the origin, and standard deviation, were independent of the initial condition. The second half of the thesis concentrates on computational applications of quantum \nwalks using the language acceptance model. I first note their equivalence to a type of quantum automaton known as the QFA-WOM, and this provides an intuitive understanding of the role of the WOM. I then use a more direct construction to show that they can accept a range of formal languages. Using this construction allows us to use superpositions of words as inputs, and the insights provided by investigating these suggest a new way of approaching the problem of quantum state discrimination.