Related papers: Quantum search of matching on signed graphs

Quantum search of matching on signed graphs

URL: http://arxiv.org/abs/2007.07223v1
Date: Mon, 13 Jul 2020 09:36:08 GMT
Title: Quantum search of matching on signed graphs
Authors: Etsuo Segawa, Yusuke Yoshie
Abstract summary: 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.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We construct a quantum searching model of a signed edge driven by a quantum walk. The time evolution operator of this quantum walk provides a weighted adjacency matrix induced by the assignment of sign to each edge. This sign can be regarded as so called the edge coloring. Then as an application, 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. We show that this quantum walk finds a colored edge within the time complexity of $O(n^{\frac{2-\alpha}{2}})$ with probability $1-o(1)$ while the corresponding random walk on the line graph finds them within the time complexity of $O(n^{2-\alpha})$ if we set the number of the edges of the matching by $O(n^{\alpha})$ for $0 \le \alpha \le 1$.

Related papers

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)
Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits [24.592554830963966]
A graph is navigable if we can successfully move from any starting node to any target node. The important question for applications is if sparser graphs can be constructed. We give a simple and efficient way to construct a navigable graph with average degree $O(sqrtn log n )$ for any set of $n$ points, in any dimension, for any distance function.
arXiv Detail & Related papers (2024-05-29T01:07:26Z)
Quantum search by continuous-time quantum walk on t-designs [0.0]
This work examines the time complexity of quantum search algorithms on $t$-designs with multiple marked elements using the continuous-time quantum walk. We identify a subset of bipartite graphs that are conducive to success compared to random-walk-based search algorithms.
arXiv Detail & Related papers (2023-10-22T00:37:52Z)
Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $epsilon$ in Wasserstein-1 distance. No algorithm can compute an $epsilon$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability.
arXiv Detail & Related papers (2023-07-02T05:03:38Z)
Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
We give a quantum algorithm for computing an $epsilon$-approximate Nash equilibrium of a zero-sum game in a $m times n$ payoff matrix with bounded entries. Given a standard quantum oracle for accessing the payoff matrix our algorithm runs in time $widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$ and outputs a classical representation of the $epsilon$-approximate Nash equilibrium.
arXiv Detail & Related papers (2023-01-10T02:56:49Z)
Sample optimal tomography of quantum Markov chains [23.427626096032803]
A state on a tripartite quantum system $mathcalH_Aotimes mathcalH_B$ forms a Markov chain, i.e., quantum conditional independence, if it can be reconstructed from its marginal on $mathcalH_Aotimes mathcalH_B$. A quantum operation from $mathcalH_B$ to $mathcalH_BotimesmathcalH_C$ via the
arXiv Detail & Related papers (2022-09-06T06:30:37Z)
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)
Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices.
arXiv Detail & Related papers (2022-03-27T20:22:17Z)
A quantum searching model finding one of the edges of a subgraph in a complete graph [0.0]
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.
arXiv Detail & Related papers (2022-02-03T08:45:39Z)
On quantum algorithms for the Schr\"odinger equation in the semi-classical regime [27.175719898694073]
We consider Schr"odinger's equation in the semi-classical regime. Such a Schr"odinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics.
arXiv Detail & Related papers (2021-12-25T20:01:54Z)
Quantum Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z)

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