arXiv:1508.05108

Grover's search with faults on some marked elements

Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

Published Aug 20, 2015• 0 citations

Abstract

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}$.

DOI: 10.48550/arxiv.1508.05108

Related papers

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

On fault-tolerance of Grover's algorithm

Nikolajs Nahimovs, Alexander Rivosh, Dmitry Kravchenko

Jan 1, 20120 citations

A Grover-based quantum search of optimal order for an unknown number of marked elements

Christof Zalka

arXiv:quant-ph/9902049Feb 12, 19999 citations

On the Breakdown of Quantum Search with Spatially Distributed Marked Vertices

Thomas G. Wong

Jan 28, 20152 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

Grover’s quantum search algorithm and Diophantine approximation

Shahar Dolev, Itamar Pitowsky, Boaz Tamir

arXiv:quant-ph/0507234Physical Review AFeb 3, 20063 citations

arXiv:1508.05108

Grover's search with faults on some marked elements

Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

Published Aug 20, 2015• 0 citations

arXiv HTML PDF

Abstract

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}

DOI: 10.48550/arxiv.1508.05108

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 [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

On fault-tolerance of Grover's algorithm

Nikolajs Nahimovs, Alexander Rivosh, Dmitry Kravchenko

Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size N in O( √ N ) queries, while any classical algorithm needs O(N ) queries [1]. However, if the query transformation might fail (with probability independent of the number of steps of the algorithm), then quantum speed-up disappears: no quantum algorithm can be faster than a classical exhaustive search by more than a constant factor [6]. In this paper we study the effect of a small number of failed queries. We show that k failed queries with a very high probability change the number of actually executed steps of Grover’s algorithm from l to O � l √ kGrover’s algorithm is a quantum search algorithm solving the unstructured search problem of size N in O( √ N ) queries, while any classical algorithm needs O(N ) queries [1]. However, if the query transformation might fail (with probability independent of the number of steps of the algorithm), then quantum speed-up disappears: no quantum algorithm can be faster than a classical exhaustive search by more than a constant factor [6]. In this paper we study the effect of a small number of failed queries. We show that k failed queries with a very high probability change the number of actually executed steps of Grover’s algorithm from l to O � l √ k

Jan 1, 20120 citations

A Grover-based quantum search of optimal order for an unknown number of marked elements

Christof Zalka

We want to find a marked element out of a black box containing N elements. When the number of marked elements is known this can be done elegantly with Grover's algorithm, a variant of which even gives a correct result with certainty. On the other hand, when the number of marked elements is not known the problem becomes more difficult. For every prescribed success probability I give an algorithm consisting of several runs of Grover's algorithm that matches a recent bound by Buhrman and de Wolf on the order of the number of queries to the black box. The improvement in the order over a previously known algorithm is small and the number of queries can clearly still be reduced by a constant factor.We want to find a marked element out of a black box containing N elements. When the number of marked elements is known this can be done elegantly with Grover's algorithm, a variant of which even gives a correct result with certainty. On the other hand, when the number of marked elements is not known the problem becomes more difficult. For every prescribed success probability I give an algorithm consisting of several runs of Grover's algorithm that matches a recent bound by Buhrman and de Wolf on the order of the number of queries to the black box. The improvement in the order over a previously known algorithm is small and the number of queries can clearly still be reduced by a constant factor.

arXiv:quant-ph/9902049Feb 12, 19999 citations

On the Breakdown of Quantum Search with Spatially Distributed Marked Vertices

Thomas G. Wong

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.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.

Jan 28, 20152 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

Grover’s quantum search algorithm and Diophantine approximation

Shahar Dolev, Itamar Pitowsky, Boaz Tamir

In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size $N$ by using only $O(\sqrt{N})$ queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either $M$ or $K$ , our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let $m$ be the required number of iterations; we prove that under certain restrictions on the sizes of $M$ and $K$ the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size $N$ by using only $O(\sqrt{N})$ queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either $M$ or $K$, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let $m$ be the required number of iterations; we prove that under certain restrictions on the sizes of $M$ and $K$ the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.

arXiv:quant-ph/0507234Physical Review AFeb 3, 20063 citations

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

N

using

O(\sqrt{N})

Ω(N)

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 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.

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.

In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size

N

by using only

O(\sqrt{N})

queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either

M

K

, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let

m

be the required number of iterations; we prove that under certain restrictions on the sizes of

M

and

K

the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.