Let a classical algorithm be determined by sequential applications of a black box performing one step of this algorithm. If we consider this black box as an oracle which gives a value F(a) for any query a, we can compute T sequential applications of F on a classical computer relative to this oracle in time T. It is proved that if T=O(2^{n/7}), where n is the length of input, then the result of T sequential applications of F can not be computed on quantum computer with oracle for F for all possible F faster than in time Ω(T). This means that there is no general method of quantum speeding up of classical algorithms provided in such a general method a classical algorithm is regarded as iterated applications of a given black box. For an arbitrary time complexity T a lower bound for the time of quantum simulation was found to be Ω(T^{1/2}).
Let a classical algorithm be determined by sequential applications of a black box performing one step of this algorithm. If we consider this black box as an oracle which gives a value F(a) for any query a, we can compute T sequential applications of F on a classical computer relative to this oracle in time T. It is proved that if T=O(2^{n/7}), where n is the length of input, then the result of T sequential applications of F can not be computed on quantum computer with oracle for F for all possible F faster than in time Ω(T). This means that there is no general method of quantum speeding up of classical algorithms provided in such a general method a classical algorithm is regarded as iterated applications of a given black box. For an arbitrary time complexity T a lower bound for the time of quantum simulation was found to be Ω(T^{1/2}).
Let f denote length preserving function on words. A classical algorithm can be considered as T iterated applications of black box representing f, beginning with input word x of length n. It is proved that if T=O(2n/(7+e)),e>0, and f is chosen randomly then with probability 1 every quantum computer requires not less than T evaluations of f to obtain the result of classical computation. It means that the set of classical algorithms admitting quantum speeding up has probability measure zero. The second result is that for arbitrary classical time complexity T and f chosen randomly with probability 1 every quantum simulation of classical computation requires at least Ω(T) evaluations of f.
We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.
We investigate the reason for the quantum speedup -- quantum algorithms requiring fewer computation steps than their classical counterparts. We extend their representation to the process of setting the problem. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. This representation is to Bob and any external observer, it cannot be to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden inside it. We resort to relational quantum mechanics. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action. To her, the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. We show that we can ascribe to the final measurement the selection of any part -- say the R-th part -- of the random outcome of the initial measurement. This projects the input state to Alice on a state of lower entropy where she knows a corresponding part of the problem setting. The quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given an oracle problem and a value of R, this retrocausality model provides the number of black box computations required to solve it. Conversely, given a known quantum algorithm, it yields the value of R that explains its speed up. R = 1/2 always yields the number of black box computations required by an existing quantum algorithm and the order of magnitude of the number required by optimal one.
We investigate the reason for the quantum speedup -- quantum algorithms requiring fewer computation steps than their classical counterparts. We extend their representation to the process of setting the problem. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. This representation is to Bob and any external observer, it cannot be to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden inside it. We resort to relational quantum mechanics. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action. To her, the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. We show that we can ascribe to the final measurement the selection of any part -- say the R-th part -- of the random outcome of the initial measurement. This projects the input state to Alice on a state of lower entropy where she knows a corresponding part of the problem setting. The quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given an oracle problem and a value of R, this retrocausality model provides the number of black box computations required to solve it. Conversely, given a known quantum algorithm, it yields the value of R that explains its speed up. R = 1/2 always yields the number of black box computations required by an existing quantum algorithm and the order of magnitude of the number required by optimal one.
Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 7th root of the classical randomized query complexity. (An earlier version of this paper gave the 9th root.) This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O'Donnell et al. (2005) and Dinur et al. (2006), we conjecture that every bounded low-degree polynomial has a "highly influential" variable. Assuming this conjecture, we show that every T-query quantum algorithm can be simulated on most inputs by a poly(T)-query classical algorithm, and that one essentially cannot hope to prove P!=BQP relative to a random oracle.