Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk
- URL: http://arxiv.org/abs/2112.03744v1
- Date: Tue, 7 Dec 2021 15:00:07 GMT
- Title: Spatial Search on Johnson Graphs by Discrete-Time Quantum Walk
- Authors: Hajime Tanaka, Mohamed Sabri, Renato Portugal
- Abstract summary: We address the spatial search problem on Johnson graphs using the coined quantum walk model.
For every fixed diameter, the success probability is $1/2$ after taking $pisqrt N/(2sqrt 2)$ steps.
We have shown that, for every fixed diameter, the success probability is $1/2$ after taking $pisqrt N/ (2sqrt)$ steps.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The spatial search problem aims to find a marked vertex of a finite graph
using a dynamic with two constraints: (1) The walker has no compass and (2) the
walker can check whether a vertex is marked only after reaching it. This
problem is a generalization of unsorted database search and has many
applications to algorithms. Classical algorithms that solve the spatial search
problem are based on random walks and the computational complexity is
determined by the hitting time. On the other hand, quantum algorithms are based
on quantum walks and the computational complexity is determined not only by the
number of steps to reach a marked vertex, but also by the success probability,
since we need to perform a measurement at the end of the algorithm to determine
the walker's position. In this work, we address the spatial search problem on
Johnson graphs using the coined quantum walk model. Since Johnson graphs are
vertex- and distance-transitive, we have found an invariant subspace of the
Hilbert space, which aids in the calculation of the computational complexity.
We have shown that, for every fixed diameter, the asymptotic success
probability is $1/2$ after taking $\pi\sqrt N/(2\sqrt 2)$ steps, where $N$ is
the number of vertices of the Johnson graph.
Related papers
- Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - 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) - 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) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
Continuous-time quantum walks provide a framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search.
We present a new continuous-time quantum walk search algorithm that can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks.
arXiv Detail & Related papers (2021-12-23T17:57:49Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical.
In this paper we present a comparative study of two quantum approaches to computing GED.
arXiv Detail & Related papers (2021-11-19T12:35:26Z) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
Existing quantum walk-based search algorithms suffer from the souffl'e problem.
We present a new quantum walk-based search framework that achieves robustness without sacrificing the quantum speedup.
arXiv Detail & Related papers (2021-11-17T10:04:44Z) - Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk [0.0]
We show that spatial search on Johnson graphs by continuous-time quantum walk achieves the lower bound $pisqrtN/2$ with success probability $1$ally for every fixed diameter.
The proof is mathematically rigorous and can be used for other graph classes.
arXiv Detail & Related papers (2021-08-04T12:16:24Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits.
Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering.
We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
arXiv Detail & Related papers (2021-06-22T11:07:38Z) - 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) - Second-order Conditional Gradient Sliding [79.66739383117232]
We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.
The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.
It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
arXiv Detail & Related papers (2020-02-20T17:52:18Z)
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.