Abstract Quantum walk is the quantum version of classical random walk, which has shown great advantage over classical algorithms. In this article, main discoveries and breakthroughs along with several applications in the last two decades are reviewed and discussed. Reducing hitting time and diminishing mixing time, as two hot research fields, are addressed. Possibility of universal computation with more generic case of quantum walk is also mentioned. In the future, we can expect new methods and models being feasible ways to approach the theoretical lower bounds of related problems, as well as more efficient applications on specific scene.
Abstract Quantum walk is the quantum version of classical random walk, which has shown great advantage over classical algorithms. In this article, main discoveries and breakthroughs along with several applications in the last two decades are reviewed and discussed. Reducing hitting time and diminishing mixing time, as two hot research fields, are addressed. Possibility of universal computation with more generic case of quantum walk is also mentioned. In the future, we can expect new methods and models being feasible ways to approach the theoretical lower bounds of related problems, as well as more efficient applications on specific scene.
A random walk is known as a random process which describes a path including a succession of random steps in the mathematical space. It has increasingly been popular in various disciplines such as mathematics and computer science. Furthermore, in quantum mechanics, quantum walks can be regarded as quantum analogues of classical random walks. Classical random walks and quantum walks can be used to calculate the proximity between nodes and extract the topology in the network. Various random walk related models can be applied in different fields, which is of great significance to downstream tasks such as link prediction, recommendation, computer vision, semi-supervised learning, and network embedding. In this article, we aim to provide a comprehensive review of classical random walks and quantum walks. We first review the knowledge of classical random walks and quantum walks, including basic concepts and some typical algorithms. We also compare the algorithms based on quantum walks and classical random walks from the perspective of time complexity. Then we introduce their applications in the field of computer science. Finally we discuss the open issues from the perspectives of efficiency, main-memory volume, and computing time of existing algorithms. This study aims to contribute to this growing area of research by exploring random walks and quantum walks together.
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.
Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of research of quantum computation full of exciting open problems for physicists, computer scientists and engineers. In this paper we review theoretical advances on the foundations of both discrete- and continuous-time quantum walks, together with the role that randomness plays in quantum walks, the connections between the mathematical models of coined discrete quantum walks and continuous quantum walks, the quantumness of quantum walks, a summary of papers published on discrete quantum walks and entangle-ment as well as a succinct review of experimental proposals and realizations of discrete-time quantum walks. Furthermore, we have reviewed several algorithms based on both discrete- and continuous-time quantum walks as well as a most important result: the computational universality of both continuous- and discrete-time quantum walks.
This article aims to provide an introductory survey on quantum random walks. Starting from a physical effect to illustrate the main ideas we will introduce quantum random walks, review some of their properties and outline their striking differences to classical walks. We will touch upon both physical effects and computer science applications, introducing some of the main concepts and language of present day quantum information science in this context. We will mention recent developments in this new area and outline some open questions. 1. Overview Ever since the discovery of quantum mechanics people have been puzzled by the counter-intuitive character of the laws of nature. Over time we have learned to accept more and more effects that are unimaginable in a classical Newtonian world. Modern technology exploits quantum effects both to our benefit and detriment—among the memorable examples we should cite laser technology and not omit the atomic bomb. In recent years interest in quantum information theory has been generated by the prospect of employing its laws to design devices of surprising power [1]. New ideas include quantum cryptography [2, 3] and quantum computation. In 1994 Shor [4] discovered a quantum algorithm to factor numbers efficiently (that is in time that grows only polynomically with the length of the number to be factored). This has unleashed a wave of activity across a broad range of disciplines: physics, computer science, mathematics and engineering. This fruitful axis of research has uncovered many new effects that are strikingly different from their classical counterparts, both from the physical point of view as well as from a computer science and communication theory perspective. Over time these communities have gained a greater understanding of the concepts and notions of the other. The idea that information cannot be separated from
Quantum versions of random walks have diverse applications that are motivating experimental implementations as well as theoretical studies. However, the main impetus behind this interest is their use in quantum algorithms, which have always employed the quantum walk in the form of a program running on a quantum computer. Recent results showing that quantum walks are "universal for quantum computation" relate entirely to algorithms, and do not imply that a physical quantum walk could provide a new architecture for quantum computers. Nonetheless, quantum walks used to model transport phenomena in spin chains and biomolecules broaden their scope well beyond algorithms, and reopen the question of when a physical implementation might provide useful computational outputs. In this article we determine the conditions under which a physical quantum walk experiment could provide useful results beyond the reach of classical computation.
In the world of computational probing, random walks and quantum walks are two separate but tightly linked paradigms. Classical stochastic processes like random walks are based on the random movement of particles in mathematical space and have been extensively used in data mining, network analysis, computer vision, etc. Quantum walks, by contrast generalize random walks into the quantum realm, taking the benefit of the quantum superposition and interference in order to investigate multiple paths at the same time. Quantum walks provide significant potential for algorithmic development: in quantum computing and communication, and in Scientific modelling and simulation. This paper provides an in-depth survey of random walks and quantum walks, outlining historical context, fundamental principles, applications, challenges, and future prospects. In this paper, motivated by the abstractness of both random walks and quantum walks, we survey the field of computational exploration at large scales, coalescing the myriad notions and difficult challenges addressed by existing research efforts on random and quantum walks, inferring a nuanced and multifaceted view on how both random walks and quantum walks are involved in paving the way to future development in many fields.