1.12 Circuits
Consider the expression maximum(2, 1 + round(x)),
where maximum is the function we saw earlier in this chapter, and round
rounds a number to the nearest integer. For example, round(1.3) equals
1. Figure 1.10 shows how processing flows as we evaluate the
expression.
To fix terminology, we can call this a function application
circuit. When we draw it like this, we call maximum,
round, and “+” functions, operations, or
gates.
The maximum and “+” gates each take two
inputs and have one output. The round gate has one input and one output. In
general, round is not reversible: you cannot go from the output answer it
produced to its input.
Going to their lowest level, classical computer processors manipulate bits using logic operators. These are also called logic gates.
The simplest logic gate is not. It turns 0 into 1 and 1 into 0. If you think of Booleans instead of bits, not interchanges false and true. not is a reversible gate. not(x) means “not applied to the Boolean x.”
Exercise 1.13
What is the value of not(not(x)) when x equals each of 0 and 1?
The and gate takes two bits and returns 1 if they are both the same and 0 otherwise.
Exercise 1.14
What are the values for each of the following?
and(0,
0)
and(0, 1)
and(1, 0)
and(1, 1)
The or gate takes two bits and returns 1 if either is 1 and 0 otherwise. The xor gate takes two bits and returns 1 if one and only one bit is 1 and 0 otherwise. xor is short for “exclusive-or.”
Exercise 1.15
What are the values for each of the following?
xor(0,
0)
xor(0, 1)
xor(1, 0)
xor(1, 1)
Figure 1.11 is a diagram of a logic circuit with two logic gates that does simple addition.
Try it out with different bit values for a and b. Confirm that the sum s and the carry bit c are correct.
By analogy to the function application and logic cases, we also have quantum gates and circuits. These operate on and include one or more qubits.
This is a 2-qubit circuit containing one quantum X gate and four quantum H gates. Both X and H are reversible gates. We cover their definitions and uses later, but note that X interchanges the north and south poles in our qubit sphere model. The H gate moves the poles to locations on the equator of the sphere.
Coders who have done classical programming know that arithmetic and algebra are involved. When we bring in quantum computing, geometry also becomes useful!
The gates that look like dials on the right of the quantum circuit perform quantum measurements. These produce the final bit values.
There is one more gate in the circuit, and that is CNOT. It is an essential and core gate in quantum computing. It looks like a • on the horizontal line from qubit q0, a ⊕ on the q1 line, and a line segment between them. It has two inputs and two outputs. Unlike the logic gates and, or, and xor, it is a reversible gate.
Exercise 1.16
Written in functional form, CNOT has the following behavior.
CNOT(|0⟩,
|0⟩) = |0⟩, |0⟩
CNOT(|0⟩, |1⟩) = |0⟩, |1⟩
CNOT(|1⟩, |0⟩) = |1⟩, |1⟩
CNOT(|1⟩, |1⟩) = |1⟩, |0⟩
The gate has two outputs, which I separated with a comma. The first qubit input is called the control, and the second is the target.
In what way is CNOT a reversible xor?
Quantum gates and circuits are the low-level building blocks that will allow us to see significant advantages over classical methods alone. You will see qubits, quantum gates, and quantum circuits as we progress through this book. In Chapter 11, Searching for the Quantum Improvement, we focus on quantum algorithms and how they obtain their speed-ups.
