right-angle minus Math bar pipe bar symblom 1 mathematical right-angle right-bracket EndLayout"/> (1.66)
Examining (1.67), we see that if f(0)=f(1) the second term vanishes and the output is |0⟩. In contrast, when f(0)≠f(1), then the first term vanishes and the output is ±|1⟩. Therefore, if we measure the output as |0⟩, we know that f(0)=f(1), while if we measure |1⟩, we know that is not the case. (Our measuring device will ignore the minus sign and show us a result of “1” if the output state is −|1⟩.)
Arranging for the amplitudes of the correct states to add and others to cancel is an example of quantum interference, another key principle underlying quantum computing. So we see that in a single function call, we are able to determine whether or not f(x) is balanced or constant—a feat that would only be possible classically with two function calls!
Now let us turn our attention to how the gate U can be realized. First, we have to confess that the circuit in Figure 1.8 is hiding something: we need another qubit to implement the U gate.
Consider the function f(x)=0. We want a unitary Uf that converts |x⟩ to |f(x)⟩, but this is clearly not reversible. Given an output of |0⟩, there’s no way to know whether the input is |1⟩ or |0⟩. To make the function reversible, we need to include both f(x) and x in the output, so that we can reconstruct the input when reversing the operation.
For two outputs, we need two inputs. We typically use |0⟩ as second input, but to be more general, let’s assume that the second input can be any input |y⟩. With |x⟩ and |y⟩ as the inputs, the outputs will be |x⟩ and |y ⊕ f(x)⟩, where ⊕ is the standard Boolean exclusive-OR (XOR) operation. As shown in Figure 1.9, this function is its own inverse; if we use |x⟩ and |y⊕f(x)⟩ as the input, we get |x⟩ and |y ⊕ f(x) ⊕ f(x)⟩ = |y⟩ as the output.
Figure 1.9 Reversible circuit for calculating f(x).
Figure 1.10 shows the four alternative implementations of Uf, depending on which version of f(x) we want. From left to right:
f1(x)=0, do nothing to y, equivalent to y⊕0.
f2(x)=1, flip y using a NOT gate, equivalent to y⊕1.
f3(x)=x, use a CNOT gate to flip y if x = 1, equivalent to y⊕x.
f4(x)=x¯, flip x and then XOR with y using a CNOT gate, equivalent to y⊕x¯. We then use another NOT gate to restore x to its original value.
Figure 1.10 Implementations of black-box function Uf for Deutsch’s problem. Top output is |y ⊕ f(x)⟩, and bottom output is |x⟩.
Now, using our Uf circuit, we will compute (−1)f(x)|x⟩ using a technique known as phase kickback. If we set |y⟩=|−⟩=(|0⟩−|1⟩)/2), then the top output of Uf will remain |−⟩ and the bottom output will be |x⟩ if f(x)=0 and will be −|x⟩ if f(x)=1. Let’s do the math.
First, consider what happens if we flip |−⟩ using the X gate:
In the cases where Uf flips |y⟩, we have:
It might seem that we “magically” moved the minus sign from one qubit to the other, but remember that this is really a two-qubit state, not two individual qubits. And −1 is just a constant, so we can associate it with either part of the two-qubit state.
Figure 1.11 shows the under-the-covers implementation of the circuit from Figure 1.8, where the dashed box replaces U. We add our ancilla qubit as part of this circuit. We typically assume that qubits are initialized in state |0⟩, so we use HX to create the desired |−⟩ state. Then we have our black-box function, Uf, which has the desired sign-flipping effect on |x⟩. Finally, it is good practice to “uncompute” the ancilla bit, restoring it |0⟩, so that the qubit can be used elsewhere in a larger circuit.
Figure 1.11 Implementation of Deutsch’s algorithm. The dashed box is equivalent to U in Figure 1.8.
If the notions of reversible logic and phase kickback seem strange, don’t worry. We’ll have a lot more to say about them in Chapters 11 and 12.
1.9 Key Characteristics of Quantum Computing
The Bell and Deutsch examples have illustrated several important characteristics of quantum computing:
Results are (usually) statistical: When a classical program is executed, you obtain the same result each time. However, when a quantum circuit is executed, multiple results are possible with probabilities determined by the magnitude squared of the amplitudes of each state. Consequently, in general a circuit must be executed
