In this section, we discuss a broadly applicable quantum algorithm that provides a polynomial speed-up over the best-known classical algorithms for a wide class of important problems. The quantum search algorithm performs a generic search for a solution to a very wide range of problems. Consider any problem where one can efficiently recognize a good solution and wishes to search through a list of potential solutions in order to find a good one. For example, given a large integer N, one can efficiently recognize whether an integer p is a non-trivial factor of N, and thus one naive strategy for finding non-trivial factors of N is to simply search through the set {2, 3, 4, . . . , ⌊√N⌋} until a factor is found. The factoring algorithm we described in Chapter 7 is not such a naive algorithm, as it makes profound use of the structure of the problem. However, for many interesting problems, there are no known techniques that make much use of the structure of the problem, and the best-known algorithm for solving these problems is to naively search through the potential solutions until one is found. Typically the number of potential solutions is exponential in the size of the problem instance, and so the naive algorithm is not efficient. Often the best-known classical search makes some very limited use of the structure of the problem, perhaps to rule out some obviously impossible candidates, or to prioritize some more likely candidates, but the overall complexity of the search is still exponential. Quantum searching is a tool for speeding up these sorts of generic searches through a space of potential solutions. It is worth noting that having a means of recognizing a solution to a problem, and knowing the set of possible solutions, means that in some sense one ‘knows’ the solution. However, one cannot necessarily efficiently produce the solution. For example, it is easy to recognize the factors of a number, but finding those factors can take a long time. We give this problem a more general mathematical structure as follows.
In this section, we discuss a broadly applicable quantum algorithm that provides a polynomial speed-up over the best-known classical algorithms for a wide class of important problems. The quantum search algorithm performs a generic search for a solution to a very wide range of problems. Consider any problem where one can efficiently recognize a good solution and wishes to search through a list of potential solutions in order to find a good one. For example, given a large integer N, one can efficiently recognize whether an integer p is a non-trivial factor of N, and thus one naive strategy for finding non-trivial factors of N is to simply search through the set {2, 3, 4, . . . , ⌊√N⌋} until a factor is found. The factoring algorithm we described in Chapter 7 is not such a naive algorithm, as it makes profound use of the structure of the problem. However, for many interesting problems, there are no known techniques that make much use of the structure of the problem, and the best-known algorithm for solving these problems is to naively search through the potential solutions until one is found. Typically the number of potential solutions is exponential in the size of the problem instance, and so the naive algorithm is not efficient. Often the best-known classical search makes some very limited use of the structure of the problem, perhaps to rule out some obviously impossible candidates, or to prioritize some more likely candidates, but the overall complexity of the search is still exponential. Quantum searching is a tool for speeding up these sorts of generic searches through a space of potential solutions. It is worth noting that having a means of recognizing a solution to a problem, and knowing the set of possible solutions, means that in some sense one ‘knows’ the solution. However, one cannot necessarily efficiently produce the solution. For example, it is easy to recognize the factors of a number, but finding those factors can take a long time. We give this problem a more general mathematical structure as follows.
In Chs. 2 and 3 we described several quantum algorithms that are exponentially faster than classical algorithms for the same problem, under some measure of complexity. Unfortunately, the algorithms of Ch. 2 apply to rather contrived problems that do not have known direct applications. We now describe a quantum algorithm that gives only a polynomial—more specifically, quadratic—speedup with respect to classical algorithms, but it applies to a large class of problems and finds many useful applications, both directly and as an algorithmic design tool. The algorithm is known as Grover’s search [89], and its generalization is known as amplitude amplification [43]. Amplitude amplification is widely used as part of many quantum algorithms. It also serves as the basis for amplitude estimation, a way of estimating probabilities quadratically faster than with classical Monte Carlo, and for quantum minimum finding. All these topics are discussed in this chapter.
Any computation is necessarily a physical process. The current drive towards increasing speed and miniaturization of computers lead modern technology towards the subatomic domain - quantum computing, where strange quantum behavior takes over from familiar classical notions. The quantum computers have the ability to solve problems with varied computational complexities and more importantly hard problems. A problem is said to be hard, if the best possible algorithm requires exponential resources. This exponential quantum parallelism is the basis for the quantum speedup of many algorithms, and has made the construction of fast algorithms for quantum computers possible. Various proposals exist for modeling and devising procedures on computational problems related to factoring, searching, quantum counting, generalization of quantum algorithms etc. (Shor, 1994). In this paper, we have discussed the importance of algorithms such as order-finding, factoring and quantum searching which require exorbitant resources for their solution which otherwise is impossible on a classical computer
In this chapter, we focus on quantum algorithms and the techniques underlying their construction. These algorithms take advantage of the basic properties of quantum mechanics, from the superposition principle to entanglement and interference effects, to solve certain computational problems much more efficiently than a classical computer. This includes basic problems of computer science: from the search of a marked item in an unstructured database (Grover’s algorithm) to integer factoring (Shor’s algorithm). The latter case provides a striking exponential speedup over the best known classical algorithms. After that, we discuss a third relevant class of quantum algorithms, the simulation of physical systems.
These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms.So far, we have only discovered a few techniques which can produce speed up versus classical algorithms.It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.In the first section of these notes, I try to explain why the recent results about quantum computing have been so surprising.This section comes from a talk I have been giving for several years now, and discusses the history of quantum computing and its relation to the mathematical foundations of computer science.In Sections 2 and 3, I talk about the quantum computing model and its relationship to physics.These sections rely heavily on two of my papers [SIAM J. Comp.26 (1997), 1484-1509; Doc.Math.Extra Vol.ICM I (1998), 467-486].Sections 4 and 5 illustrate the general technique of using quantum Fourier transforms to find periodicity.Section 4 contains an algorithm of Dan Simon showing that quantum computers are likely to be exponentially faster than classical computers for some problems.Section 5 discusses my factoring algorithm, which was inspired in part by Dan Simon's paper.In the final section, I discuss Lov Grover's search algorithm, which illustrates a different technique for speeding up classical algorithms.These techniques for constructing faster algorithms for classical problems on quantum computers are the only two significant ones which have been discovered so far.
Consider a Boolean function χ:X→{0,1} that partitions set X between its good and bad elements, where x is good if χ(x)=1 and bad otherwise. Consider also a quantum algorithm A such that A∣0⟩=∑x∈Xαx∣x⟩ is a quantum superposition of the elements of X, and let a denote the probability that a good element is produced if A∣0⟩ is measured. If we repeat the process of running A, measuring the output, and using χ to check the validity of the result, we shall expect to repeat 1/a times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good x after an expected number of applications of A and its inverse which is proportional to 1/a, assuming algorithm A makes no measurements. This is a generalization of Grover's searching algorithm in which A was restricted to producing an equal superposition of all members of X and we had a promise that a single x existed such that χ(x)=1. Our algorithm works whether or not the value of a is known ahead of time. In case the value of a is known, we can find a good x after a number of applications of A and its inverse which is proportional to 1/a even in the worst case. We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform amplitude estimation, a process that allows to estimate the value of a. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of x∈X such that χ(x)=1. We obtain optimal quantum algorithms in a variety of settings.
Abstract Quantum superposition is a powerful computational tool to have at one’s disposal – in fact, a phrase along the lines quantum computers evaluate a function for every possible input in superposition and hence achieve a massive speed-up appears in virtually every popular and media article on the subject. The reality is, however, a little more complicated. In this chapter, we look at what is probably the closest quantum algorithm to the naive idea of ‘evaluating for every possibility at once’, namely Lov Grover’s quantum search algorithm. Grover’s algorithm is one of the oldest and most important quantum algorithms and offers a quadratic advantage over the best possible classical algorithm for the problem of searching an unstructured database. Notably, a quadratic quantum advantage is the best one can hope for in certain problems that exhibit a lack of structure, which is proven by considering the performance of the best possible quantum algorithm tackling the OR problem.