Optimization of quantum random walk simulations

Abstract

In computer science, an exponential performance gain is considered an importantachievement that can extend the set of practically computable problems. Behind the interest in quantum computation, there is the fact that several quantum algorithms have been shown toprovide exponential speedup against their classical counterparts. Of these, the most recent one,the one based on quantum random walks, is discussed in this work. The methods used indemonstrating the exponential algorithmic speedup by quantum random walks are analyzed indetail. This analysis comes after introductory parts where basic quantum computation concepts, quantum simulation techniques and quantum random walk ideas are discussed. Anew optimization technique on the implementation of quantum random walks is alsointroduced. This technique is based on the idea of manipulating the order in which theconstituent Hamiltonians are simulated for small durations in the iterative step of the simulation algorithm. Our approach can be generalized to optimize any quantum simulation inwhich the linear combination rule is used to simulate a collection of constituent Hamiltonians.