A quantum searching model finding one of the edges of a subgraph in a complete graph

• URL: http://arxiv.org/abs/2202.01464v2
• Date: Sun, 5 Jun 2022 03:35:41 GMT
• Title: A quantum searching model finding one of the edges of a subgraph in a complete graph
• Authors: Yusuke Yoshie and Kiyoto Yoshino
• Abstract summary: We construct a quantum searching model finding one of the edges of a given subgraph in a complete graph. We show that the model is valid for any subgraph, i.e., a complete graph.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Some of the quantum searching models have been given by perturbed quantum walks. Driving some perturbed quantum walks, we may quickly find one of the targets with high probability. In this paper, we construct a quantum searching model finding one of the edges of a given subgraph in a complete graph. How to construct our model is that we label the arcs by $+1$ or $-1$, and define a perturbed quantum walk by the sign function on the set of arcs. After that, we detect one of the edges labeled $-1$ by the induced sign function as fast as possible. This idea was firstly proposed by Segawa et al. in 2021. They only addressed the case where the subgraph forms a matching, and obtained by a combinatorial argument that the time of finding one of the edges of the subgraph is quadratically faster than a classical searching model. In this paper, we show that the model is valid for any subgraph, i.e., we obtain by spectral analysis a quadratic speed-up for finding one of the edges of the subgraph in a complete graph.

Related papers

• Quantum Search with the Signless Laplacian [0.0]
  We explore the signless Laplacian, which may arise in layered antiferromagnetic materials. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.
  arXiv  Detail & Related papers  (2025-01-28T18:18:01Z)
• Quantum Walk Search on Complete Multipartite Graph with Multiple Marked Vertices [7.922488341886121]
  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.
  arXiv  Detail & Related papers  (2024-10-07T11:13:41Z)
• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  This article presents a novel and succinct algorithmic framework via alternating quantum walks. It unifies quantum spatial search, state transfer and uniform sampling on a large class of graphs. The approach is easy to use since it has a succinct formalism that depends only on the depth of the Laplacian eigenvalue set of the graph.
  arXiv  Detail & Related papers  (2024-07-01T06:09:19Z)
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk. The same technique can be applied to other 1-dimensional hierarchical graphs.
  arXiv  Detail & Related papers  (2024-04-30T11:45:49Z)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  We propose a novel approach for designing deterministic quantum search algorithms on a variety of graphs via alternating quantum walks. Our approach is universal because it does not require an instance-specific analysis for different graphs.
  arXiv  Detail & Related papers  (2023-07-30T05:14:19Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• 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)
• Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach [49.25767340466445]
  We propose AnomRank, an online algorithm for anomaly detection in dynamic graphs. AnomRank uses a two-pronged approach defining two novel metrics for anomalousness. We show theoretically and experimentally that the two-pronged approach successfully detects two common types of anomalies.
  arXiv  Detail & Related papers  (2020-11-26T01:38:27Z)
• Quantum search of matching on signed graphs [0.0]
  We construct a quantum searching model of a signed edge driven by a quantum walk. Under an arbitrary edge coloring which gives a matching on a complete graph, we consider a quantum search of a colored edge from the edge set of a complete graph.
  arXiv  Detail & Related papers  (2020-07-13T09:36:08Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$. We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
  arXiv  Detail & Related papers  (2020-05-13T14:53:36Z)

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.