WEBVTT

1
00:00:00.180 --> 00:00:04.255
Can four pieces build any two-input rule?

2
00:00:04.255 --> 00:00:11.744
Exclusive-or accepts two input pairs, so we will start
by building its matrix one accepting position at a time.

3
00:00:11.744 --> 00:00:16.283
You will learn how a column and a row create a single-position basis matrix,

4
00:00:16.283 --> 00:00:20.555
then how those pieces combine into a complete operator C M.

5
00:00:20.735 --> 00:00:26.795
Ket one is a column containing one above zero. Ket zero contains zero above one.

6
00:00:26.795 --> 00:00:30.859
The vertical arrangement matters: these are columns with two entries.

7
00:00:30.859 --> 00:00:35.212
Their names tell us which input state they select in our true-first ordering.

8
00:00:35.392 --> 00:00:38.132
Transpose a column and it becomes a row.

9
00:00:38.132 --> 00:00:43.298
We call that row a bra. Bra zero contains zero followed by one.

10
00:00:43.298 --> 00:00:50.241
The angled brackets are names for these vectors; we are
still doing a concrete calculation with zeros and ones.

11
00:00:50.421 --> 00:00:56.632
Multiply ket one by bra zero. Every column entry multiplies every row entry.

12
00:00:56.632 --> 00:01:03.296
The first row becomes zero, one. The second becomes zero, zero.

13
00:01:03.296 --> 00:01:08.427
This is an outer product: a column times a row produces a matrix.

14
00:01:08.607 --> 00:01:12.938
Choosing either ket and either bra gives four possible pieces.

15
00:01:12.938 --> 00:01:18.998
Each contains exactly one one. Its ket chooses the row and its bra chooses the column.

16
00:01:18.998 --> 00:01:24.338
These four single-position matrices are the basis pieces for our two-input operators.

17
00:01:24.518 --> 00:01:30.729
Choose the top-right piece and the bottom-left piece. Combine their entries with exclusive-or.

18
00:01:30.729 --> 00:01:34.944
Because their ones occupy different cells, both ones remain.

19
00:01:34.944 --> 00:01:41.767
We have reconstructed the complete exclusive-or matrix from its two accepting input pairs.

20
00:01:41.947 --> 00:01:48.100
Try building ket zero times bra one. Which row does
the ket choose, and which column does the bra choose?

21
00:01:48.100 --> 00:02:00.337
Decide where the single one will appear. The other entries must all be zero.

22
00:02:00.517 --> 00:02:06.635
Ket zero chooses the bottom row. Bra one chooses
the first column, so the one belongs at the lower left.

23
00:02:06.635 --> 00:02:14.205
The paper names this operator with a downward double
arrow. Its matrix accepts left input false and right input true.

24
00:02:14.385 --> 00:02:17.822
An outer product makes a matrix from a column and a row.

25
00:02:17.822 --> 00:02:23.406
In the next lesson, we place a row on the left of an existing C M and a column on its right.

26
00:02:23.406 --> 00:02:29.001
We will compute the resulting single bit, showing every AND and exclusive-or.