2nd Column equals StartFraction Math bar pipe bar symblom alpha mathematical right-angle plus Math bar pipe bar symblom beta mathematical right-angle Over StartRoot 2 EndRoot EndFraction circled-times StartFraction Math bar pipe bar symblom alpha mathematical right-angle plus Math bar pipe bar symblom beta mathematical right-angle Over StartRoot 2 EndRoot EndFraction 3rd Row 1st Column 2nd Column equals one-half left-parenthesis Math bar pipe bar symblom alpha alpha mathematical right-angle plus Math bar pipe bar symblom alpha beta mathematical right-angle plus Math bar pipe bar symblom beta alpha mathematical right-angle plus Math bar pipe bar symblom beta beta mathematical right-angle right-parenthesis period EndLayout"/> (1.60)
However, by the linearity of unitary operators:
Since Eqs. (1.60) and (1.61) cannot both be true, there is no unitary Uclone that can perform the cloning operation for all states.
We stated earlier that we can clone a (computational) basis state. This can be done with the CNOT gate, with the first qubit as the control. (With our bottom-to-top ordering, this corresponds to the UCN′ operator from (1.52).) Suppose state |ψ⟩ is either |0⟩ or |1⟩, but we don’t know which.
If we apply the circuit from Figure 1.5 to an arbitrary state |ψ⟩ = α|0⟩ + β|1⟩, we get a result that looks sort of like cloning, but not quite:
The result is not cloning because the two qubits are entangled. We did not succeed in creating two independent copies of |ψ⟩. This is a useful construct, however, and can be extended to create n-qubit states that look like this:
These states will be useful for quantum error correction codes (Chapter 10).
1.8 Example: Deutsch’s Problem
We now have enough quantum computing “machinery” to work out a simple example of a quantum algorithm. The example algorithm is admittedly not very useful, but it provides some important insights into how quantum computers can outperform classical computers.
Consider a function that takes a single binary digit as input, and provides a single binary digit as output. There are four possible functions: f1(x)=0, f2(x)=1, f3(x)=x, and f4(x)=x¯. Suppose someone gave us an implementation of one of these functions in a black box, and asked us to determine whether f(0)=f(1), or if f(0)≠f(1). Classically, we could do this in two function calls, one with x = 0, and one with x = 1. However, using a quantum algorithm we can answer this question with a single function call! Let’s see how this could be done.
First, suppose that we have the gate U shown in Figure 1.8(a) for implementing the function f(x). The function is implemented by changing the sign of the state: if f(x)=0 then the sign is unchanged, and if f(x)=1 then the sign of the state is flipped. We will return to the question of how to implement this gate shortly, but for now let us assume that the gate is given to us, and our job is to determine if f(0)=f(1) or f(0)≠f(1). Now consider the circuit shown in Figure 1.8(b). Applying the Hadamard gate to the input |0⟩ gives
Figure 1.8 Conceptual illustration of the Deutsch Problem.
Note that the Hadamard gate enables us to apply U to both |0⟩ and |1⟩ at the same time. This is referred to as quantum parallelism and is one of the secrets behind the power of quantum computing (although there are some key qualifications that make this somewhat less exciting than it would seem at first!).
Continuing with the calculation, we next compute ψ2=Uψ1 to obtain
Applying the second Hadamard gate gives the final output:
