Implementation of a continuous-time quantum walk on a sparse graph
Physical Review A · 15.11.2024 · 110 (5)
DOI: 10.1103/physreva.110.052215 ↗Kurz gefasst
Fachartikel in der Zeitschrift Physical Review A, online erschienen am 15.11.2024. Verfasst von Zhaoyang Chen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 36 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Guangzhou Municipal Science and Technology Program key projects, Guangdong Provincial Quantum Science Strategic, Initiative.
Abstract (Originalsprache)
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.
Förderung
- National Natural Science Foundation of China
- Guangzhou Municipal Science and Technology Program key projects
- Guangdong Provincial Quantum Science Strategic, Initiative
- Innovation Program for Quantum Science and Technology
Zitieren
APA
Chen, Z., Li, G., & Li, L. (2024). Implementation of a continuous-time quantum walk on a sparse graph. Physical Review A, 110(5). https://doi.org/10.1103/physreva.110.052215
Vancouver
Chen Z, Li G, Li L. Implementation of a continuous-time quantum walk on a sparse graph. Physical Review A. 2024;110(5). doi:10.1103/physreva.110.052215
BibTeX
@article{Chen2024,
author = {Chen, Zhaoyang and Li, Guanzhong and Li, Lvzhou},
title = {Implementation of a continuous-time quantum walk on a sparse graph},
journal = {Physical Review A},
year = {2024},
volume = {110},
number = {5},
doi = {10.1103/physreva.110.052215}
}
EUVIMED