Tensor products, CNOT and reversible logic

1 / 15 · Learn

Before you start

Every lesson so far has used one qubit. This one puts several together, first as ordinary bits and then in superposition, and adds gates that act on two or three of them at once.

By the end of this lesson you can:

write a multi-qubit product state as a column vector in this course’s order, top qubit first;
say how many amplitudes $n$ qubits need, and how many bits one measurement returns;
find the odds and the leftover state when you measure one qubit of two;
apply CNOT and Toffoli to basis states, and read a circuit’s time order against its operator order;
explain why AND can’t be a quantum gate as it stands, and how Toffoli gets around that.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

A general state of three qubits: how many complex amplitudes does it take to write down, and how many bits do you get when you measure all three qubits in the 0/1 basis?

A8 amplitudes; 8 bits
B3 amplitudes; 3 bits
C8 amplitudes; 3 bits
D6 amplitudes; 3 bits

Show the answer

Answer: C. 8 amplitudes; 3 bits

Each of the $2^{3} = 8$ strings is a basis state with its own amplitude, but one measurement picks out one string: 3 bits.

Why not the others

A. A common idea is that every amplitude gets read out. One shot of the measurement returns one 3-bit string, so 3 bits. The 8 amplitudes set the odds of the 8 possible strings; they never come out as data.
B. One number per qubit would describe a classical register, where each bit has a definite value. A quantum register gives an amplitude to every string: $2^{3} = 8$ numbers. Even one qubit needs two, $\alpha$ and $\beta$ .
D. Adding 2 per qubit treats the qubits as separate lists. The basis states are the strings 000 to 111, and there are $2^{3} = 8$ of them, each with its own amplitude. Dimensions multiply under $\tp$ .

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

Every quantum gate is reversible. Can a quantum computer compute $\mathrm{AND}(a, b)$ of two bits?

ANo. AND is irreversible, so quantum circuits cannot compute it.
BYes. Apply an AND gate to the two qubits, as in a classical chip.
COnly approximately: the answer comes out right with some probability below 1.
DYes, if the circuit keeps $a$ and $b$ and writes the answer into an extra bit.

Show the answer

Answer: D. Yes, if the circuit keeps $a$ and $b$ and writes the answer into an extra bit.

Keep $a$ and $b$ and write the answer into a third bit: $(a, b, c)\mapsto(a, b, c\oplus \mathrm{AND}(a, b))$ is a permutation of the eight strings. That is exactly the Toffoli gate. With $c = 0$ the third bit ends up holding $\mathrm{AND}(a, b)$ .

Why not the others

A. This takes "gates must be reversible" one step too far. The function AND can still be computed: keep $a$ and $b$ and XOR the answer into an extra bit, $(a, b, c)\mapsto(a, b, c\oplus \mathrm{AND}(a, b))$ . That is a permutation of bit strings, so it is reversible. Only a gate that throws its inputs away is ruled out.
B. A classical AND gate turns two bits into one and loses information: three of its four inputs (00, 01, 10) all give 0. A quantum gate is unitary, so it must be undoable, and no rule can undo a collision like that. Classical chips may lose information; quantum gates may not.
C. Nothing random is needed. On basis-state inputs a reversible circuit is a permutation of bit strings and gives the answer with certainty. Randomness only enters if you feed in superpositions and then measure.

2 / 15 · Learn

Part A · Bits as vectors

Refresher: Tensor products Kronecker products of vectors, if you want a refresher first.

Start with ordinary bits. Write a bit that is 0 as $\ket0 = \begin{bmatrix}1\\0\end{bmatrix}$ and a bit that is 1 as $\ket1 = \begin{bmatrix}0\\1\end{bmatrix}$ . A pair of bits $x, y$ becomes the tensor product $\ket x\tp\ket y$ , also written $\ket x\ket y$ or $\ket{xy}$ . To build it, multiply each entry of the first column by the whole second column, and stack the results:

\ket1\tp\ket0 = \begin{bmatrix}0\\1\end{bmatrix}\tp\begin{bmatrix}1\\0\end{bmatrix} = \begin{bmatrix}0\cdot1\\0\cdot0\\1\cdot1\\1\cdot0\end{bmatrix} = \begin{bmatrix}0\\0\\1\\0\end{bmatrix}.

This column is $\ket{10}$ . The four slots are labelled 00, 01, 10, 11: binary counting, with the first label (the top wire of a circuit) as the most significant bit. A definite string of bits always gives a single 1, in the slot named by that string.

Check yourself

Write $\ket0\tp\ket1$ as a column vector, slots in the order 00, 01, 10, 11.

Hints

Read the factors left to right, first factor first: which two-bit string do they spell?
They spell 01. Which entry of the column is slot 01, counting 00, 01, 10, 11?
Slot 01 is the second entry: put the 1 there and 0 everywhere else.

Show the answer

Answer: $|01\rangle$

Top entry of $\ket0$ is 1, so the first half is $\ket1 = (0, 1)$ and the second half is $0\cdot\ket1$ : $(0, 1, 0, 0) = \ket{01}$ .

Check yourself

Three bits in the state $\ket{110} = \ket1\tp\ket1\tp\ket0$ give a column of 8 entries, with slots 000, 001, …, 111 in binary order. Where is the 1?

AIn the 6th entry, slot 101
BIn the 4th entry, slot 011
CIn the 7th entry, slot 110
DThe column has only 3 entries: 1, 1, 0

Show the answer

Answer: C. In the 7th entry, slot 110

Slots run 000, 001, 010, 011, 100, 101, 110, 111. The string 110 is binary for 6, so the 1 is in slot 6, the 7th entry.

Why not the others

A. Binary 110 is 6, but the slots start at 000 = 0, so slot 6 is the 7th entry; the 6th entry is slot 101. Read the slot label rather than counting positions.
B. That reads the string from the right. The first label, the top wire, is the most significant bit, so $\ket{110}$ sits in slot 110. That is binary for 6, the 7th entry when you start counting at slot 000.
D. Three bits need $2\times2\times2 = 8$ slots, one for each string 000 … 111, not one slot per bit. A definite string puts a single 1 in its own slot and 0 everywhere else.

3 / 15 · Learn

Part A · Superposed factors: the ⊗ grid

Nothing changes when the factors are superpositions. If the top qubit is $a_0\ket0 + a_1\ket1$ and the bottom one is $b_0\ket0 + b_1\ket1$ , expanding the product term by term gives

