(x) = a (a==1 being a constant), all the amplitudes Uxz of |z) =||0) are equal to Ux0 =(-1)f(x) =(-1)a1Since = = (4) has a length of unity, this means that all other amplitudes Ux,z#0 must be zero. The query registers thus displays 14) = |0) i.e., all output qubits are equal to |0). A single measurement by projecting the register over |0) yielding (4/4) = 1, suffices to prove the point. Consider next the second case: if f(x) is balanced, this means that the amplitude of |z) = |0) is zero, as the terms (-1)f(x)+x.0 = (-1)f(x) in the sum in Eq. (19.3) cancel each other (one half yielding +1, the other half yielding 1). For any x we thus have the property (-1)f(x) = 0, indicating that f(x) is, indeed, balanced. In this case, the query register cannot output (4)=10) meaning that at least one of the register qubits must be |1). A single projection test yielding 0) = 0 suffices to prove the point. In summary, the Deutsch-Jozsa algorithm demonstrates the capability of quantum parallelism over an arbitrary number of qubits N. It takes a single calculation and a single measurement of the output register (4) to obtain the answer to Deutsch's problem. In contrast, a classical computation would require at least "2n/2 plus one" measurements with random inputs to obtain the same answer within reasonable confidence, and 2nd measurements for absolute confidence. While this discussion makes a point about the power of quantum parallelism, it should not be concluded that evaluating the properties of the function f(x) is of any particular interest to quantum computing algorithms. Rather, the Deutsch and Deutsch- Jozsa algorithms must be regarded as representing a most elegant introduction to the concept. Quantum Fourier transform algorithm In this section, I shall describe the quantum Fourier transform (QFT), which lies at the root of several important quantum-computing algorithms, for some revolutionary applications to be developed in Chapter 20. To avoid any misconception, QFT was not developed with the purpose of boosting the spe