Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- URL: http://arxiv.org/abs/2111.09012v4
- Date: Sat, 19 Nov 2022 12:05:43 GMT
- Title: Robust Quantum Walk Search Without Knowing the Number of Marked Vertices
- Authors: Yongzhen Xu, Delong Zhang, Lvzhou Li
- Abstract summary: 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.
- Score: 0.2320417845168326
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: There has been a very large body of research on searching a marked vertex on
a graph based on quantum walks, and Grover's algorithm can be regarded as a
quantum walk-based search algorithm on a special graph. However, the existing
quantum walk-based search algorithms suffer severely from the souffl\'{e}
problem which mainly means that the success probability of finding a marked
vertex could shrink dramatically even to zero when the number of search steps
is greater than the right one, thus heavily reducing the robustness and
practicability of the algorithm. Surprisingly, while the souffl\'{e} problem of
Grover's algorithm has attracted enough attention, how to address this problem
for general quantum walk-based search algorithms is missing in the literature.
Here we initiate the study of overcoming the souffl\'{e} problem for quantum
walk-based search algorithms by presenting a new quantum walk-based search
framework that achieves robustness without sacrificing the quantum speedup. In
this framework, for any adjustable parameter $\epsilon$, the quantum algorithm
can find a marked vertex on an $N$-vertex {\it complete bipartite graph} with
probability at least $ 1-\epsilon$, whenever the number of search steps $h$
satisfies $h \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N} + 1$. Note that the
algorithm need not know the exact number of marked vertices. Consequently, we
obtain quantum search algorithms with stronger robustness and practicability.
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) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - Quantum algorithms and the power of forgetting [1.5791732557395555]
We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT.
While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit from this behavior.
arXiv Detail & Related papers (2022-11-22T18:04:10Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
Amplitude amplification is usually used to amplify success probability, but the souffl'e problems follow.
In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the souffl'e problems.
arXiv Detail & Related papers (2022-09-09T07:43:46Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - 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) - 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) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
Given a unitary matrix that performs certain operation, obtaining the equivalent quantum circuit is a non-trivial task.
Three problems are explored: the coin for the quantum walker, the Toffoli gate and the Fredkin gate.
The algorithm proposed proved to be efficient in decomposition of quantum circuits, and as a generic approach, it is limited only by the available computational power.
arXiv Detail & Related papers (2021-06-06T13:15:25Z) - 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)
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.