Quantum computer algorithms are designed to exploit the properties of quantum physics. Quantum computations can be carried out in parallel on superpositions of exponentially many computational basis states and information about theoutcomes of these computations can be measured via quantum interference. Bycasting quantum algorithms within the paradigm of quantum interferometry, mostof the known quantum algorithms are clari\fed, uni\fed, and generalised.Further, the limitations of quantum computer algorithms is studied in theblack-box model of computation, where the black-box reveals information aboutcertain parameters (in this case Boolean values X1; X2; : : : ; XN ) and we wish tocompute a function of these parameters. It is shown that the probability amplitudes of a quantum algorithm which has made T black-box calls is a polynomialin X1; X2; : : : ; XN of degree at most T . From this fact we can derive severallower bounds on the number of queries required to compute various functions ofX1; X2; : : : ; XN , such as their parity, or ma jority value. Further, any function thatcan be evaluated probabilistically using T queries on a quantum computer can beevaluate deterministically on a classical computer using at most (4T )6queries.Several other relationships are also established.Lastly, techniques for better exploiting a \fxed amount of quantum resourcesare illustrated and versions of quantum algorithms that can be implemented withvery few qubits are suggested. I describe some of the \frst quantum algorithms anddetail the \frst implementation, namely, the Deutsch algorithm.
D (Lin or=> ( A ) i) FIGURE 2.8. One common approach is to analysis the above state in the computational basis, but analysing the second register in the eigenvector basis produces a convenient description of the final
id: a8ce3f9ce1271ecdb229a5a001e122fb - page: 86
we get 2mi yo Yd y (Sere) sey yeG/k \teT (the first summation is over a set of coset representatives y of G/K) whereas in our analysis we write this in the eigenvector basis as do 18) 1%) teT as illustrated in figure 2.8. 2.10. Finding Hidden Affine Functions As pointed out in the previous section, Deutschs problem (section 2.1) is a very special instance of the hidden subgroup problem. It can also be rephrased as follows. PROBLEM 40. Given an integer N and a function f : ma +b, where xz,m,b Zo, find m. We can partially generalise this problem as follows. 2.10. FINDING HIDDEN AFFINE FUNCTIONS 86 PROBLEM 41. Given an integer N function f : 2 > mx +b, where x,m,b Zn, find m. Since b could be any integer from Zy, one classical evaluation of f gives no information about m. The next algorithm, however solves Problem 41 with just one application of U,. ALGORITHM 42. Input: e An integer N. e A black-box that implements Uy : |x) |y) > |x) |y+ f(x)).
id: cb1cd7736c4d545702a1c6254d7ee638 - page: 86
Output: e An integer m Zy. Complexity: e 1 application of Us e 1 application of QFT(N) and 2 applications of QFT(N)!. Procedure: 1. Start with two registers in the state |00...0)|Y,) Hy x Hy where |) = QFT(N)"'|1). . Apply QFT(N) to the first register. . Apply Us. . Apply QFT(N)~ to the first register. Ee WwW bw 5. Measure the first register and output the measured value. PROPOSITION 43. Algorithm 42 solves Problem 41. 2.10. FINDING HIDDEN AFFINE FUNCTIONS 87 ProoF. The second register is in the state N-1 | Wi) = Se?" | j) j=0 which is an eigenstate of the operation | y) > |y + f(z)) with eigenvalue emit After step 3 we will have the state N-1
id: 18afa28fec181fca39e8e94a87f24820 - page: 87
to the first register we get 2" |m) | W,). As with the hidden subgroup algorithm, we are measuring the eigenvalues o shift functions | f(z)) > | f(z + y)), except in this case we know the eigenvectors and can efficiently construct one, and the respective eigenvalue directly gives us the desired solution (in contrast, the hidden subgroup algorithms only output elements orthogonal to the solution, from which the solution is derived by linear algebra). Bernstein and Vazirani [BV97] generalised the Deutsch problem another way that we describe here. PROBLEM 44. Given a function f : 2 4 m"-x-+b, where x,m Z3, b Zo, find m. This following algorithm is a refinement of the one proposed in [BV97] for solving Problem 44. ALGORITHM 45.
id: bc96c6b1090f1d13a8ebc20d427d4edd - page: 88