Quantum algorithms with random walks

OData support
Dr. Friedl Katalin
Department of Computer Science and Information Theory

It is well known, that some classical algorithms can be accelerated by using randomization. One common method for this is the random walk. When the research of the quantum algorithms began to spread, it was obvious to study the application of the random walk in the quantum world. It was discovered, that this extension is possible, and an efficient search algorithm can be constructed using Markov chains. Compared to the classical approach, a quadric speed up can be achieved in the general cases.

This paper starts with explaining the basics of the quantum algorithms, highlighting the main differences between the classical and the quantum approaches. Furthermore, it presents some interesting properties of the quantum world. In particular the quantum teleportation, which allows the transmission of quantum states without a quantum channel, and the no-cloning theorem which states that a quantum state can not be copied.

The second chapter presents Grover's search algorithm. The original algorithm does not use random walk, but is can be shown, that is can be simulated with a quantum Markov chain without losing its efficiency. Although Grover's algorithm does not promise exponential speed ups, like Shor's famous algorithm for integer factorization, search can be found in many algorithms as subtask. Also the amplitude amplification, the generalization of Grover's algorithm, forms the basis of many quantum algorithms.

The third chapter briefly describes the classic random walk, and it's quantum extension. This is not trivial, because the quantum algorithms use the hidden parallelism in the quantum world. In the general cases, quadratic speed ups can be achieved, and in some special cases even exponential.

The fourth chapter shows a search algorithm designed by Frédéric Magniez, Ashwin Nayak, Jérémie Roland and Miklos Santha, based on the quantum Markov chains [1]. This algorithm uses a quantum operator based on a Markov chain, and an oracle. During the iterations is amplifies the amplitude of the marked elements, so at the end of the search we get a marked element, with a high probability. It can be shown, that this algorithm equivalent to the Grover-search.

The fifth chapter presents a data structure designed to simulate quantum circuits [2], used by the QuIDDPro program [3]. In the original paper, the proof of the complexity was not detailed, in the chapter I show a detailed, reasoning I developed.

In order to get a better understanding of the algorithm, I traced the workings of the algorithm with a small input. The sixth chapter show this with the help of the QuIDDPro program, which uses the QuIDD data structure, shown in the previous chapter. In order to do this, it wasn't sufficient to describe the operators in the usual way, I had to construct them from the basic building blocks. I chose the 3-SAT problem to do this, after describing the problem, I follow the algorithm step-by-step with a given 3-CNF.

[1] Magniez, F., Nayak, A., Roland, J., and Santha, M. Search via quantum walk, 2011, arXiv:quant-ph/0608026.

[2] Viamontes, G. F., Markov, I. L., and Hayes, J. P. Improving gate-level simulation of quantum circuits, 2003, arXiv:quant-ph/0309060v2.

[3] http://vlsicad.eecs.umich.edu/Quantum/qp/


Please sign in to download the files of this thesis.