Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices

• URL: http://arxiv.org/abs/2410.04924v1
• Date: Mon, 7 Oct 2024 11:13:41 GMT
• Title: Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices
• Authors: Ningxiang Chen, Meng Li, Xiaoming Sun,
• Abstract summary: This paper examines the quantum walk search algorithm on complete multipartite graphs. We employ the coined quantum walk model and achieve quadratic speedup. We also provide the numerical simulation and circuit implementation of our quantum algorithm.
• Score: 7.922488341886121
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum walk is a potent technique for building quantum algorithms. This paper examines the quantum walk search algorithm on complete multipartite graphs with multiple marked vertices, which has not been explored before. Two specific cases of complete multipartite graphs are probed in this paper, and in both cases, each set consists of an equal number of vertices. We employ the coined quantum walk model and achieve quadratic speedup with a constant probability of finding a marked vertex. Furthermore, we investigate the robust quantum walk of two cases and demonstrate that even with an unknown number of marked vertices, it is still possible to achieve a quadratic speedup compared to classical algorithms and the success probability oscillates within a small range close to 1. This work addresses the overcooking problem in quantum walk search algorithms on some complete multipartite graphs. We also provide the numerical simulation and circuit implementation of our quantum algorithm.

Related papers

• Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk [0.8057006406834466]
  This paper presents a deterministic search algorithm on complete bipartite graphs. We address the most general case of multiple marked states, so there is a problem of estimating the number of marked states. We construct a quantum counting algorithm based on the spectrum structure of the search operator.
  arXiv  Detail & Related papers  (2024-04-02T05:09:33Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Quantum Counting on the Complete Bipartite Graph [0.0]
  Quantum counting is a key quantum algorithm that aims to determine the number of marked elements in a database. Since Grover's algorithm can be viewed as a quantum walk on a complete graph, a natural way to extend quantum counting is to use the evolution operator of quantum-walk-based search on non-complete graphs.
  arXiv  Detail & Related papers  (2023-11-17T09:22:28Z)
• Implementation of Continuous-Time Quantum Walks on Quantum Computers [0.0]
  Quantum walks are interesting candidates to be implemented on quantum computers. We describe efficient circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms on three graph classes.
  arXiv  Detail & Related papers  (2022-12-17T14:59:21Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions. For its practicability and wide-applicability, we give a brief review of typical graph learning techniques. We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
  arXiv  Detail & Related papers  (2022-02-19T02:56:47Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
  Existing quantum walk-based search algorithms suffer from the souffl'e problem. We present a new quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup.
  arXiv  Detail & Related papers  (2021-11-17T10:04:44Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Quantum walk-based search algorithms with multiple marked vertices [0.0]
  The quantum walk is a powerful tool to develop quantum algorithms. We extend previous analytical methods based on Szegedy's quantum walk. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.
  arXiv  Detail & Related papers  (2021-03-23T22:57:07Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
  arXiv  Detail & Related papers  (2020-12-28T18:04:16Z)

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.