\begin{aligned} &(a_0\ket0+a_1\ket1)\tp(b_0\ket0+b_1\ket1)\\ &\quad= a_0b_0\ket{00}+a_0b_1\ket{01}\\ &\qquad+a_1b_0\ket{10}+a_1b_1\ket{11}. \end{aligned}

Each amplitude is the top qubit’s amplitude for the first label times the bottom qubit’s amplitude for the second label: $\alpha_{xy} = a_x b_y$ . Products, never sums. The basis states that appear do not change; only the amplitudes do.

Check yourself

Write $\ket+\tp\ket1$ as a column vector (order 00, 01, 10, 11).

Hints

Which basis states have bottom label 1?
Each amplitude is (top amplitude) × (bottom amplitude) for that slot’s two labels.
The bottom factor $\ket1$ has $b_0 = 0$ , so slots 00 and 10 are 0.

Show the answer

Answer: $\frac{1}{\sqrt{2}}|01\rangle + \frac{1}{\sqrt{2}}|11\rangle$

$\tfrac{1}{\sqrt2}(\ket0+\ket1)\ket1 = \tfrac{1}{\sqrt2}(\ket{01}+\ket{11})$ : the entries are $(0, \tfrac{1}{\sqrt2}, 0, \tfrac{1}{\sqrt2})$ .

Check yourself

The top qubit is in $\tfrac{\sqrt3}{2}\ket0 + \tfrac12\ket1$ and the bottom qubit in $\tfrac{1}{\sqrt2}(\ket0 - i\ket1)$ . What is the amplitude of $\ket{01}$ in the two-qubit state?

$\alpha_{01} = \;?$

Hints

Which factor supplies the first label, 0, and which supplies the second, 1?
For a product state, $\alpha_{xy} = a_x b_y$ .
Multiply $\tfrac{\sqrt3}{2}$ by $-\tfrac{i}{\sqrt2}$ .

Show the answer

Answer: $\alpha_{01} = -\frac{\sqrt{6}}{4}\,i$

$\alpha_{01} = a_0 b_1 = \tfrac{\sqrt3}{2}\cdot\left(-\tfrac{i}{\sqrt2}\right) = -\tfrac{i\sqrt6}{4} \approx -0.612i$ .

Common slips

$\frac{\sqrt{2}}{4}$ : That is $a_1 b_0$ , the amplitude of $\ket{10}$ . In $\ket{01}$ the first label belongs to the top qubit: you need the top qubit’s $\ket0$ amplitude times the bottom qubit’s $\ket1$ amplitude.
$\frac{\sqrt{3}}{2}-\frac{1}{\sqrt{2}}i$ : Adding the two amplitudes treats the qubits as separate lists. In a product state they multiply: $\tfrac{\sqrt3}{2}\times\left(-\tfrac{i}{\sqrt2}\right)$ . A quick check: a sum like this has size above 1, and no amplitude can.
$-\frac{\sqrt{6}}{4}$ : Right size, but the $-i$ from the bottom factor went missing. The bottom qubit’s $\ket1$ amplitude is $-i/\sqrt2$ , and the whole factor carries into the product.

4 / 15 · Learn

Part A · 2ⁿ amplitudes, n bits out

Each qubit you add doubles the list of basis strings: 2 for one qubit, 4 for two, $2^n$ for $n$ . A general $n$ ⁠-qubit state needs one complex amplitude per string. Most states are not products, so you cannot shrink the list to two numbers per qubit (Lesson 7 shows why). Take $n = 500$ : $2^{500}$ is roughly $10^{150}$ , far more numbers than there are atoms in the observable universe.

Measurement does not read that list out. Measuring all $n$ qubits in the 0/1 basis returns one $n$ ⁠-bit string $x$ , with probability $\abs{\alpha_x}^2$ , and leaves the register in $\ket{x}$ . You get $n$ bits per run, never $2^n$ numbers.

Check yourself

A register has 10 qubits. How many complex amplitudes does a general state of it need?

Hints

How many 10-bit strings are there?
Each added qubit doubles the number of basis states.
Compute $2^{10}$ .

Show the answer

Answer: $1024$

$2^{10} = 1024$ : one amplitude for each 10-bit string.

Common slips

$20$ : That is 2 per qubit, added up. Dimensions multiply: the basis states are the 10-bit strings, each with its own amplitude. How many 10-bit strings are there?
$10$ : One number per qubit would do for a classical register. A quantum state gives an amplitude to every 10-bit string, and each added qubit doubles the number of strings.
$100$ : That is $10^2$ . Each added qubit doubles the number of basis strings, rather than adding to it or squaring it: one qubit has 2, two have 4, three have 8.

Check yourself

You measure all 10 qubits of that register in the 0/1 basis, once. How many bits of output do you get?

Hints

What does one shot of the figure above return: eight numbers, or something shorter?
Measuring one qubit in the 0/1 basis gives one bit, 0 or 1.
One bit from each of the ten qubits.

Show the answer

Answer: $10$

One run returns one 10-bit string. The 1024 amplitudes set the odds of each string.

Common slips

$1024$ : That counts amplitudes, not output. One measurement returns one 10-bit string, such as 0110100011. The 1024 amplitudes decide how likely each string is, but they never come out as data.
$1$ : One bit per qubit, not one in total: measuring all 10 qubits gives a 10-bit string.

5 / 15 · Learn

Part A · Measuring one qubit of two

You can also measure just one qubit. Lay the four amplitudes out as a $2\times2$ grid, rows for the top qubit and columns for the bottom one. Measuring the top qubit in the 0/1 basis gives 0 with probability $\abs{\alpha_{00}}^2 + \abs{\alpha_{01}}^2$ , the total of row 0. If you get 0, row 1 is wiped out and row 0 is rescaled so the state is normalized again:

