To start laying the groundwork for understanding quantum computing, it can be helpful to know a little about how classical computing works.
Classical computers use bits to process and store information. Each bit represents either a 0 or a 1, which are both considered computational states. We use gates to manipulate these bits, and gates work together to create logical circuits.
A gate is represented with a symbol and is accompanied by a truth table, which is a table of values representing input and output.
Let’s look at some basic gates.
Gates
NOT Gate
The NOT gate flips a bit, so that a 0 becomes a 1 and a 1 becomes a 0.
Symbol:
In this image, A is the input and Q is the output.
Truth Table:
| Input A | Output Q |
|---|---|
| 0 | 1 |
| 1 | 0 |
The above table is read row by row. So the first row is saying if the input is 0, the output is 1 and the second row is saying that if the input is 1, the output is 0.
AND Gate
The AND gate takes in two inputs. If both the first input and the second input are 1 then the output is 1, otherwise the output is 0.
Symbol:
A and B are the inputs, Q is the output.
Truth Table:
| Input A | Input B | Output Q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR Gate
The OR gate takes in two inputs. If either of the inputs is 1, the output will be 1. Otherwise the output is 0.
Symbol:
Truth Table:
| Input A | Input B | Output Q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
XOR Gate
The XOR gate takes two inputs. If exactly one of the inputs is equal to 1, then the output is 1. Otherwise the output is 0.
The XOR gate is also useful because its truth table provides output for the following operation:
(Input A ⊕ Input B) % 2The ⊕ symbol in this case indicates binary addition. The % is for a modulo operation, which returns the remainder after one number has been divided by another.
You can also think of the output in the truth table as representing the 2^0 (aka the right-most) place of the result of Input A ⊕ Input B.
It’ll be more clear why these features of the XOR gate are important when we start looking at circuits.
Symbol:
Truth Table:
| Input A | Input B | Output Q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Now that we know these basic gates, we can start doing more complex operations by combining them to create circuits.
Circuits
Half adder
The half adder circuit is used to add two single-digit binary numbers together. The simplest version of it combines a XOR gate and an AND gate in order to do this.
In this circuit, C is the result of the AND gate, which only returns 1 if both A and B are 1. Output S is the result of the XOR gate, which outputs 1 if exactly one input is 1.
When you’re adding two digits together and you’re going place by place, if there is an overflow you’ll use a carry signal to keep track of that as you move to the next place. In this circuit, that “carry” is represented by C. The other output, S, is considered the “sum” output.
Diagram:
Truth Table:
| Input A | Input B | Output C | Output S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Notice that when we look at output C and output S together, they give us the binary number for the addition of the two inputs. For example, when Input A and Input B are both 1, the two outputs together are 10 which is the answer to Input A ⊕ Input B. Output C is the 2^1 place and Output S is the 2^0 place.
At this point we’re successfully doing addition, but only with two bits. To expand on that, we’ll look at the full adder.
Full adder
The full adder circuit is used to add three one-bit binary numbers together. To do this, you can use two half adders and one OR gate.
Truth Table:
| Input A | Input B | Input Cin | Output Cout | Output S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
You can think of a full adder as completing the following steps:
1. Use Input A and Input B as the inputs for the first half adder.
2. Use the sum output digit from step 1 (aka not the carry digit) and C(in) (the third one-bit input number) as the inputs for the second half adder. The sum output of the second half adder is the final sum output, Output S, in the truth table.
3. Use the carry from step 1 (the first half adder) and the carry from step 2 (the second half adder) as the inputs for the OR gate. This is Output C(out) (the final carry) in the truth table.
Many full adders can be combined to create a cascade of adders, thereby allowing you to add numbers with more and more bits. To add two n-bit binary numbers together, you need n applications of the full adder which means it runs in polynomial time.