Quantum Algorithms for Graph and Algebra Problems

Quantum computing is an exciting new area between computerscience and quantum physics. The computation is based on quantummechanics. Quantum computing has the potential to demonstrate thatfor some problems quantum computation is more efficient thanclassical computation. Sebastian Dörn presents new quantumalgorithms for basic problems from graph and algebra theory. Firstof all, he introduces several quantum search procedures, likeGrover search and quantum walks. Then he presents an overview ofrecent quantum graph algorithms, for example shortest path andmaximum flow algorithms. In the main part of this book, SebastianDörn gives new quantum algorithms for matching problems, graphtraversal problems and independent set problems. Furthermorequantum complexity bounds for group testing problems and forproblems from linear algebra are presented. All quantum algorithmsare faster than the best known classical algorithms for thecorresponding problems. This book willbe of interest to graduatestudents and researchers in physics, computer science andmathematics with an interest in quantum computing, and may be usedin courses on quantum algorithms.