Searching Weighted Barbell Graphs with Laplacian and Adjacency Quantum Walks

• URL: http://arxiv.org/abs/2408.08244v2
• Date: Tue, 24 Sep 2024 16:18:53 GMT
• Title: Searching Weighted Barbell Graphs with Laplacian and Adjacency Quantum Walks
• Authors: Jonas Duda, Thomas G. Wong,
• Abstract summary: A quantum particle evolving by Schr"odinger's equation in discrete space constitutes a continuous-time quantum walk on a graph. We show that the Laplacian quantum walk's behavior does not change, no matter the weight of the bridge, and so the single bridge is too restrictive to affect the walk.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A quantum particle evolving by Schr\"odinger's equation in discrete space constitutes a continuous-time quantum walk on a graph of vertices and edges. When a vertex is marked by an oracle, the quantum walk effects a quantum search algorithm. Previous investigations of this quantum search algorithm on graphs with cliques have shown that the edges between the cliques can be weighted to enhance the movement of probability between the cliques to reach the marked vertex. In this paper, we explore the most restrictive form of this by analyzing search on a weighted barbell graph that consists of two cliques of the same size joined by a single weighted edge/bridge. This graph is generally irregular, so quantum walks governed by the graph Laplacian or by the adjacency matrix can differ. We show that the Laplacian quantum walk's behavior does not change, no matter the weight of the bridge, and so the single bridge is too restrictive to affect the walk. Similarly, the adjacency quantum walk's behavior is unchanged for most weights, but when the weight equals the size of a clique, the probability does collect at the clique containing the marked vertex, and utilizing a two-stage algorithm with different weights for each stage, the success probability is boosted from 0.5 to 0.996, independent of the size of the barbell graph.

Related papers

• Quantum Search with a Generalized Laplacian [0.0]
  A single excitation in a quantum spin network can effect a variety of continuous-time quantum walks on unweighted graphs.<n>We show that the Heisenberg model can effect these three quantum walks on signed weighted graphs.
  arXiv  Detail & Related papers  (2025-06-27T08:27:01Z)
• 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)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• 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)
• A vertical gate-defined double quantum dot in a strained germanium double quantum well [48.7576911714538]
  Gate-defined quantum dots in silicon-germanium heterostructures have become a compelling platform for quantum computation and simulation. We demonstrate the operation of a gate-defined vertical double quantum dot in a strained germanium double quantum well. We discuss challenges and opportunities and outline potential applications in quantum computing and quantum simulation.
  arXiv  Detail & Related papers  (2023-05-23T13:42:36Z)
• Walking on Vertices and Edges by Continuous-Time Quantum Walk [0.0]
  We define a version of the continuous-time quantum walk that allows the walker to hop from vertices to edges and vice versa. We analyze the spatial search algorithm on the complete bipartite graph by modifying the new version of the Hamiltonian.
  arXiv  Detail & Related papers  (2022-06-07T15:10:18Z)
• 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)
• 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)
• 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)
• Analysis of Lackadaisical Quantum Walks [0.0]
  The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each. We analytically prove that lackadaisical quantum walks can find a unique marked. vertebrae on any regular locally arc-transitive graph with constant success probability. quadratically faster than the hitting time.
  arXiv  Detail & Related papers  (2020-02-26T00:40:25Z)
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
  The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph. It can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph. We present a number of numerical simulations supporting this hypothesis.
  arXiv  Detail & Related papers  (2020-02-26T00:10:38Z)
• Discrete-Time Quantum Walks on Oriented Graphs [0.0]
  We define discrete-time quantum walks on arbitrary oriented graphs. We introduce a parameter, called alpha, that quantifies the amount of orientation.
  arXiv  Detail & Related papers  (2020-01-13T01:42:42Z)

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.