Optimality conditions for spatial search with multiple marked vertices
- URL: http://arxiv.org/abs/2201.12937v3
- Date: Thu, 5 Jan 2023 08:22:34 GMT
- Title: Optimality conditions for spatial search with multiple marked vertices
- Authors: Mathieu Roget, Hachem Kadri and Giuseppe Di Molfetta
- Abstract summary: We provide conditions for optimality for a multi-items QWSearch algorithm.
We numerically show that the computational advantage with respect to the classical counterpart is not always certain.
- Score: 5.28539620288341
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We contribute to fulfil the long-lasting gap in the understanding of the
spatial search with multiple marked vertices. The theoretical framework is that
of discrete-time quantum walks (QW), \textit{i.e.} local unitary matrices that
drive the evolution of a single particle on the lattice. QW based search
algorithms are well understood when they have to tackle the fundamental problem
of finding only one marked element in a $d-$dimensional grid and it has been
proven they provide a quadratic advantage over classical searching protocols.
However, once we consider to search more than one element, the behaviour of the
algorithm may be affected by the spatial configuration of the marked elements
and even the quantum advantage is no longer guaranteed. Here our main
contribution is threefold~: (i)~we provide \textit{sufficient conditions for
optimality} for a multi-items QWSearch algorithm~; (ii)~we provide analytical
evidences that \textit{almost, but not all} spatial configurations with
multiple marked elements are optimal; and (iii)~we numerically show that the
computational advantage with respect to the classical counterpart is not always
certain and it does depend on the proportion of searched elements over the
total number of grid points.
Related papers
- Quantum algorithms through graph composition [0.40792653193642503]
We introduce the graph composition framework, a generalization of the st-connectivity framework for generating quantum algorithms.
We show how the st-connectivity framework subsumes the learning graph framework, the weighted-decision-tree framework, and a zero-error version of the latter.
We also simplify existing quantum algorithms for the space-efficient directed st-connectivity problem, the pattern-matching problem and the infix-search problem.
arXiv Detail & Related papers (2025-04-02T20:20:51Z) - Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
We show that Variational Quantum Algorithms can be a viable alternative to classical algorithms in the near future.
In particular, we compare the performances, in terms of success probability, of two algorithms, i.e., Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE)
The simulation experiments, performed for a set of simple problems, %CM230124 that involve a Cloud and two Edge nodes, show that the VQE algorithm ensures better performances when it is equipped with appropriate circuit textitansatzes that are able to restrict the search space
arXiv Detail & Related papers (2024-01-25T17:37:40Z) - 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) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
We show the first tight characterization of the optimal Hessian-dependent sample complexity.
A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances.
The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
arXiv Detail & Related papers (2023-06-21T17:03:22Z) - HKNAS: Classification of Hyperspectral Imagery Based on Hyper Kernel
Neural Architecture Search [104.45426861115972]
We propose to directly generate structural parameters by utilizing the specifically designed hyper kernels.
We obtain three kinds of networks to separately conduct pixel-level or image-level classifications with 1-D or 3-D convolutions.
A series of experiments on six public datasets demonstrate that the proposed methods achieve state-of-the-art results.
arXiv Detail & Related papers (2023-04-23T17:27:40Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
In this paper, we build the search algorithm upon a complicated search space with long-distance connections.
We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks.
In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
arXiv Detail & Related papers (2021-12-05T06:42:48Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function.
We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
arXiv Detail & Related papers (2021-09-30T19:17:35Z) - 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) - Deterministic spatial search using alternating quantum walks [0.0]
We prove that for a set of optimal quantum walk times and marked vertex phase shifts, a deterministic algorithm for structured spatial search is established.
This improves on the original spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability.
It is expected that this new framework can be readily extended to deterministic spatial search on other families of graph structures.
arXiv Detail & Related papers (2021-04-08T14:32:48Z) - Quantum walk-based search algorithms with multiple marked vertices [0.0]
The quantum walk is a powerful tool to develop quantum algorithms.
We extend previous analytical methods based on Szegedy's quantum walk.
Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.
arXiv Detail & Related papers (2021-03-23T22:57:07Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z) - On the optimality of spatial search by continuous-time quantum walk [0.0]
We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm.
Our predictions are valid, for example, for Hamiltonians whose spectral gap is considerably larger than $n-1/2$.
arXiv Detail & Related papers (2020-04-27T10:05:55Z)
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.