\ket{\psi'} = \frac{\alpha_{00}\ket{00} + \alpha_{01}\ket{01}}{\sqrt{\abs{\alpha_{00}}^2 + \abs{\alpha_{01}}^2}}.

For the bottom qubit, use columns instead of rows.

Check yourself

Take $\ket\psi = \tfrac12\ket{00} + \tfrac{i}{\sqrt2}\ket{01} + \tfrac12\ket{10}$ . You measure only the top qubit, in the 0/1 basis. What is the probability that it gives 0?

$P(\text{top} = 0) = \;?$

Hints

Which two basis states have the top (first) label equal to 0?
Add $\abs{\alpha}^2$ over that row.
$\abs{\tfrac12}^2 + \abs{\tfrac{i}{\sqrt2}}^2 = \tfrac14 + \ldots$

Show the answer

Answer: $P(\text{top} = 0) = \frac{3}{4}$

Row 0: $\abs{\tfrac12}^2 + \abs{\tfrac{i}{\sqrt2}}^2 = \tfrac14 + \tfrac12 = \tfrac34$ .

Common slips

$-\frac{1}{4}$ : A probability can’t be negative. Squaring $\tfrac{i}{\sqrt2}$ itself brings in $i^2 = -1$ . A probability uses the squared size, $\abs{\alpha}^2 = \alpha\alpha^*$ , which is never negative. Redo the sum with squared sizes.
$\frac{1}{4}$ : $\tfrac14$ is the other row, $\abs{\alpha_{10}}^2$ (the top qubit giving 1), or $\abs{\alpha_{00}}^2$ on its own. For 0 you need both entries of row 0: $\abs{\alpha_{00}}^2 + \abs{\alpha_{01}}^2$ .
$\frac{1}{2}$ : That adds a column, $\abs{\alpha_{00}}^2 + \abs{\alpha_{10}}^2$ , which belongs to the bottom qubit. The top qubit is the first label, so add the row: $\abs{\alpha_{00}}^2 + \abs{\alpha_{01}}^2$ .

Check yourself

The top qubit gave 0. What is the two-qubit state now?

Hints

Which entries are wiped out by the result 0?
Keep row 0 and divide by $\sqrt{P} = \sqrt{3/4}$ .

Show the answer

Answer: $\frac{1}{\sqrt{3}}|00\rangle + \frac{2}{\sqrt{6}}\,i|01\rangle$

Keep row 0 and divide by $\sqrt{3/4} = \tfrac{\sqrt3}{2}$ : $\tfrac{1}{\sqrt3}\ket{00} + i\sqrt{\tfrac23}\,\ket{01}$ . Check: $\tfrac13 + \tfrac23 = 1$ .

6 / 15 · Learn

Part B · CNOT: XOR that keeps its input

Refresher: Bits, XOR and bit strings XOR and bit strings, if $\oplus$ is new to you.

The basic two-qubit gate is the controlled-NOT, or CNOT. It has a control qubit (top wire, drawn •) and a target qubit (drawn ⊕). On basis states it flips the target exactly when the control is 1:

\ket{A, B}\ \to\ \ket{A,\ B\oplus A},

where $\oplus$ is addition mod 2 (XOR). So $\ket{10}\to\ket{11}$ and $\ket{11}\to\ket{10}$ , while $\ket{00}$ and $\ket{01}$ stay put. Classical XOR turns two bits into one. CNOT keeps $A$ as well, and that is why it can be undone: apply it twice and $B\oplus A\oplus A = B$ .

Check yourself

Which matrix is $U_{CN}$ (control on top) in the basis order 00, 01, 10, 11? Column $k$ is the image of the $k$ ⁠-th basis state.

A $\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$
B $\begin{bmatrix}0&1&0&0\\1&0&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}$
C $\begin{bmatrix}1&0&0&0\\0&0&0&1\\0&0&1&0\\0&1&0&0\end{bmatrix}$
D $\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&-1\end{bmatrix}$

Show the answer

Answer: A. $\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$

$\ket{00}$ and $\ket{01}$ map to themselves; $\ket{10}\mapsto\ket{11}$ and $\ket{11}\mapsto\ket{10}$ , so the last two columns of the identity are exchanged.

Why not the others

B. This swaps $\ket{00}$ and $\ket{01}$ , so it flips the bottom bit when the top bit is 0. CNOT acts when the control is 1, so the first two slots stay put.
C. This one swaps $\ket{01}$ and $\ket{11}$ : it flips the top bit when the bottom bit is 1. That is CNOT with control and target exchanged. With the control on top, the pair that trades places is $\ket{10}$ and $\ket{11}$ , the last two slots.
D. This only changes the sign of $\ket{11}$ (it is the controlled- $Z$ gate) and moves nothing. CNOT moves basis states: $\ket{10}$ and $\ket{11}$ trade places, so its matrix has 1s off the diagonal.

Check yourself

Now put the control on the bottom wire and the ⊕ on the top wire. What does this CNOT do to $\ket{01}$ ?

A $\ket{10}$
B $\ket{11}$
C $\ket{00}$
D $\ket{01}$ , unchanged

Show the answer

Answer: B. $\ket{11}$

The control is the bottom bit, which is 1, so the top (target) bit flips: $\ket{01}\to\ket{11}$ .

Why not the others

A. That exchanges the two bits. One CNOT changes only its target bit. Exchanging two bits takes three CNOTs, as the next segment shows.
C. That flips the control. On a basis input a CNOT never changes its control bit; it flips the target bit, and only when the control bit is 1.
D. That treats the top bit as the control. Here the control is the bottom bit, and in $\ket{01}$ the bottom bit is 1, so the top bit flips.

7 / 15 · Learn

Part B · Time order and operator order

Reading a circuit takes three conventions. Each wire is a qubit, and the top wire is the first label. Time runs left to right. But when you write the circuit as operators, the order reverses: a circuit that applies $A$ and then $B$ is the operator $BA$ , because the matrix written next to the ket acts first. A one-qubit gate $U$ on the top wire of two is $U\tp I$ ; on the bottom wire it is $I\tp U$ .

Check yourself

A two-qubit circuit applies $U_{CN}$ (control on top) first and then $X$ on the top wire. Which operator does the whole circuit apply?

A $U_{CN}\,(X\tp I)$
B $(X\tp I)\,U_{CN}$
C $U_{CN} + X\tp I$
D $(I\tp X)\,U_{CN}$

Show the answer

Answer: B. $(X\tp I)\,U_{CN}$

Time runs left to right, but operators act right to left: the first gate sits next to the ket. $X$ on the top wire is $X\tp I$ , so the circuit is $(X\tp I)U_{CN}$ .

Why not the others

A. That is the circuit order written left to right. The matrix next to the ket acts first, so the first gate goes on the right. You can check that the two differ: on $\ket{00}$ , $(X\tp I)U_{CN}$ gives $\ket{10}$ , while $U_{CN}(X\tp I)$ gives $\ket{11}$ .
C. Gates in sequence multiply; they never add. A sum of two unitaries is usually not even unitary.
D. $I\tp X$ acts on the bottom wire. The first factor of a tensor product belongs to the top wire, so $X$ on the top wire is $X\tp I$ .

