Implementation of Continuous-Time Quantum Walk on Sparse Graph

Abstract

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={\hat{I}}^{3}A$ (${\hat{I}}^3$ 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^3\Vert H\Vert tN\log N{)}^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\Vert H\Vert t{N}^4\log 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_j$, where each $e^{-i{H}_{j}t}$ is a CTQW on a star graph which can be implemented efficiently.