Quantum walks are stochastic processes generated by a quantum evolution mechanism, allowing for speed-up in spreading and hitting-time performance with respect to their classical counterparts. Investigating the role of the memory effects for these models, we address the problem of finding the minimal linear system that exactly reproduces the evolution of the output distribution of a quantum walk. After adapting the classical approach to our setting, we investigate analytically and numerically the structural complexity of quantum walks, both in general and in particular examples. Lastly, we focus on Grover’s algorithm, a quantum computing search algorithm that can be re-framed as a quantum walk, showing that it allows for a dramatic reduction in its representation.
Quantum walks are stochastic processes generated by a quantum evolution mechanism, allowing for speed-up in spreading and hitting-time performance with respect to their classical counterparts. Investigating the role of the memory effects for these models, we address the problem of finding the minimal linear system that exactly reproduces the evolution of the output distribution of a quantum walk. After adapting the classical approach to our setting, we investigate analytically and numerically the structural complexity of quantum walks, both in general and in particular examples. Lastly, we focus on Grover’s algorithm, a quantum computing search algorithm that can be re-framed as a quantum walk, showing that it allows for a dramatic reduction in its representation.
In the first part of the thesis we construct a new, simple framework which amplifies to a constant the success probability of any abstract search algorithm. The total query complexity is given by the quantum hitting time of the resulting operator, which we show that it is of the same order as the quantum hitting time of the original algorithm. As a major application of our framework, we show that for any reversible walk P and a single marked state, the quantum walk corresponding to P can find the solution using a number of queries that is quadratically smaller than the classical hitting time of P. Our algorithm is more general and simpler to implement than the solution known previously in the literature (Krovi, Magniez, Ozols, and Roland, 2015), which was developed specifically for quantum walks; we also prove that, for the particular case of quantum walks, we can embed their algorithm into our framework, thus simulating it exactly. Finally, we show that we can implement amplitude amplification using our tool. In the second part of the thesis we give a new lower bound in the query model which proves that Grover's algorithm for unordered searching is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same an exact bound. We then turn our attention to non-adaptive algorithms for the same problem of searching an unordered set. In this model, we obtain a lower bound and we give an algorithm which matches the lower bound, thus showing that the lower bound is exactly optimal.
A general approach to obtain reduced models for a wide class of discrete-time quantum systems is proposed. The obtained models not only reproduce exactly the output of a given quantum model, but are also guaranteed to satisfy physical constraints, namely complete positivity and preservation of total probability. A fundamental framework for exact model reduction of quantum systems is constructed leveraging on algebraic methods, as well as novel results on quantum conditional expectations in finite-dimensions. The proposed reduction algorithm is illustrated and tested on prototypical examples, including the quantum walk realizing Grover’s algorithm.
Many quantum algorithms critically rely on quantum walk search, or the use of quantum walks to speed up search problems on graphs. However, the main results on quantum walk search are scattered over different, incomparable frameworks, such as the hitting time framework, the MNRS framework, and the electric network framework. As a consequence, a number of pieces are currently missing. For example, recent work by Ambainis et al. (STOC'20) shows how quantum walks starting from the stationary distribution can always find elements quadratically faster. In contrast, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. We present a new quantum walk search framework that unifies and strengthens these frameworks, leading to a number of new results. For example, the new framework effectively finds marked elements in the electric network setting. The new framework also allows to interpolate between the hitting time framework, minimizing the number of walk steps, and the MNRS framework, minimizing the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. In addition to quantum walks and phase estimation, our new algorithm makes use of quantum fast-forwarding, similar to the recent results by Ambainis et al. This perspective also enables us to derive more general complexity bounds on the quantum walk algorithms, e.g., based on Monte Carlo type bounds of the corresponding classical walk. As a final result, we show how in certain cases we can avoid the use of phase estimation and quantum fast-forwarding, answering an open question of Ambainis et al.
Mean squared displacement has been widely used as the primary metric for comparing quantum and classical random walks, with quantum walks showing quadratic scaling versus linear scaling for classical walks. However, this comparison may not capture the full picture: while the mean squared displacement is well suited for Gaussian distributions, quantum walk distributions exhibit distinctly non-Gaussian features. We propose that the mean hitting time offers a complementary perspective with clear operational meaning for search algorithms. Through analytical calculations, we show that quantum and classical walks yield identical MHT for symmetric initial conditions with two detectors, suggesting that the apparent quantum advantage seen in MSD comparisons may be context dependent. Interestingly, introducing stochastic resetting reveals more dynamics. We demonstrate analytically that quantum walks can achieve reduced MHT under stochastic reset through quasimomentum redistribution, while classical walks see no benefit. This quantum advantage naturally degrades with noise, and the quantum walk converges to classical behavior. We suggest that MHT reduction under stochastic reset can serve as an additional signature of quantum behavior, particularly useful for characterizing quantum walk implementations on noisy quantum devices. Our results indicate that different metrics can reveal different aspects of quantum-classical comparisons in walk-based algorithms.
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.
Random walks (or Markov chains) are models extensively used in theoretical computer science. Several tools, including analysis of quantities such as hitting and mixing times, are helpful for devising randomized algorithms. A notable example is Schöning's algorithm for the satisfiability (SAT) problem. In this work, we use the density-matrix formalism to define a quantum Markov chain model which directly generalizes classical walks, and we show that a common tools such as hitting times can be computed with a similar formula as the one found in the classical theory, which we then apply to known quantum settings such as Grover's algorithm.