Three CNOTs, the middle one upside down (control on the bottom), swap two qubits. Follow the bits:

\ket{a,b}\to\ket{a,\ a\oplus b}\to\ket{b,\ a\oplus b}\to\ket{b,\ a}.

The middle CNOT XORs the bottom bit into the top one, and $a\oplus(a\oplus b) = b$ . The last CNOT XORs the new top bit into the bottom one: $(a\oplus b)\oplus b = a$ .

Check yourself

Trace $\ket{10}$ through the swap circuit: CNOT (control top), then CNOT (control bottom), then CNOT (control top). Which list gives the state after each gate?

A $\ket{11}$ , then $\ket{01}$ , then $\ket{00}$
B $\ket{01}$ , then $\ket{01}$ , then $\ket{01}$
C $\ket{11}$ , then $\ket{01}$ , then $\ket{01}$
D $\ket{11}$ , then $\ket{10}$ , then $\ket{11}$

Show the answer

Answer: C. $\ket{11}$ , then $\ket{01}$ , then $\ket{01}$

$\ket{10}\to\ket{11}$ (top is 1, flip the bottom) $\to\ket{01}$ (bottom is 1, flip the top) $\to\ket{01}$ (top is 0, nothing). The bits have traded places: 10 became 01.

Why not the others

A. In the last step the control (top) bit is 0, so nothing happens and $\ket{01}$ stays $\ket{01}$ . A CNOT acts on its target only when its control bit is 1.
B. A single CNOT can’t swap: it changes only its target bit. The first CNOT turns $\ket{10}$ into $\ket{11}$ ; the swap is complete only after all three.
D. That runs the middle CNOT with its control still on top. In the swap circuit the middle CNOT is flipped: the bottom bit controls and the top bit is the target, so $\ket{11}\to\ket{01}$ .

Check yourself

Build the swap yourself, using only CNOTs. Click a wire to place a CNOT with its control there; click a placed CNOT to flip its direction. The truth table shows what your circuit does to each basis input.

Build it in the circuit builder (gates: CNOT).

Hints

How many CNOTs does the swap use, and which one is upside down?
Control on top, then control on the bottom, then control on top again.

Show the answer

One circuit that works: CNOT q0→q1, then CNOT q1→q0, then CNOT q0→q1.

CNOT (control top), CNOT (control bottom), CNOT (control top): every input $\ket{ab}$ comes out as $\ket{ba}$ . Starting with the control on the bottom works too, since the circuit is symmetric.

8 / 15 · Explore

Part B · Can the control qubit change?

Predict, then see

So far CNOT has only ever flipped its target. Now feed it superpositions: control $\ket+$ on top, target $\ket-$ below. Predict the output.

A $\ket-\ket-$ : the control changes and the target does not.
B $\ket+\ket+$ : the control is partly 1, so the target flips.
CAn entangled state: CNOT on a superposition always entangles.
D $\ket+\ket-$ : the control never changes, and a $\ket+$ control is not definitely 1.

In a sentence or two: a CNOT only ever applies $X$ to its target. Why did the control change here?

Show what happens

What happens: A. $\ket-\ket-$ : the control changes and the target does not.

Write the control in the 0/1 basis: $\tfrac{1}{\sqrt2}(\ket0\ket- + \ket1\ket-)$ . CNOT leaves the first term alone and applies $X$ to the target in the second, and $X\ket- = -\ket-$ . The result is $\tfrac{1}{\sqrt2}(\ket0 - \ket1)\ket- = \ket-\ket-$ : the target is untouched and the control picked up the sign. “The control never changes” is guaranteed only when the control is in a basis state.

Why not the others

B. Flipping $\ket-$ does not give $\ket+$ : $X\ket- = -\ket-$ , the same state with a sign. Where that sign ends up is the whole story.
C. CNOT can entangle (Lesson 7 shows how), but not always. Here the output factors as $\ket-\ket-$ , one state for each qubit.
D. The rule “the control never changes” comes from the truth table, which lists basis inputs only. Expand the input in the 0/1 basis and apply CNOT term by term, and a minus sign lands on the control’s $\ket1$ term.

Why a sign can change the control (open after the experiment)

For a basis-state control the sign is harmless: $U_{CN}\ket1\ket- = -\ket1\ket-$ , which differs from $\ket1\ket-$ only by a global phase. In a superposition the sign multiplies only the $\ket1$ branch, so it becomes a relative phase between the control’s $\ket0$ and $\ket1$ , and that turns $\ket+$ into $\ket-$ . This effect is called phase kickback. Lesson 7 builds on it: which targets kick a sign back, which leave the control alone, and which entangle the pair. Deutsch’s algorithm (Lesson 9) runs on it.

Check yourself

Same CNOT (control on top), new input: control $\ket-$ , target $\ket-$ . What comes out?

A $\ket+\ket+$
B $\ket-\ket+$
C $\ket-\ket-$ , unchanged
D $\ket+\ket-$

Hints

Write the control $\ket-$ in the 0/1 basis first.
Only the control’s $\ket1$ term gets $X$ on the target, and $X\ket- = -\ket-$ .

Show the answer

Answer: D. $\ket+\ket-$

Expand the control: $\tfrac{1}{\sqrt2}(\ket0 - \ket1)\ket-$ . CNOT turns the second term into $-\ket1(-\ket-) = +\ket1\ket-$ , giving $\tfrac{1}{\sqrt2}(\ket0 + \ket1)\ket- = \ket+\ket-$ .

Why not the others

A. Only one thing changes. The target stays $\ket-$ , because $X$ only multiplies it by $-1$ ; that $-1$ is what flips the control.
B. The target $\ket-$ is not flipped to $\ket+$ : $X\ket- = -\ket-$ . The sign lands on the control’s $\ket1$ term instead.
C. The control changes here too. Term by term: $\tfrac{1}{\sqrt2}(\ket0\ket- - \ket1\ket-)\to\tfrac{1}{\sqrt2}(\ket0\ket- + \ket1\ket-)$ , because $X\ket- = -\ket-$ flips the sign of the second term. That is $\ket+\ket-$ .

9 / 15 · Worked example

Part B · Worked example: CNOT shuffles slots

