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=\gamma A$ ($\gamma$ 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.

References in corpus (9)

• Environment-Assisted Quantum Walks in Photosynthetic Energy Transfer
• Universal computation by quantum walk
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Spatial search by quantum walk
• Universal computation by multi-particle quantum walk
• Classical approach to the graph isomorphism problem using quantum walks
• Integrality Gaps for Random Integer Programs via Discrepancy
• Efficient quantum circuits for continuous-time quantum walks on composite graphs
• Optimal exact quantum algorithm for the promised element distinctness problem

Cited by in corpus (2)

• Scalable Structure For Chiral Quantum Routing
• Signatures of quantum chaos and complexity in the Ising model on random graphs