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 a large number of times, with the results of the computation extracted from a histogram of the measured outcomes.It is possible, however, for the outcome to be one particular state with probability 1. This is the case for Deutsch’s algorithm, for example. We know the answer for certain after one execution (assuming the quantum machine is error-free). So it’s not the case that a quantum algorithm must be probabilistic, but the most interesting algorithms tend to be that way.
Quantum parallelism: Arranging for the input state to be a superposition allows the calculation to consider multiple cases at once. However, it is not as easy to capitalize on this as it might sound. As indicated in the previous bullet, even though the output state may contain the complete solution, a single measurement will yield only one state with a probability given by the squared magnitude of the amplitude of the state in the solution of the problem.
Exponential scaling: The number of cases that can be considered scales as 2N, where N is the number of qubits. Beyond about 50 qubits, a general quantum processor cannot be simulated by a supercomputer; said differently, a processor with of order 50 or more qubits is capable of computations not possible on the best classical computers. However, if the quantum program is restricted to certain types of gates, then the operation of the quantum computer can be efficiently simulated by a classical computer.
Quantum interference: When multiple cases are considered using superposition, the goal of the quantum circuit is to arrange for the amplitudes of correct answer(s) to add constructively, while arranging for the incorrect answer(s) to add destructively.
Asking the right question: Although the output state of a quantum calculation will generally contain information about many possibilities, making a measurement collapses the state and therefore only gives a single result. In the Deutsch Problem, two classical function calls would not only tell you whether the function was constant or balanced, but it would tell you precisely what the function was. In contrast, the quantum calculation answers the question about whether the function is constant or balanced in one function call (which requires consideration of both cases), but it does not tell you which of the two possible functions it is.
1.10 Quantum Computing Systems
At this point, you may be asking: what kind of physical system exhibits the behavior that we can exploit for quantum computing? Any two-state quantum mechanical system can represent a qubit, and there are several possibilities, such as the spin of an electron, the polarization of a photon, or the energy level of an electron in a charged ion. Any of these systems can be used to build a quantum computer, but there are tradeoffs regarding how the qubits can be manufactured and controlled, and how they interact with one another.
In this book, we concentrate on one specific technology for creating qubits and quantum computing systems: superconducting circuits. Unlike many competing technologies, superconducting qubits are macroscopic in size and are based on well-known nanofabrication technologies. They represent the current technology of choice for several companies building quantum computer systems, including IBM, Google, and Rigetti.
A large part of this book, Chapters 2–8, is devoted to a detailed explanation of these devices and how to control them to carry out the fundamental operations of a quantum computer, described above. In this section, before diving into the details, we provide a high-level overview of a superconducting quantum computer.
As we will see in Chapter 2, we will need to couple the qubit to a signal whose frequency depends on the energy difference between the |0⟩ and |1⟩ states, i.e., the ground and excited states. In superconducting quantum computers, this energy difference corresponds to a microwave frequency near 5 GHz. Consequently, we must design a microwave system to control and measure superconducting qubit states.
The general features of the microwave system to control and readout superconducting qubits are shown in Figure 1.12. A key feature is that the qubits must be held at a very low temperature, near absolute zero. Consequently the qubits must be located in a cryogenic refrigerator. To understand why this is necessary, we want to make sure that if we put the qubit in the ground state, it stays in the ground state. In other words, we want to make sure that it is unable to absorb