{
  "id": "2408.10553",
  "version": "v1",
  "published": "2024-08-20T05:20:55.000Z",
  "updated": "2024-08-20T05:20:55.000Z",
  "title": "Implementation of Continuous-Time Quantum Walk on Sparse Graph",
  "authors": [
    "Zhaoyang Chen",
    "Guanzhong Li",
    "Lvzhou Li"
  ],
  "categories": [
    "quant-ph"
  ],
  "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 \\|H\\| t N \\log N)^{1+o(1)}$, compared to the general Pauli decomposition, which scales like $(\\|H\\| 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^{-iH_jt}$ is a CTQW on a star graph which can be implemented efficiently.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-20T05:20:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "continuous-time quantum walk",
      "sparse graph",
      "star graph",
      "constructing efficient quantum circuits",
      "general pauli decomposition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}