Related papers: Application of graph theory in quantum computer science

Application of graph theory in quantum computer science

URL: http://arxiv.org/abs/2109.12978v1
Date: Mon, 27 Sep 2021 12:07:25 GMT
Title: Application of graph theory in quantum computer science
Authors: Adam Glos
Abstract summary: We demonstrate that the continuous-time quantum walk models remain powerful for nontrivial graph structures. The quantum spatial search defined through CTQW has been proven to work well on various undirected graphs. In the scope of this aspect we analyze, whether quantum speed-up is observed for complicated graph structures as well.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this dissertation we demonstrate that the continuous-time quantum walk models remain powerful for nontrivial graph structures. We consider two aspects of this problem. First, it is known that the standard Continuous-Time Quantum Walk (CTQW), proposed by Childs and Goldstone, can propagate quickly on the infinite path graph. However, the Schr\"odinger equation requires the Hamiltonian to be symmetric, and thus only undirected graphs can be implemented. In this thesis, we address the question, whether it is possible to construct a continuous-time quantum walk on general directed graphs, preserving its propagation properties. Secondly, the quantum spatial search defined through CTQW has been proven to work well on various undirected graphs. However, most of these graphs have very simple structures. The most advanced results concerned the Erd\H{o}s-R\'enyi model of random graphs, which is the most popular but not realistic random graph model, and Barab\'asi-Albert random graphs, for which full quadratic speed-up was not confirmed. In the scope of this aspect we analyze, whether quantum speed-up is observed for complicated graph structures as well.

Related papers

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)
Exponential speedups for quantum walks in random hierarchical graphs [8.984888893275713]
We show how to generalize the use of quantum walks to a class of hierarchical graphs. The hitting times of quantum walks on these graphs are related to the localization properties of zero modes in certain disordered tight binding Hamiltonians.
arXiv Detail & Related papers (2023-07-27T17:59:58Z)
Graph Generation with Diffusion Mixture [57.78958552860948]
Generation of graphs is a major challenge for real-world tasks that require understanding the complex nature of their non-Euclidean structures. We propose a generative framework that models the topology of graphs by explicitly learning the final graph structures of the diffusion process.
arXiv Detail & Related papers (2023-02-07T17:07:46Z)
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)
Non-separable Spatio-temporal Graph Kernels via SPDEs [90.62347738138594]
We provide graph kernels for principled-temporal modelling on graphs. By providing novel tools for modelling on graphs, we outperform pre-existing graph kernels in real-world applications.
arXiv Detail & Related papers (2021-11-16T14:53:19Z)
Perfect State Transfer in Weighted Cubelike Graphs [0.0]
A continuous-time quantum random walk describes the motion of a quantum mechanical particle on a graph. We generalize the PST or periodicity of cubelike graphs to that of weighted cubelike graphs.
arXiv Detail & Related papers (2021-09-26T13:44:44Z)
Simplifying Continuous-Time Quantum Walks on Dynamic Graphs [0.0]
A continuous-time quantum walk on a dynamic graph evolves by Schr"odinger's equation with a sequence of Hamiltonians encoding the edges of the graph. In this paper, we give six scenarios under which a dynamic graph can be simplified.
arXiv Detail & Related papers (2021-06-10T19:24:32Z)
How to Teach a Quantum Computer a Probability Distribution [0.0]
We explore teaching a coined discrete time quantum walk on a regular graph a probability distribution. We also discuss some hardware and software concerns as well as immediate applications and the several connections to machine learning.
arXiv Detail & Related papers (2021-04-15T02:41:27Z)
Graph and graphon neural network stability [122.06927400759021]
Graph networks (GNNs) are learning architectures that rely on knowledge of the graph structure to generate meaningful representations of network data. We analyze GNN stability using kernel objects called graphons.
arXiv Detail & Related papers (2020-10-23T16:55:56Z)
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)
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)

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