Читать книгу Principles of Superconducting Quantum Computers - Daniel D. Stancil - Страница 28

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.

(1.64)

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

(1.65)

Applying the second Hadamard gate gives the final output:

(1.66)

(1.67)

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 U_f 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 U_f, 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 U_f 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 U_f 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:

(1.68)

In the cases where U_f flips |y⟩, we have:

(1.69)

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, U_f, 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.