y results in the outputs X, y + f(x). Let us now analyze the evolution of the tensor state, from left to right, through the locations marked 1234 in the figure, starting from /V/1 = = at 1: (19.2) |11)) (note the factor 1/2 introduced in the right-hand side, to ensure normalization of the tensor product of mixed states). Then, using the definition in Eq. (19.1): (19.3) Then, 4 - + |-,00f(1)) - Quantum database search algorithms (19.4) Next consider the two cases (a) a = f(0) = f(1), and (b) a = f(0) # f(1) = . From Eq. (19.4), we obtain: |0) |à)) (19.5) Finally, we note thatf(0)of(1)=0iff(0)=f(1) and f(0)of(1)=1iff(0) = # f(1). Using this property, and the definition of a Boolean variable |a) - |a) = + (|0) - |1)), we obtain from Eq. (19.5) within an unobservable phase eir -1: (19.6) The result shows that measuring the first qubit, namely, If(0) + f(1)), provides the answer "at once" to Deutsch's problem. Indeed, if we measure If(0) + f(1)) = |0), we conclude that f(0) = f(1) and, therefore, that f(x) is a constant, and if we measure f(0) (f(1)) = |1), we conclude the opposite. Thus, Deutsch's algorithm makes it possible to solve the problem without having to compute f(0), f(1) separately, unlike in the classical case. This simple problem magnifies the property of quantum parallelism, which is the key to quantum computing. 19.2 Deutsch-Jozsa algorithm Figure 19.2 Equivalent representation for n-qubit wires, with H gates deployed in parallel. (+f(x) Figure 19.3 Quantum circuit for implementing the Deutsch-Jozsa algorithm. Deutsch-Jozsa algorithm In this section, we consider the generalization of Deutsch's algorithm, which is referred to as the Deutsch-Jozsa algorithm. Now f(x) is a function of any inte- ger x E {0, 1, 2 2n-1}, which outputs a Boolean f(x) E {0, 1}. What is known as Deutsch's problem is to find a way to tell, for all possible values of X, whether f f(x) is constant, or f(x) is balanced, meaning in this last case that the output is 0 or 1 for exactly one half of the possible inputs. The answer to De