Worked example

CNOT on a product state, slot by slot

CNOT only moves basis states around, so on a column vector it just shuffles entries. Here it acts on $\ket1\tp\left(\tfrac35\ket0 + \tfrac45\ket1\right)$ , control on top.

Build the vector
The top factor is $(0, 1)$ , the bottom factor $(\tfrac35, \tfrac45)$ . The top qubit’s $\ket0$ amplitude is 0, so slots 00 and 01 are 0; its $\ket1$ amplitude is 1, so slots 10 and 11 copy the bottom factor: $\left(0,\ 0,\ \tfrac35,\ \tfrac45\right)$ .
Shuffle
$U_{CN}$ fixes $\ket{00}$ and $\ket{01}$ and exchanges $\ket{10}\leftrightarrow\ket{11}$ . So the amplitude in slot 10 moves to slot 11 and the one in slot 11 moves to slot 10: $\left(0,\ 0,\ \tfrac45,\ \tfrac35\right)$ .
Read it back
That is $\ket1\tp\left(\tfrac45\ket0 + \tfrac35\ket1\right)$ . With the control definitely 1, the target simply got an $X$ . Multiplying by the matrix $U_{CN}$ gives the same result; the shuffle is a faster way to do that product.
Your turn
Now the control is the bottom wire and the ⊕ is on the top wire. The input is $\left(\tfrac{\sqrt3}{2}\ket0 + \tfrac12\ket1\right)\tp\ket1$ .
Your turn
Build the input vector, decide which slots this CNOT exchanges, and enter the output (order 00, 01, 10, 11).
Hints
1. Which basis states have the control (bottom) bit equal to 1?
2. Those states get their top bit flipped: $\ket{01}\leftrightarrow\ket{11}$ .
Show the answer
Answer: $\frac{1}{2}|01\rangle + \frac{\sqrt{3}}{2}|11\rangle$
Input $(0, \tfrac{\sqrt3}{2}, 0, \tfrac12)$ . Exchanging slots 01 and 11 gives $(0, \tfrac12, 0, \tfrac{\sqrt3}{2}) = \left(\tfrac12\ket0 + \tfrac{\sqrt3}{2}\ket1\right)\tp\ket1$ : the top qubit got an $X$ .

Here is one more worked example, with the control on the bottom wire.

Another worked example

Control on the bottom wire

Build the vector
Input $\left(\tfrac35\ket0 + \tfrac45\ket1\right)\tp\ket1$ . The bottom factor is $\ket1$ , so only slots whose second label is 1 are nonzero: slot 01 gets $\tfrac35\cdot1$ and slot 11 gets $\tfrac45\cdot1$ . The vector is $\left(0,\ \tfrac35,\ 0,\ \tfrac45\right)$ .
Shuffle
With the control on the bottom wire, a basis state has its top bit flipped when its bottom bit is 1: $\ket{01}\leftrightarrow\ket{11}$ , while $\ket{00}$ and $\ket{10}$ stay. Exchange entries 2 and 4: $\left(0,\ \tfrac45,\ 0,\ \tfrac35\right)$ .
Read it back
That is $\left(\tfrac45\ket0 + \tfrac35\ket1\right)\tp\ket1$ : the top qubit got an $X$ , because its control was definitely 1.

Check yourself

A CNOT with its control on the top wire acts on $\ket1\tp\left(\tfrac12\ket0 - \tfrac{\sqrt3}{2}\ket1\right)$ . Enter the output vector in the order 00, 01, 10, 11.

Hints

Which bit is the control, and in which slots is it 1?
Those slots trade places in pairs that differ only in the target bit.

Show the answer

Answer: $-\frac{\sqrt{3}}{2}|10\rangle + \frac{1}{2}|11\rangle$

The input vector is $\left(0,\ 0,\ \tfrac12,\ -\tfrac{\sqrt3}{2}\right)$ . The control on top exchanges slots 10 and 11, giving $\left(0,\ 0,\ -\tfrac{\sqrt3}{2},\ \tfrac12\right)$ : the target qubit got an $X$ .

10 / 15 · Learn

Part B · Gates must be reversible

Every quantum gate is unitary, and a unitary always has an inverse, $U^\dagger$ . So a gate can never send two different inputs to the same output: if it did, nothing could tell them apart afterwards to undo it. On basis states, then, a reversible classical gate must be a permutation: each input string goes to its own output string, with as many bits out as in.

NOT, CNOT and swap pass this test. Classical AND does not. It takes two bits and returns one, and three of its four inputs (00, 01, 10) all give 0.

Check yourself

An AND gate outputs 0. Can you tell what its inputs were?

AYes: an output of 0 means both inputs were 0.
BNo: 00, 01 and 10 all give 0, so the information is gone.
CYes, by running the AND gate backwards.

Show the answer

Answer: B. No: 00, 01 and 10 all give 0, so the information is gone.

AND sends 00, 01 and 10 to the same output, 0. A unitary gate can’t do that, because it must be undoable.

Why not the others

A. That is only one of three cases: AND(0, 1) and AND(1, 0) are also 0. The output 0 leaves three possibilities, and that loss is exactly why AND cannot be a unitary gate.
C. Running a gate backwards needs a rule that sends each output to one input. For AND the output 0 has three possible inputs, so no such rule exists. Every unitary gate has one: $U^\dagger$ .

Check yourself

Which of these classical operations could run on a quantum computer as gates, exactly as stated?

Select all that apply.

AXOR: $(a, b)\mapsto a\oplus b$ , one bit out
BSwap: $(a, b)\mapsto(b, a)$
CNOT: $a\mapsto\bar a$
DCNOT: $(a, b)\mapsto(a,\ a\oplus b)$
ENAND: $(a, b)\mapsto\overline{ab}$
FOR: $(a, b)\mapsto a\lor b$

Show the answer

Answers: B. Swap: $(a, b)\mapsto(b, a)$ ; C. NOT: $a\mapsto\bar a$ ; D. CNOT: $(a, b)\mapsto(a,\ a\oplus b)$

NOT, CNOT and swap permute the bit strings, so each can be undone (each is its own inverse). XOR, OR and NAND squeeze two bits into one, so different inputs collide.

Why not the others

A. XOR turns two bits into one: 01 and 10 both give 1. Keeping $a$ next to the XOR fixes that, and the result is CNOT.
E. NAND gives 1 for three of its four inputs, so it loses information just as AND does.
F. Three inputs (01, 10, 11) all give 1, so OR cannot be undone.

