Home > issue 5 > The Essence of Quantum Computing

## The Essence of Quantum Computing Part 2 of 3 Part Series

### 9.4 Swapping states

Three applications of the Cnot gate will swap |a, b〉 to |b, a〉:

where ⊕ denotes modulo 2 addition2

### 9.5 The Deutsch algorithm

Pay very careful attention to this landmark algorithm in quantum computing. Consider the Boolean functions f that map {0, 1} to {0, 1}. There are exactly four such functions, as follows:

(1) two “constant” functions: f(0) = f(1) = 0 and f(0) = f(1) = 1;
(2) two “balanced” functions: f(0) = 0, f(1) = 1 and f(0) = 1, f(1) = 0.

The task is to identify the set to which f(0) and f(1) belong to in only one measurement. Note, that we do not seek the values of f(0) and f(1) but only a global property of f.

The solution provided here is reported in Cleve, et al3., which improves upon the original paper by Deutsch (1985)4. Deutsch’s solution had three possible outcomes: “balanced”, “constant”, and “inconclusive” with 50% probability that it would produce an “inconclusive” result. The solution described here always correctly identifies “constant” and “balanced” functions. The improvement took more than a decade to be discovered.

Let the initial state of the 2-qubit system be |Ψ〉 = |01〉 . When the Hadamard gate acts on it, we get

What has been cleverly accomplished is that by measuring the first qubit we may determine f(0) ⊕ f(1) which will tell us if f(0) = f(1) or not. In essence, just one evaluation of f(x) has allowed us to find a global property of f(x), namely, f(0)⊕ f(1). On the other hand, a classical computer would have required at least two evaluations. The Deutsch algorithm provided the first example that a quantum computer could do something that a classical computer cannot. It was simply brilliant in conception.

### 9.6 The Deutsch-Jozsa algorithm

The Deutsch-Jozsa algorithm5 solves a generalized Deutsch problem. Given a black box Uf whose action is to perform |x, y〉 |x, y ⊕ f(x)〉 for x ∈ {0, 1} n ≡{0,…,2n -1} and f(x)∈ {0, 1}, and that it is known beforehand that f is one of two kinds: either f(x) is constant for all values of x, or else f(x) is balanced, i.e., equal to 1 for exactly half of all possible x, and 0 for the other half. The significance of this problem is that a classical solution, in the worst-case, would require 2n-1 +1 evaluations of f before determining the answer with certainty since one may receive 2n/2 0s before finally getting a 1. Remarkably, the Deutsch-Jozsa algorithm requires only one evaluation of f. The reader is encouraged to see Table 9.1 where the algorithm is provided in summary form.

The Deutsch–Jozsa algorithm later inspired two revolutionary quantum algorithms, namely Shor’s factoring algorithm and Grover’s search algorithm, described in Section 10.

### 9.7 Computing f(x) in parallel

This is remarkable. The first term contains information about f(0) along with its input x = 0, and the second term contains information about f(1) along with its input x = 1. That is, the second qubit is in an equal superposition of f(0) and f(1), and the two values were calculated in parallel. This power of quantum algorithms comes from quantum parallelism and entanglement. So, most quantum algorithms begin by computing a function f(x) on a superposition of all values of x as follows:
Start with an n-qubit state |00…〉 and apply H to all the qubits to get

which is the superposition of all integers 0≤ x < 2n. Next, add a k-qubit register in state |00..0〉, large enough to hold the longest value of f(x). Then by linearity

Thus f(x) is computed in parallel for all values of x∈ {0,…, 2n -1}, provided one knows how to construct the appropriate Uf that will map a pair of qubit strings |x, 0〉 into the pair |x, f(x)〉. The output comes from the constructive interference of parallel computations.

The trick in constructing Uf is to break down the computation, corresponding to the function f(x), into a set of 1-qubit and 2-qubit unitary operations such that the state |x, 0 is mapped to the state |x, f(x)〉  for any input x. Note that the number of qubits required for the second register must be at least sufficient to store the longest result f(x) for any of these computations. In general, in designing quantum algorithms, one assumes that for reasonable functions, a suitable Uf can be built.

2 0 ⊕ 0 = 0, 0 ⊕ 1 = 1, 1 ⊕ 0 = 1, 1 ⊕ 1 = 1. See Sec. A.5.7 in Appendix A for a quick recall of modular arithmetic.
3Cleve, et al (1998).
4 Deutsch (1985).
5 Deutsch & Jozsa (1992).

Pages ( 2 of 14 ): « Previous1 2 34 ... 14Next »