The kinds of search algorithms that can run on quantum computers are qualitatively different from those that run on classical computers. As this article shows, quantum searches are thus vastly more efficient on certain kinds of problems.
Quantum computing introduces an efficient way for unfolding complex problems on computing systems. It uses concept of superposition and entanglement, & hence supports intrinsic parallelism for obtaining the speedup in context of time over classical computing. Quantum algorithms can be efficiently implemented over quantum computing system. Most popular quantum algorithms like Grover's and Shor's provide a great foundation to specifically design the algorithms. These algorithms work on improving the lower runtime bounds of classical algorithms. Grover's algorithm exhibits a quadratic polynomial speedup while searching an element among `N' elements unstructured database. The algorithmic strategy can be applied over various computer science related applications and some important are being considered in this article i.e. pattern matching, data mining and machine learning. This article explores quantum fundamentals; history based evolution followed by Grover's search algorithm in detail with cascading advantages, limitations & applications and also finally concludes with the significance of quantum computing & quantum algorithmic domains.
Quantum computing is the delicate art of using a quantum-mechanical system to perform some kind of computation. Such a system differs in a number of significant ways from ordinary computers:• A quantum computer actually does a lot of computations at the same time, each solution is represented by a particular possible state. This is inherent to the physical properties of such a system.• Unless you are sure that you have reached the final (unique) solution, you can not "look" at the "values" of the variables in the computer program that is being run: since all solutions are possible at the same time, observing the values will influence the system and put it into one particular, but otherwise arbitrary, state.• All computations must be reversible, that is, a statement like "a = 5" can only appear in the initialization phase of a program, because the previous value will be lost. On the other hand, a statement like "a = a + 5" is reversible, since you can retrieve the original value.The properties of such a quantum computer make it possible to devise very efficient algorithms. One such algorithm, described by L. Grover (see the references), is searching in an unsorted array of items. With ordinary computers this can not be done more efficiently than in O (N) steps (an exhaustive search: each item is examined in the worst case), with this quantum algorithm, however, the number of steps needed is O (N 1/2 ).Devising quantum algorithms requires a thorough understanding of quantum mechanics, there is no doubt about that. Another question is: do we need quantum computers and special programming languages to program (or perhaps emulate) these algorithms? This article tries to show that, at least for the quantum search algorithm, a classical programming language like Fortran is quite fit (yes, the pun is fortunate).
Applied Physics
Quantum computers, when they become available, will harness the power of quantum mechanics to perform calculations and searches, outperforming classical computers at certain tasks. The development of quantum computers is two-pronged: Both hardware and software must be devised. The focus in the software realm is on which problems can be solved and how to do so. Solving a set of linear equations is a generic and important problem in many fields of science, engineering, and mathematics. On a classical computer the computational cost of extracting a solution grows linearly with the size of the system. Harrow et al. have developed a quantum algorithm that will solve the problem much more rapidly (scaling as the logarithm of the system size), requiring exponentially less time. Now we wait for the machinery to arrive.
Phys. Rev. Lett. 103 , 150502 (2009).