11 / 15 · Learn

Part B · Toffoli: AND without losing anything

The Toffoli gate has two controls and one target. On basis states it flips the target only when both controls are 1:

(a,\ b,\ c)\ \mapsto\ (a,\ b,\ c\oplus ab).

It keeps $a$ and $b$ , so it is a permutation of the eight 3-bit strings: it exchanges 110 and 111 and leaves the other six alone. Apply it twice and you are back where you started. In a circuit it is drawn as two control dots joined to a ⊕.

Check yourself

Toffoli has its controls on the top two wires and its target on the bottom wire. Match each input with its output.

Match each of these…

$\ket{110}$
$\ket{101}$
$\ket{111}$

…with one of these

$\ket{011}$
$\ket{110}$
$\ket{100}$
$\ket{101}$
$\ket{111}$

Hints

For each input, are both control bits (the first two labels) equal to 1?
Only then does the last bit flip.

Show the answer

$\ket{110}$	$\ket{111}$
$\ket{101}$	$\ket{101}$
$\ket{111}$	$\ket{110}$

$\ket{110}$ : both controls are 1, so $c = 0$ flips to 1, giving $\ket{111}$ . $\ket{101}$ : the second control is 0, so nothing changes. $\ket{111}$ : both controls are 1, so $c = 1$ flips to 0, giving $\ket{110}$ .

Fix some of the inputs and Toffoli computes other things. With $c = 0$ the target ends up as $ab$ : AND, with nothing thrown away. The extra input you supply is called an ancilla; outputs kept only so the gate stays reversible (here $a$ and $b$ , if all you wanted was the AND) are called garbage. Two other settings matter. NAND gates can build any classical circuit, provided you can also copy a bit (FANOUT) so that one output feeds several gates. Toffoli can do both jobs, so a quantum computer can run any classical computation.

Check yourself

Which fixed inputs make Toffoli compute NAND( $a$ , $b$ ) in the third bit, and which make it copy $b$ ?

ANAND: set $c = 1$ . Copy: impossible, because copying is forbidden.
BNAND: set $c = 1$ . Copy: set $a = 1$ and $c = 0$ .
CNAND: set $c = 0$ . Copy: set $a = 1$ and $c = 0$ .
DNAND: set $c = 1$ . Copy: set $a = 0$ and $c = 0$ .

Hints

What is $1\oplus ab$ ?
For a copy you need $c\oplus ab = b$ .

Show the answer

Answer: B. NAND: set $c = 1$ . Copy: set $a = 1$ and $c = 0$ .

With $c = 1$ the target becomes $1\oplus ab = \overline{ab}$ , which is NAND. With $a = 1$ and $c = 0$ it becomes $0\oplus b = b$ , so the output $(1, b, b)$ holds two copies of $b$ .

Why not the others

A. What is forbidden is copying an unknown quantum state (Lesson 7). Copying a classical bit, a basis state 0 or 1, is fine: with $a = 1$ and $c = 0$ , Toffoli outputs $(1, b, b)$ .
C. With $c = 0$ the third bit becomes $ab$ : that is AND. NAND is $\overline{ab} = 1\oplus ab$ , so the target has to start at 1.
D. With $a = 0$ the product $ab$ is always 0, so the target never flips and stays 0. To copy $b$ you need $ab = b$ , which takes $a = 1$ .

12 / 15 · Practice

Practice

Three problems from both parts. Hints unlock after a first try.

Check yourself

The top qubit is in $\tfrac35\ket0 + \tfrac45\ket1$ and the bottom qubit in $\tfrac45\ket0 - \tfrac{3i}{5}\ket1$ . What is the amplitude of $\ket{01}$ in the two-qubit state?

Hints

Which qubit does the first label of $\ket{01}$ belong to?
For a product state, $\alpha_{xy} = a_x b_y$ : top amplitude for the first label times bottom amplitude for the second.
Multiply the top qubit’s $\ket{0}$ amplitude, $\tfrac35$ , by the bottom qubit’s $\ket{1}$ amplitude, $-\tfrac{3i}{5}$ .

Show the answer

Answer: $-\frac{9}{25}\,i$

$\alpha_{01} = a_0\,b_1 = \left(\tfrac35\right)\left(-\tfrac{3i}{5}\right) = -\tfrac{9}{25}\,i \approx -0.36i$ .

Expand the product term by term: the coefficient of $\ket{01}$ is the top qubit’s $\ket{0}$ amplitude times the bottom qubit’s $\ket{1}$ amplitude, $\left(\tfrac35\right)\left(-\tfrac{3i}{5}\right) = -\tfrac{9}{25}\,i \approx -0.36i$ .

Common slips

$\frac{16}{25}$ : That is $a_1b_0$ , the amplitude of $\ket{10}$ . In $\ket{01}$ the first label belongs to the top qubit, so you need the top qubit’s $\ket{0}$ amplitude times the bottom qubit’s $\ket{1}$ amplitude.
$\frac{3}{5}-\frac{3}{5}i$ : Adding the two amplitudes treats the qubits as separate lists. In a product state each amplitude is a product, $\alpha_{xy} = a_x b_y$ : expanding $(a_0\ket0 + a_1\ket1)(b_0\ket0 + b_1\ket1)$ multiplies them.

Check yourself

Build a circuit on three wires that leaves $q_0 = a$ and $q_1 = b$ unchanged and turns $q_2$ , which starts at 0, into NAND( $a$ , $b$ ). An $X$ in a column with control dots becomes a ⊕ that acts only when every dot in that column is 1.

Build it in the circuit builder (gates: control, X).

Hints

What does a Toffoli put on $q_2$ when $q_2$ starts at 0?
NAND is NOT of AND: $\overline{ab} = 1\oplus ab$ .
Place a Toffoli (two dots and an $X$ in one column), then an $X$ on $q_2$ alone in the next column.

Show the answer

One circuit that works: Toffoli q0,q1→q2, then X on q2.

A Toffoli writes $ab$ into $q_2$ , and an $X$ on $q_2$ then gives $1\oplus ab = \overline{ab}$ . Putting the $X$ first also works: it sets the target to 1, and the Toffoli then gives $1\oplus ab$ .

