In this thesis we present a theoretical study of quantum walks, with a particular focus on the development of viable schemes concerned with their physical realization. Ever since their introduction over a decade ago, quantum walks have been extensively explored for their non-intuitive dynamics which may hold the key to a new generation of quantum algorithms. This growing interest in the theoretical applications of quantum walks has been paralleled by a flurry of research into a more practical problem: how does one physically implement a quantum walk in the laboratory? We begin this thesis by first presenting an overview of the quantum walk theory, including some of its algorithmic applications. This is then followed by a comprehensive survey of numerous proposals for a physical implementation of quantum walks, underpinned by a wide range of quantum, classical and hybrid technologies. This review consequently highlights what has so far remained a major challenge for the quantum walk enthusiasts; a physical realization that is experimentally viable whilst remaining readily scalable and not limited to problems with specific connectivity criteria. It is precisely this challenge that we seek to examine in the remaining parts of this thesis.
In this thesis we present a theoretical study of quantum walks, with a particular focus on the development of viable schemes concerned with their physical realization. Ever since their introduction over a decade ago, quantum walks have been extensively explored for their non-intuitive dynamics which may hold the key to a new generation of quantum algorithms. This growing interest in the theoretical applications of quantum walks has been paralleled by a flurry of research into a more practical problem: how does one physically implement a quantum walk in the laboratory? We begin this thesis by first presenting an overview of the quantum walk theory, including some of its algorithmic applications. This is then followed by a comprehensive survey of numerous proposals for a physical implementation of quantum walks, underpinned by a wide range of quantum, classical and hybrid technologies. This review consequently highlights what has so far remained a major challenge for the quantum walk enthusiasts; a physical realization that is experimentally viable whilst remaining readily scalable and not limited to problems with specific connectivity criteria. It is precisely this challenge that we seek to examine in the remaining parts of this thesis.
The classical random walk formalism plays an important role in a wide range of applications. Its quantum counterpart, the quantum walk, is proposed as an important theoretical model for quantum computing. By exploiting quantum effects such as superposition, interference, and entanglement, quantum walks and their variations have been extensively studied for achieving computing power beyond that of classical computing and have been broadly used in designing quantum algorithms for algebraic and optimization problems, graph and network analysis, and quantum Hamiltonian and biochemical process simulations. Moreover, quantum walk models have been proven capable of universal quantum computation. Unlike conventional quantum circuit models, quantum walks provide a feasible path for implementing application-specific quantum computing, particularly in the noisy intermediate-scale quantum era. Recently, remarkable progress has been achieved in implementing a wide variety of quantum walks and quantum walk applications, which demonstrates the great potential of quantum walks. In this review, we provide a thorough summary of quantum walks and quantum walk computing, including theories and characteristics, physical implementations, and applications. We also discuss the challenges facing quantum walk computing, which aims to realize a practical quantum computer in the near future.
Over the last two decades quantum walks have proven to be a very useful concept in quantum information processing, quantum communication and quantum simulations. The presented thesis reviews our contribution to this field of research. We provide a thorough introduction to methods used for the study of quantum walks and their potential applications. To keep the presentation intelligible we focus on specific examples. In particular, we analyze in detail the properties of homogeneous quantum walks on a one-dimensional lattice with two and three internal states. The application of the obtained results is illustrated on the examples persistence of unvisited sites and quantum transport to an absorbing sink. We also discuss quantum walks on finite graphs and their applications to quantum search and perfect state transfer. Extension of the presented results, which can be found in enclosed published papers, is discussed in detail.
This paper explores the application of quantum walk algorithms to a variety of optimization problems. Traditional optimization algorithms often struggle with complex landscapes and high dimensionality, leading to computational bottlenecks. Quantum walks, leveraging quantum superposition and interference, offer a fundamentally different approach that can potentially overcome these limitations. We present a framework for designing quantum walk algorithms specifically for optimization, focusing on key aspects such as step selection, boundary conditions, and measurement strategies. The core of our approach lies in adapting the inherent parallelism of quantum walks to efficiently explore the solution space. We demonstrate the theoretical potential of this approach through examples and outline future research directions. The algorithms presented aim to significantly improve the speed and accuracy of solving various optimization problems. The core claim is that quantum walks provide a novel approach to search and optimization. The core mechanism involves developing tailored quantum walk algorithms, capitalizing on their parallel exploration capabilities. This research expands the applicability of quantum walk theory beyond its established use cases.
The quantum walk is a method for conceptualizing and designing quantum computing algorithms and it comes in two forms: the continuous-time and discrete-time quantum walk. The thesis is organized into three parts, each of which looks to develop the concept and uses of the quantum walk. The first part is the theory of the quantum walk. This includes definitions and considerations for the various incarnations of the discrete-time quantum walk and a discussion on the general method for connecting the continuous-time and discrete-time versions. As a result, it is shown that most versions of the discrete-time quantum walk can be put into a general form and this can be used to simulate any continuous-time quantum walk. The second part uses these results for a hypothetical application. The application presented is a search algorithm that appears to scale in the time for completion independent of the size of the search space. This behavior is then elaborated upon and shown to have general qualitative agreement with simulations to within the approximations that are made. The third part introduces a method of implementation. Given a universal quantum computer, the method is discussed and shown to simulate an arbitrary discrete-time quantum walk. Some of the benefits of this method are that half the unitary evolution can be achieved without the use of any gates and there may be some possibility for error detection. The three parts combined suggest a possible experiment, given a quantum computing scheme of sufficient robustness.
Quantum random walks have received much interest due to their nonintuitive dynamics, which may hold the key to a new generation of quantum algorithms. What remains a major challenge is a physical realization that is experimentally viable and not limited to special connectivity criteria. We present a scheme for walking on arbitrarily complex graphs, which can be realized using a variety of quantum systems such as a Bose-Einstein condensate trapped inside an optical lattice. This scheme is particularly elegant since the walker is not required to physically step between the nodes; only flipping coins is sufficient.
Quantum machine learning combines quantum computing with machine learning to solve complex computational problems more efficiently than classical approaches. This survey provides an introduction to the foundations, algorithms, frameworks, data and applications of quantum machine learning, serving as a resource for researchers and practitioners. We begin by reviewing existing surveys to identify gaps that this work addresses, followed by a detailed discussion of the foundational principles of quantum mechanics and machine learning essential for quantum machine learning. Key algorithms are examined, highlighting their mechanisms, advantages, and applications across various domains. Current frameworks and platforms for implementing quantum machine learning algorithms are explored, emphasizing their unique features and suitability for different contexts. Existing quantum datasets for practical usage are also reported and commented on. This survey also reviews over 135 articles, categorized into theoretical and practical contributions, to identify key advances, limitations, and application areas within quantum machine learning. Critical challenges such as hardware limitations, error rates, and scalability are analyzed to detect the obstacles that must be addressed for practical deployment. By synthesizing these elements into a structured overview, this survey aims at serving as both an introduction and a guide for advancing research and development in this disruptive field.