It is well known that a quantum computer can search more quickly than a classical computer while solving the so-called Grover-searching problem.We present a new searching problem which cannot be classified into Grover's problem and can be solved by using the modified searching iterations with the same efficiency as for Grover's problem.
It is well known that a quantum computer can search more quickly than a classical computer while solving the so-called Grover-searching problem.We present a new searching problem which cannot be classified into Grover's problem and can be solved by using the modified searching iterations with the same efficiency as for Grover's problem.
Search is one of the most commonly used primitives in quantum algorithm design. It is known that quadratic speedups provided by Grover’s algorithm are optimal, and no faster quantum algorithms for Search exist. While it is known that at least some quantum computation is required to achieve these speedups, the existing bounds do not rule out the possibility of an equally fast hybrid quantum-classical algorithm where most of the computation is classical. In this work, we study such hybrid algorithms, and we show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. In addition, we generalize this result to algorithms with subconstant success probabilities.
Since Grover’s seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of n items x 1,…,x n and we would like to find i:x i =1. We consider a new variant of this problem in which evaluating x i for different i may take a different number of time steps. Let t i be the number of time steps required to evaluate x i . If the numbers t i are known in advance, we give an algorithm that solves the problem in O(t12+t22+…+tn2) steps. This is optimal, as we also show a matching lower bound. The case, when t i are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.
The research community has been actively working on the realization of quantum computer. But the large scale commercial quantum computers are not a reality yet quantum computing field has become richer by day with the advent of algorithms and the avenue of its application in multiple domains. Availability of efficient quantum simulators will enable the researchers to quickly verify their results and concepts in order to establish a working proof of correctness. One important algorithm that has become one of the basic ingredients to build other algorithms and models is the Grover's search Algorithm which is known to be the most compute intensive. Our approach highlights the design principles for the fast simulation of Grover's search which can be implemented on a general purpose personal computer. The performance obtained are encouraging when compared to the existing simulators.
This paper's aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover\cite{grover}. Grover's algorithm is a basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that are polynomially faster than fastest known and fastest possible classical algorithms that solve the same problems. Our goal in this paper is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by providing a set of tools, each of which makes use of Grover's algorithm or similar techniques, which can be used as subroutines in many quantum algorithms.}{The tools we provide are carefully constructed: they are easy to use, and in many cases they are asymptotically faster than the best tools previously available. The tools we build on include algorithms by Boyer, Brassard, Hoyer and Tapp, Buhrman, Cleve, de Witt and Zalka and Durr and Hoyer.}{After creating our tools, we create several new quantum algorithms, each of which is faster than the fastest known deterministic classical algorithm that accomplishes the same aim, and some of which are faster than the fastest possible deterministic classical algorithm. These algorithms solve problems from the fields of graph theory and computational geometry, and some employ dynamic programming techniques. We discuss a breadth-first search that is faster than Θ(edges) (the classical limit) in a dense graph, maximum-points-on-a-line in O(N3/2lgN) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools, working to encourage their use and the study of quantum algorithms in general.