Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that are based on block encoding and quantum singular value transformation techniques. Block encoding allows us to embed a properly scaled matrix A of interest in a larger unitary transformation U that can be carried out efficiently on a quantum computer once U is decomposed into a product of simpler unitaries. Such a decomposition yields a quantum circuit consisting of quantum gates that can be implemented and assembled on a quantum computer. Quantum singular value transformation allows us to block encode polynomials of A and express these block encodings in terms of block encodings of A. Although this approach can potentially achieve exponential speedup in solving linear algebra problems on a quantum computer (compared to the best algorithm used on a classical computer), such gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of A, which is difficult in general, and non-trivial even for well structured sparse matrices. In this talk, I will give some examples on how efficient quantum circuits can be constructed for some well structured sparse matrices, and discuss a few strategies used in these constructions. Of particular interest are sparse stochastic matrices that correspond to random walks on a graph. I will show how the block encoding of a particular type of random walk can be efficiently implemented to yield an efficient quantum walk.
Copyright. All Rights Reserved.