On the Breakdown of Quantum Search with Spatially Distributed Marked Vertices

Thomas G. Wong

Published Jan 28, 2015• 2 citations

Abstract

Grover's algorithm finds one of $k$ items in an \emph{unstructured} database of size $N$ in time $O(\!\sqrt{N/k})$, and the algorithm's parameter(s) and runtime are unchanged no matter which of the $k$ items are marked. For \emph{structured} search by continuous-time quantum walk, however, we show that rearranging the marked elements can cause the parameter(s) or runtime to vary such that, without prior knowledge of the spatial distribution of the marked elements, a potentially sub-exponential number of configurations would need to be tried, meaning it would be better to not run the search algorithm at all.

Related papers

Grover's search with faults on some marked elements

Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

arXiv:1508.05108Aug 20, 20150 citations

Optimality conditions for spatial search with multiple marked vertices

Mathieu Roget, Hachem Kadri, Giuseppe Di Molfetta

arXiv:2201.12937Physical Review ResearchJul 11, 20234 citations

Grover’s Search with Faults on Some Marked Elements

Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

International Journal of Foundations of Computer ScienceJun 1, 20183 citations

Determinstic Grover's Algorithm: Finding the Needle in the Haystack Every Time … Well Most Times

F. Mohit, Markus Rambach, Till J. Weinhold +3 more

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)Jun 23, 20250 citations

Multimarked Spatial Search by Continuous-Time Quantum Walk

Pedro H. G. Lugão, Renato Portugal, Mohamed Sabri +1 more

arXiv:2203.14384ACM Transactions on Quantum ComputingNov 27, 20245 citations

Deterministic spatial search using alternating quantum walks

S. Marsh, Jingbo B. Wang

arXiv:2104.03806Physical Review AAug 24, 202115 citations

On the Breakdown of Quantum Search with Spatially Distributed Marked Vertices

Thomas G. Wong

Published Jan 28, 2015• 2 citations

OpenAlex

Abstract

Grover's algorithm finds one of

k

items in an \emph{unstructured} database of size

N

in time

O(\!\sqrt{N/k})

, and the algorithm's parameter(s) and runtime are unchanged no matter which of the

k

items are marked. For \emph{structured} search by continuous-time quantum walk, however, we show that rearranging the marked elements can cause the parameter(s) or runtime to vary such that, without prior knowledge of the spatial distribution of the marked elements, a potentially sub-exponential number of configurations would need to be tried, meaning it would be better to not run the search algorithm at all.

Related papers

Grover's search with faults on some marked elements

Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size $N$ using $O(\sqrt{N})$ queries. It provides a significant speed-up over any classical algorithm \cite{Gro96}. The running time of the algorithm, however, is very sensitive to errors in queries. It is known that if query may fail (report all marked elements as unmarked) the algorithm needs $Ω(N)$ queries to find a marked element \cite{RS08}. \cite{AB+13} have proved the same result for the model where each marked element has its own probability to be reported as unmarked. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of non-faulty marked items in $O(\sqrt{N})$ queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of limiting state $ρ_{lim}$ .Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size $N$ using $O(\sqrt{N})$ queries. It provides a significant speed-up over any classical algorithm \cite{Gro96}. The running time of the algorithm, however, is very sensitive to errors in queries. It is known that if query may fail (report all marked elements as unmarked) the algorithm needs $Ω(N)$ queries to find a marked element \cite{RS08}. \cite{AB+13} have proved the same result for the model where each marked element has its own probability to be reported as unmarked. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of non-faulty marked items in $O(\sqrt{N})$ queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of limiting state $ρ_{lim}$.

arXiv:1508.05108Aug 20, 20150 citations

Optimality conditions for spatial search with multiple marked vertices

Mathieu Roget, Hachem Kadri, Giuseppe Di Molfetta

We contribute to fulfill 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), 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\text{\ensuremath{-}}\text{dimensional}$ grid and it has been proven they provide a quadratic advantage over classical searching protocols. However, once we consider searching more than one element, the behavior 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 sufficient conditions for optimality for a multi-items QWSearch algorithm; (ii) we provide analytical evidence that 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.We contribute to fulfill 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), 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\text{\ensuremath{-}}\text{dimensional}$ grid and it has been proven they provide a quadratic advantage over classical searching protocols. However, once we consider searching more than one element, the behavior 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 sufficient conditions for optimality for a multi-items QWSearch algorithm; (ii) we provide analytical evidence that 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.

arXiv:2201.12937Physical Review ResearchJul 11, 20234 citations

