Implementation of Continuous-Time Quantum Walk on Sparse Graph
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912120738676736 |
|---|---|
| author | Chen, Zhaoyang Li, Guanzhong Li, Lvzhou |
| author_facet | Chen, Zhaoyang Li, Guanzhong Li, Lvzhou |
| contents | 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^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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10553 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Implementation of Continuous-Time Quantum Walk on Sparse Graph Chen, Zhaoyang Li, Guanzhong Li, Lvzhou Quantum Physics 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^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. |
| title | Implementation of Continuous-Time Quantum Walk on Sparse Graph |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2408.10553 |