Related papers: Quantitative approach to Grover's quantum walk on graphs

Quantitative approach to Grover's quantum walk on graphs

URL: http://arxiv.org/abs/2207.01686v1
Date: Mon, 4 Jul 2022 19:33:06 GMT
Title: Quantitative approach to Grover's quantum walk on graphs
Authors: Gamal Mograby, Radhakrishnan Balu, Kasso A. Okoudjou and Alexander Teplyaev
Abstract summary: 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.
Score: 62.997667081978825
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: In this paper, we study Grover's search algorithm focusing on continuous-time quantum walk on graphs. We propose an alternative optimization approach to Grover's algorithm on graphs that can be summarized as follows: instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph Laplacians. As a result, we search for the most appropriate analytical structure on graphs endowed with fixed topologies yielding better search outcomes. We discuss strategies to investigate the optimality of Grover's algorithm and provide an example with an easy tunable graph Laplacian to investigate our ideas.

Related papers

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)
The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
The noisy version of the graph isomorphism problem aims to find a matching between the nodes of two graphs which preserves most of the edges. This thesis focuses on understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data.
arXiv Detail & Related papers (2024-04-18T15:31:13Z)
The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure [18.00833762891405]
Graph Lottery Ticket (GLT) Hypothesis: There is an extremely sparse backbone for every graph. We study 8 key metrics of interest that directly influence the performance of graph learning algorithms. We propose a straightforward and efficient algorithm for finding these GLTs in arbitrary graphs.
arXiv Detail & Related papers (2023-12-08T00:24:44Z)
Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search [31.68823192070739]
This work studies a central extremal graph theory problem inspired by a 1975 conjecture of ErdHos. It aims to find graphs with a given size (number of nodes) that maximize the number of edges without having 3- or 4-cycles.
arXiv Detail & Related papers (2023-11-06T22:29:55Z)
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)
A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
arXiv Detail & Related papers (2023-03-10T21:18:34Z)
Optimal Propagation for Graph Neural Networks [51.08426265813481]
We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
arXiv Detail & Related papers (2022-05-06T03:37:00Z)
Line Graph Neural Networks for Link Prediction [71.00689542259052]
We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
arXiv Detail & Related papers (2020-10-20T05:54:31Z)
Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
arXiv Detail & Related papers (2020-06-19T13:09:44Z)
Wasserstein-based Graph Alignment [56.84964475441094]
We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
arXiv Detail & Related papers (2020-03-12T22:31:59Z)

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