Grover’s Search with Faults on Some Marked Elements

Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size [Formula: see text] using [Formula: see text] queries. It provides a significant speed-up over any classical algorithm [3]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6]. We study the behavior of Grover’s algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in [Formula: see text] queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of a limiting state [Formula: see text].Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size [Formula: see text] using [Formula: see text] queries. It provides a significant speed-up over any classical algorithm [3]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6]. We study the behavior of Grover’s algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in [Formula: see text] queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of a limiting state [Formula: see text].

International Journal of Foundations of Computer ScienceJun 1, 20183 citations

Determinstic Grover's Algorithm: Finding the Needle in the Haystack Every Time … Well Most Times

F. Mohit, Markus Rambach, Till J. Weinhold +3 more

Grover's algorithm is a quantum algorithm that interrogates an N-element unstructured database in $\sqrt{N}$ searches as opposed to the best classical algorithm, which requires $N/2$ [1]. The algorithm is non-deterministic, with a significant probability of failing that varies with the size of the database and the number of marked elements. For example, with a single marked element, the success probability is 100% for $N=4$ , drops to 87% for $N=7$ , is near 100% for $N=9$ , and is below 94% for $N=15$ . This can be improved by several repetitions of the algorithm, which, however, lowers its quadratic quantum advantage.Grover's algorithm is a quantum algorithm that interrogates an N-element unstructured database in$\sqrt{N}$searches as opposed to the best classical algorithm, which requires$N/2$[1]. The algorithm is non-deterministic, with a significant probability of failing that varies with the size of the database and the number of marked elements. For example, with a single marked element, the success probability is 100% for$N=4$, drops to 87% for$N=7$, is near 100% for$N=9$, and is below 94% for$N=15$. This can be improved by several repetitions of the algorithm, which, however, lowers its quadratic quantum advantage.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)Jun 23, 20250 citations

Multimarked Spatial Search by Continuous-Time Quantum Walk

Pedro H. G. Lugão, Renato Portugal, Mohamed Sabri +1 more

The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is $O(\sqrt {N})$ with an asymptotic probability of 1+ o (1), where N is the number of vertices.The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is $O(\sqrt {N})$ with an asymptotic probability of 1+ o (1), where N is the number of vertices.

arXiv:2203.14384ACM Transactions on Quantum ComputingNov 27, 20245 citations

Deterministic spatial search using alternating quantum walks

S. Marsh, Jingbo B. Wang

This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. 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 that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an $N$ -vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.This paper examines the performance of spatial search where the Grover diffusion operator is replaced by continuous-time quantum walks on a class of interdependent networks. 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 that finds the marked vertex with 100% probability. This improves on the Childs and Goldstone spatial search algorithm on the same class of graphs, which we show can only amplify to 50% probability. Our method uses $\ensuremath{\lceil}\frac{\ensuremath{\pi}}{2\sqrt{2}}\sqrt{N}\ensuremath{\rceil}$ marked vertex phase shifts for an $N$-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.

arXiv:2104.03806Physical Review AAug 24, 202115 citations

Grover's algorithm finds one of

k

items in an \emph{unstructured} database of size

N

in time

O(\!\sqrt{N/k})

, and the algorithm's parameter(s) and runtime are unchanged no matter which of the

k

Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size

N

using

O(\sqrt{N})

queries. It provides a significant speed-up over any classical algorithm \cite{Gro96}. The running time of the algorithm, however, is very sensitive to errors in queries. It is known that if query may fail (report all marked elements as unmarked) the algorithm needs

Ω(N)

queries to find a marked element \cite{RS08}. \cite{AB+13} have proved the same result for the model where each marked element has its own probability to be reported as unmarked. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of non-faulty marked items in

O(\sqrt{N})

queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of limiting state

ρ_{lim}

Grover's algorithm is a quantum algorithm that interrogates an N-element unstructured database in

\sqrt{N}

searches as opposed to the best classical algorithm, which requires

N/2

[1]. The algorithm is non-deterministic, with a significant probability of failing that varies with the size of the database and the number of marked elements. For example, with a single marked element, the success probability is 100% for

N=4

, drops to 87% for

N=7

, is near 100% for

N=9

, and is below 94% for

N=15

. This can be improved by several repetitions of the algorithm, which, however, lowers its quadratic quantum advantage.

O(\sqrt {N})

with an asymptotic probability of 1+ o (1), where N is the number of vertices.

N

-vertex graph, making it comparable to Grover's algorithm for an unstructured search. It is expected that this framework can be readily extended to deterministic spatial search on other families of graph structures.