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 log N)¹⁺ᵒ⁽¹⁾, compared to the general Pauli decomposition, which scales like (\|H\| t N⁴ log N)¹⁺ᵒ⁽¹⁾. 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.