Column 1: control dots on $q_0$ and $q_1$ , $X$ on $q_2$ (a Toffoli): $(a, b, 0)\mapsto(a, b, ab)$ . Column 2: $X$ on $q_2$ alone: $(a, b, ab)\mapsto(a, b, 1\oplus ab)$ . Inputs 000, 010, 100, 110 go to 001, 011, 101, 110.

Check yourself

Take $\ket\psi = \tfrac{1}{\sqrt6}\ket{00} + \tfrac{i}{\sqrt6}\ket{01} - \tfrac{2}{\sqrt6}\ket{11}$ . You measure only the bottom qubit, in the 0/1 basis. What is the probability that it gives 0?

$P = \;?$

Hints

Which two basis states have the bottom (second) label equal to 0?
The probability of a result on one qubit is the sum of $\abs{\alpha}^2$ over every basis state that agrees with it.
Add $\abs{\alpha_{00}}^2$ and $\abs{\alpha_{10}}^2$ .

Show the answer

Answer: $P = \frac{1}{6}$

Add the column for 0: $\abs{\alpha_{00}}^2 + \abs{\alpha_{10}}^2 = \tfrac{1}{6} + 0 = \tfrac{1}{6}$ .

The bottom qubit is the second label, so the result 0 covers $\ket{00}$ and $\ket{10}$ : $P = \tfrac{1}{6} + 0 = \tfrac{1}{6}$ . After that result only those terms remain, divided by $\sqrt{\tfrac{1}{6}}$ : $|00\rangle$ .

Common slips

$\frac{1}{3}$ : That total belongs to the top qubit: it adds the terms whose first label is 0. The bottom qubit is the second label, so add $\abs{\alpha_{00}}^2 + \abs{\alpha_{10}}^2$ .
$\frac{5}{6}$ : That is the probability of the other result, 1. For 0, add the squared magnitudes of the terms whose second label is 0.

13 / 15 · Explain

Explain it

Why can’t a quantum computer apply the classical AND gate directly, and how does the Toffoli gate get around this?

Show a model answer

Quantum gates are unitary, so every gate has an inverse and different inputs must give different outputs. AND sends three inputs (00, 01 and 10) to the same output 0, so it destroys information and cannot be undone. Toffoli keeps $a$ and $b$ and writes $c\oplus ab$ into a third bit. That makes it a permutation of the eight basis strings, and its own inverse. With $c = 0$ the third bit holds AND( $a$ , $b$ ); the extra bit is an ancilla, and the kept inputs are garbage you may not need.

A good answer covers

Quantum gates are unitary, so reversible: each one has an inverse.
AND maps several inputs (00, 01, 10) to the same output, so it loses information.
Toffoli keeps $a$ and $b$ and writes $c\oplus ab$ into an extra bit, so it is a permutation of basis states; with $c = 0$ that bit is AND( $a$ , $b$ ).
Mentions the ancilla bit, or the leftover garbage outputs.

14 / 15 · Mastery check

Mastery check

Check yourself

A general state of 7 qubits: how many complex amplitudes does it take to write down, and how many bits do you get when you measure all 7 qubits in the 0/1 basis?

A128 amplitudes; 128 bits
B128 amplitudes; 7 bits
C7 amplitudes; 7 bits
D14 amplitudes; 7 bits

Show the answer

Answer: B. 128 amplitudes; 7 bits

Each of the $2^{7} = 128$ strings is a basis state with its own amplitude, but one measurement picks out one string: 7 bits.

Why not the others

A. A common idea is that every amplitude gets read out. One shot of the measurement returns one 7-bit string, so 7 bits. The 128 amplitudes set the odds of the 128 possible strings; they never come out as data.
C. One number per qubit would describe a classical register, where each bit has a definite value. A quantum register gives an amplitude to every string: $2^{7} = 128$ numbers. Even one qubit needs two, $\alpha$ and $\beta$ .
D. Adding 2 per qubit treats the qubits as separate lists. The basis states are the strings 0000000 to 1111111, and there are $2^{7} = 128$ of them, each with its own amplitude. Dimensions multiply under $\tp$ .

Check yourself

Three qubits, top to bottom: $\tfrac45\ket0 - \tfrac{3i}{5}\ket1$ , then $\tfrac{\sqrt3}{2}\ket0 + \tfrac12\ket1$ , then $\tfrac35\ket0 + \tfrac45\ket1$ . What is the amplitude of $\ket{100}$ in their product state?

Show the answer

Answer: $-0.312\,i$

One factor per qubit, in order: $\left(-\tfrac{3i}{5}\right)\left(\tfrac{\sqrt3}{2}\right)\left(\tfrac35\right) = -\tfrac{9\sqrt{3}}{50}\,i \approx -0.312i$ .

Common slips

$0.554$ : That reads $100$ from the right, which is the amplitude of $\ket{001}$ . The first label is the top qubit, so take the top qubit’s $\ket{1}$ amplitude, the middle qubit’s $\ket{0}$ amplitude and the bottom qubit’s $\ket{0}$ amplitude.

Check yourself

Take $\ket\psi = \tfrac{1}{\sqrt2}\ket{01} + \tfrac{i}{2}\ket{10} - \tfrac12\ket{11}$ . You measure only the bottom qubit, in the 0/1 basis. What is the probability that it gives 1?

Hints

Which two basis states have the bottom (second) label equal to 1?
The probability of a result on one qubit is the sum of $\abs{\alpha}^2$ over every basis state that agrees with it.
Add $\abs{\alpha_{01}}^2$ and $\abs{\alpha_{11}}^2$ .

Show the answer

Answer: $\frac{3}{4}$

Add the column for 1: $\abs{\alpha_{01}}^2 + \abs{\alpha_{11}}^2 = \tfrac{1}{2} + \tfrac{1}{4} = \tfrac{3}{4}$ .

The bottom qubit is the second label, so the result 1 covers $\ket{01}$ and $\ket{11}$ : $P = \tfrac{1}{2} + \tfrac{1}{4} = \tfrac{3}{4}$ . After that result only those terms remain, divided by $\sqrt{\tfrac{3}{4}}$ : $\frac{2}{\sqrt{6}}|01\rangle - \frac{1}{\sqrt{3}}|11\rangle$ .

Common slips

$\frac{1}{2}$ : That total belongs to the top qubit: it adds the terms whose first label is 1. The bottom qubit is the second label, so add $\abs{\alpha_{01}}^2 + \abs{\alpha_{11}}^2$ .
$\frac{1}{4}$ : That is the probability of the other result, 0. For 1, add the squared magnitudes of the terms whose second label is 1.

