Implementation of Continuous-Time Quantum Walk on Sparse Graph

Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing, especially for designing quantum algorithms. However, how to efficiently implement CTQWs is a challenging issue. In this paper, we study implementation of CTQWs on sparse graphs, i. e. , constructing efficient quantum circuits for implementing the unitary operator e^-iHt, where H= A (is a constant and A corresponds to the adjacency matrix of a graph). Our result is, for a d-sparse graph with N vertices and evolution time t, we can approximate e^-iHt by a quantum circuit with gate complexity (d³ \|H\| t N N) ^1+o (1), compared to the general Pauli decomposition, which scales like (\|H\| t N⁴ N) ^1+o (1). For sparse graphs, for instance, d=O (1), we obtain a noticeable improvement. Interestingly, our technique is related to graph decomposition. More specifically, we decompose the graph into a union of star graphs, and correspondingly, the Hamiltonian H can be represented as the sum of some Hamiltonians Hⱼ, where each e^-iHⱼt is a CTQW on a star graph which can be implemented efficiently.