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

• Toward Minimum Graphic Parity Networks [9.459397370755115]
  A graphic parity network for a graph $G$ is a quantum circuit composed solely of CNOT gates.<n>We show that a graphic parity network for a connected graph with $n$ vertices and $m$ edges requires at least $m+n-1$ gates.<n>We conjecture that all such graphs belong to a newly defined graph class.
  arXiv  Detail & Related papers  (2025-09-12T09:00:38Z)
• Graph Random Features for Scalable Gaussian Processes [52.89901965157282]
  We study the application of graph random features (GRFs) to scalable Gaussian processes on discrete input spaces.<n>We prove that (under mild assumptions) Bayesian inference with GRFs enjoys $O(N3/2)$ time complexity with respect to the number of nodes $N$, compared to $O(N3)$ for exact kernels.
  arXiv  Detail & Related papers  (2025-09-03T20:13:23Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits [20.069035622098905]
  We focus on the Hamming-Weight-preserving states, defined as $psi_textHr = sum_textHW(x)=k alpha_x |xrangle$, which have leveraged their strength in quantum machine learning.<n>We propose an algorithm to build the preparation circuit of $O(log n)$-depth with $O(m)$ ancillary qubits.<n>Specifically for the $n$-qubit tree-structured and grid-structured states, the number of ancillary qubits in the corresponding preparation circuits
  arXiv  Detail & Related papers  (2025-08-20T06:50:13Z)
• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices. We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Quantum phase discrimination with applications to quantum search on graphs [0.0]
  We propose a quantum algorithm named it quantum phase discrimination(QPD) for this task. By using QPD, we reduce the query complexity of a path-finding algorithm proposed by Li and Zur. We present two applications to quantum search on graphs.
  arXiv  Detail & Related papers  (2025-04-21T16:06:43Z)
• 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)
• The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
  Graph Neural Network (GNN) whose output is identical to the graph function? In this paper, we fully answer this question and characterize the class of graph problems that can be represented by GNNs. We show that this condition can be efficiently verified by checking quadratically many constraints.
  arXiv  Detail & Related papers  (2022-02-17T18:54:27Z)
• 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.