Check yourself

Compute $U_{CN}\,(X\tp I)\ket{10}$ , where $U_{CN}$ has its control on the top qubit and $X\tp I$ is $X$ on the top qubit.

A $\ket{00}$
B $\ket{01}$
C $\ket{10}$
D $\ket{11}$

Show the answer

Answer: A. $\ket{00}$

$X\tp I$ acts first (it is next to the ket): $\ket{10}\to\ket{00}$ . Then $U_{CN}$ : $\ket{00}\to\ket{00}$ .

Why not the others

B. That applies the two gates in the order they are written, left to right. In a product of operators the rightmost acts first. $X\tp I$ acts first (it is next to the ket): $\ket{10}\to\ket{00}$ . Then $U_{CN}$ : $\ket{00}\to\ket{00}$ .
C. That is the input unchanged, as if the two gates cancelled. They don’t: $X\tp I$ acts first (it is next to the ket): $\ket{10}\to\ket{00}$ . Then $U_{CN}$ : $\ket{00}\to\ket{00}$ .
D. Trace it one gate at a time, starting from the right. $X\tp I$ acts first (it is next to the ket): $\ket{10}\to\ket{00}$ . Then $U_{CN}$ : $\ket{00}\to\ket{00}$ .

Check yourself

Every quantum gate is reversible. Can a quantum computer compute $\mathrm{XOR}(a, b)$ of two bits?

AYes. Apply an XOR gate to the two qubits, as in a classical chip.
BNo. XOR is irreversible, so quantum circuits cannot compute it.
CYes, if the circuit keeps $a$ and $b$ and writes the answer into an extra bit.
DOnly approximately: the answer comes out right with some probability below 1.

Show the answer

Answer: C. Yes, if the circuit keeps $a$ and $b$ and writes the answer into an extra bit.

Keep $a$ and $b$ and write the answer into a third bit: $(a, b, c)\mapsto(a, b, c\oplus \mathrm{XOR}(a, b))$ is a permutation of the eight strings, built from two CNOTs, one from each input bit into the third. With $c = 0$ the third bit ends up holding $\mathrm{XOR}(a, b)$ .

Why not the others

A. A classical XOR gate turns two bits into one and loses information: 00 and 11 both give 0, and 01 and 10 both give 1. A quantum gate is unitary, so it must be undoable, and no rule can undo a collision like that. Classical chips may lose information; quantum gates may not.
B. This takes "gates must be reversible" one step too far. The function XOR can still be computed: keep $a$ and $b$ and XOR the answer into an extra bit, $(a, b, c)\mapsto(a, b, c\oplus \mathrm{XOR}(a, b))$ . That is a permutation of bit strings, so it is reversible. Only a gate that throws its inputs away is ruled out.
D. Nothing random is needed. On basis-state inputs a reversible circuit is a permutation of bit strings and gives the answer with certainty. Randomness only enters if you feed in superpositions and then measure.

15 / 15 · Recap

Recap

From memory

Before reading the summary, write down what you remember. Pulling it back from memory is what makes it last.

How do you turn two one-qubit states into one two-qubit vector, and what happens when you measure just one of the qubits?
Show the key points
- Each amplitude is a product, $\alpha_{xy} = a_x b_y$ (top amplitude times bottom amplitude).
- Slots in the order 00, 01, 10, 11; the first label is the top wire.
- $n$ qubits need $2^n$ amplitudes, but measuring them all in the 0/1 basis returns one $n$ ⁠-bit string.
- Measuring one qubit: add $\abs{\alpha}^2$ over its row (or column), keep it, divide by $\sqrt{P}$ .
What does CNOT do, and when can its control qubit change?
Show the key points
- On basis states, $\ket{A,B}\to\ket{A, B\oplus A}$ : the target flips when the control is 1.
- On superpositions, apply it term by term.
- With target $\ket-$ the sign lands on the control: $\ket+\ket-\to\ket-\ket-$ .
Why must quantum gates be reversible, and how does Toffoli compute AND anyway?
Show the key points
- Unitary means invertible: no two inputs may share an output.
- AND sends 00, 01 and 10 to 0, so it loses information.
- Toffoli $(a, b, c)\mapsto(a, b, c\oplus ab)$ : $c = 0$ gives AND, $c = 1$ gives NAND, and $a = 1$ , $c = 0$ copies $b$ .

Key ideas

Qubits in $\ket a$ and $\ket b$ together are in $\ket a\tp\ket b$ , with amplitudes $\alpha_{xy} = a_x b_y$ in the order 00, 01, 10, 11. The first label is the top wire.
$n$ qubits need $2^n$ amplitudes; measuring all of them in the 0/1 basis returns one $n$ ⁠-bit string.
Measuring one qubit of two in the 0/1 basis: add $\abs{\alpha}^2$ over the matching terms (its row or column of the grid), keep those terms, and divide by $\sqrt{P}$ .
CNOT maps $\ket{A,B}\to\ket{A, B\oplus A}$ on basis states. On superpositions apply it term by term; with target $\ket-$ the control picks up the sign, so $\ket+\ket-\to\ket-\ket-$ .
Circuits run left to right in time, but the operator is written right to left: $A$ then $B$ is $BA$ . Three CNOTs, the middle one reversed, swap two qubits.
Gates are unitary, so reversible. AND is not; Toffoli $(a, b, c)\mapsto(a, b, c\oplus ab)$ is, and with fixed inputs it gives AND, NAND and FANOUT.

Go further

Free resources for when you want more than this lesson covers.

From Cbits to Qbits: teaching computer scientists quantum mechanicsN. David Mermin · Article
A physicist’s case for treating classical bits as vectors before qubits, the order this course follows, worked out in full.
Basics of quantum information: Multiple systemsJohn Watrous, IBM Quantum · Course
Tensor products, Bell states and partial measurements for any number of systems, with a video and Qiskit code.
Reversible computingWikipedia · Article
Why erasing a bit must give off a minimum amount of heat (Landauer’s principle), the physics behind reversible logic.

Math refreshers

The toolkit topics this lesson leans on.

Tensor productsCombining qubits: |a⟩⊗|b⟩ as a 4-entry vector
Bits, XOR and bit stringsx ⊕ y, x · z mod 2, sums over {0,1}ⁿ, and signs that depend on f(x)