Quantum search by continuous-time quantum walk on t-designs
- URL: http://arxiv.org/abs/2310.14141v1
- Date: Sun, 22 Oct 2023 00:37:52 GMT
- Title: Quantum search by continuous-time quantum walk on t-designs
- Authors: Pedro H. G. Lug\~ao, Renato Portugal
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This work examines the time complexity of quantum search algorithms on
combinatorial $t$-designs with multiple marked elements using the
continuous-time quantum walk. Through a detailed exploration of $t$-designs and
their incidence matrices, we identify a subset of bipartite graphs that are
conducive to success compared to random-walk-based search algorithms. These
graphs have adjacency matrices with eigenvalues and eigenvectors that can be
determined algebraically and are also suitable for analysis in the
multiple-marked vertex scenario. We show that the continuous-time quantum walk
on certain symmetric $t$-designs achieves an optimal running time of
$O(\sqrt{n})$, where $n$ is the number of points and blocks, even when
accounting for an arbitrary number of marked elements. Upon examining two
primary configurations of marked elements distributions, we observe that the
success probability is consistently $o(1)$, but it approaches 1 asymptotically
in certain scenarios.
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) - 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) - Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk [0.8057006406834466]
This paper presents a deterministic search algorithm on complete bipartite graphs.
We address the most general case of multiple marked states, so there is a problem of estimating the number of marked states.
We construct a quantum counting algorithm based on the spectrum structure of the search operator.
arXiv Detail & Related papers (2024-04-02T05:09:33Z) - Taming Quantum Time Complexity [45.867051459785976]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for
Multi-Block Bilevel Optimization [43.74656748515853]
Non-stationary multi-block bilevel optimization problems involve $mgg 1$ lower level problems and have important applications in machine learning.
We aim to achieve three properties for our algorithm: a) matching the state-of-the-art complexity of standard BO problems with a single block; (b) achieving parallel speedup by sampling $I$ samples for each sampled block per-iteration; and (c) avoiding the computation of the inverse of a high-dimensional Hessian matrix estimator.
arXiv Detail & Related papers (2023-05-30T04:10:11Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - Quantum Approximate Counting for Markov Chains and Application to
Collision Counting [0.0]
We show how to generalize the quantum approximate counting technique developed by Brassard, Hoyer and Tapp [ICALP 1998] to estimating the number of marked states of a Markov chain.
This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful "quantum walk based search" framework established by Magniez, Nayak, Roland and Santha.
arXiv Detail & Related papers (2022-04-06T03:04:42Z) - 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) - 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) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated.
Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform.
In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
arXiv Detail & Related papers (2020-11-24T18:44:57Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers.
We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
arXiv Detail & Related papers (2020-02-26T16:19:09Z)
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.