useful applications in quantum computing, both algorithms represent a most elegant means of introducing the concept of quantum computation parallelism. I then describe two most important QC algorithms, which nicely exploit quantum parallelism. The first is the quantum Fourier transform (QFT), for which a detailed analysis of QFT circuits and quantum-gate requirements is also provided. As will be shown in the next chapter, a key application of QFT concerns the famous Shor's algorithm, which makes it possible to factor numbers into primes in terms of polynomials. The second algorithm, no less famous than Shor's, is referred to as the Grover quantum database search, whose application is the identification of database items with a quadratic gain in speed. Deutsch algorithm Our exploration of quantum algorithms shall begin with the solution of a very basic problem: finding whether or not a Boolean function f(x) is a constant. The solution is given by the Deutsch algorithm, which illustrates a fundamental property of quantum computing, namely parallelism. As we shall indeed see, quantum computation makes it possible to evaluate f(x) simultaneously for all values of the variable x, in contrast to classical computing (i.e., von Neumann architecture, Chapter 15) where such an evaluation must be performed one variable at a time, or through as many computers working in parallel. Assume then a Boolean function f(x) where x is a binary variable. We can con- ceive of a 2-qubit quantum circuit based on a unitary operator Uf that achieves the transformation Ufx,y)=x,yof(x)) (19.1) 19.1 Deutsch algorithm y + ((f) Figure 19.1 Quantum circuit for implementing the Deutsch algorithm. where the simplified notation lu, v) = |u) X /u) stands for tensor product. Consider next the quantum circuit arrangement shown in Fig. 19.1, where H are Hadamard gates and |0), |1) are two ancilla qubits. We call X, y the inputs resulting from the Hadamard transforms on the two ancilla qubits, and note that the action of the "black box" gate Uf on X, , 