utsch's problem takes the form of a quantum algorithm, whose circuit is similar to the previous one. The difference is that x is not a single Boolean but a binary number, which we shall distribute over as many qubits. As a new convention for quantum circuits, we shall represent n-qubit wires with H gates deployed in parallel, according to Fig. 19.2. The Deutsch-Jozsa circuit is represented in Fig. 19.3 (recalling from Chapter 17 the notation Aon for n-tensored operators A). The circuit is seen to have n ancilla qubits |0) and one ancilla qubit |1) as inputs, which pass together through n + 1 parallel Hadamard gates. The input tensor state at 1 is |0) X |0))" times |1). At 2 in Fig. 19.3, Quantum database search algorithms we obtain (19.7) We call /x) the query register, similarly to the "register" in the classical von Neumann architecture (Chapter 15) the difference being that it is made of qubits. At 3, we obtain2 (19.8) And at 4, after passing the top n-qubit through the parallel gate Hon, , we obtain: (19.9) To develop the right-hand side in Eq. (19.9), we must calculate = Hon /x1x2...xn). It is an easy exercise to establish that: (19.10) where x . Z = X1Z1 + X2Z2 + + XnZn is a scalar product modulo 2. Combining Eqs. (19.9) and (19.10), we then obtain: (19.11) 1 In the last two equations, I have introduced the equivalent n-qubit notations = (|0) +|1)) with Xi = 0, 1 and x = 0, 1,2...2n-1. The correspondence is easily checked with n = 2 and then by induction. 2 The last equality in Eq. (19.8) is straightforward: given x, if f(x) = 0 then 10 + f(x)) - 10 f(x)) = |0) - |1) = (-1) (10) - |1)); if f(x) = 1 then 10 + f(x)) - = 1 |0) = (-1)¹ (|0) - |1)); hence, - case. 19.3 Quantum Fourier transform algorithm (19.12) (19.13) The n-qubit (4) defined in Eqs. (19.11) and (19.12) represents the output query register. As we shall see, the corresponding amplitudes Uxz contain all the information needed to answer Deutsch's problem. To show this, consider the two cases of interest: f(x) is constant, or f(x) is balanced. If f