Implementation of Continuous-Time Quantum Walk on Sparse Graph

• URL: http://arxiv.org/abs/2408.10553v1
• Date: Tue, 20 Aug 2024 05:20:55 GMT
• Title: Implementation of Continuous-Time Quantum Walk on Sparse Graph
• Authors: Zhaoyang Chen, Guanzhong Li, Lvzhou Li,
• Abstract summary: Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing. How to efficiently implement CTQWs is a challenging issue. In this paper, we study implementation of CTQWs on sparse graphs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
  We give an algorithm to perform pattern matching in quantum circuits for many patterns simultaneously. In the case of quantum circuits, we can express the bound obtained in terms of the maximum number of qubits.
  arXiv  Detail & Related papers  (2023-02-13T22:09:02Z)
• From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
  Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor $w$, where $w$ is the computer word size. We show that a simple bit-parallel algorithm on such restricted family of graphs can indeed be converted into a realistic quantum algorithm.
  arXiv  Detail & Related papers  (2023-02-06T15:14:34Z)
• Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice Gauge Theory [9.83302372715731]
  The Hamiltonian cycle (HC) problem in graph theory is a well-known NP-complete problem. We present an approach in terms of $mathbbZ$ lattice gauge theory defined on the lattice with the graph as its dual. For some random samples of small graphs, we demonstrate that the dependence of the average value of $g_c$ on $sqrtN_hc$, $N_hc$ being the number of HCs, and that of the average value of $frac1g_c$ on $N
  arXiv  Detail & Related papers  (2022-02-17T18:39:42Z)
• Robust Estimation for Random Graphs [47.07886511972046]
  We study the problem of robustly estimating the parameter $p$ of an ErdHos-R'enyi random graph on $n$ nodes. We give an inefficient algorithm with similar accuracy for all $gamma 1/2$, the information-theoretic limit.
  arXiv  Detail & Related papers  (2021-11-09T18:43:25Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs [6.305950347749109]
  We introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs.
  arXiv  Detail & Related papers  (2021-10-08T15:24:31Z)
• A framework for optimal quantum spatial search using alternating phase-walks [0.0]
  We generalise the Childs & Goldstone ($mathcalCG$) algorithm via alternating applications of marked-vertex phase shifts and continuous-time quantum walks. We demonstrate the effectiveness of the algorithm by applying it to obtain $mathcalO(sqrtN)$ search on a variety of graphs.
  arXiv  Detail & Related papers  (2021-09-29T11:16:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.