Withdrawn: A Measurement-based Algorithm for Graph Colouring

• URL: http://arxiv.org/abs/2111.14390v3
• Date: Thu, 3 Mar 2022 07:20:48 GMT
• Title: Withdrawn: A Measurement-based Algorithm for Graph Colouring
• Authors: Michael Epping and Tobias Stollenwerk
• Abstract summary: In a previous version of this document we misinterpreted the runtime of a part of the described algorithm. We present a novel algorithmic approach to find a proper colouring of a graph with $d$ colours, if it exists.
• Score: 0.5482532589225553
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In a previous version of this document we misinterpreted the runtime of a part of the described algorithm. Indeed, the runtime is not better than the Grover-Algorithm. We therefor withdraw this work. We present a novel algorithmic approach to find a proper vertex colouring of a graph with $d$ colours, if it exists. We associate a $d$-dimensional quantum system with each vertex and the initial state is a mixture of all possible colourings, from which we obtain a random proper colouring of the graph by measurements. The non-deterministic nature of the quantum measurement is tackled by a reset operation, which can revert the effect of unwanted projections. As in the classical case, we find that the runtime scales exponentially with the number of vertices. However, we provide numerical evidence that the average runtime of the problem-specific part of the algorithm scales polynomially in the number of edges.

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)
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
  Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning and central for successful graph kernels and graph neural networks. We propose a framework for gradual neighborhood refinement, which allows a slower convergence to the stable coloring. Our approach is used to derive new variants of existing graph kernels and to approximate the graph edit distance via optimal assignments.
  arXiv  Detail & Related papers  (2022-09-19T14:37:35Z)
• 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)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics. We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
  arXiv  Detail & Related papers  (2021-12-08T08:23:37Z)
• Evolutionary Algorithm for Graph Coloring Problem [0.0]
  The graph coloring problem (GCP) is one of the most studied NP-HARD problems in computer science. In our paper, we start with the theoretical upper bound of chromatic number, that is, maximum out-degree + 1. In the process of evolution some of the colors are made unused to dynamically reduce the number of color in every generation.
  arXiv  Detail & Related papers  (2021-11-17T12:16:57Z)
• A Grover search-based algorithm for the list coloring problem [1.332560004325655]
  We propose a quantum algorithm based on Grover search to speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases where the lists and graphs considered are arbitrary in nature.
  arXiv  Detail & Related papers  (2021-08-20T08:41:22Z)
• 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)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner? Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.
  arXiv  Detail & Related papers  (2021-06-08T16:10:36Z)
• Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem [15.45783225341009]
  We study the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized searchs to recompute high quality solutions.
  arXiv  Detail & Related papers  (2021-05-26T13:00:31Z)
• 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)
• GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
  We propose a framework to generate adversarial examples in one of the most challenging black-box settings. Our framework is based on the observation that the decision boundary of deep networks usually has a small mean curvature in the vicinity of data samples.
  arXiv  Detail & Related papers  (2020-03-13T20:03:01Z)

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.