Reversible computing and uncomputation

1 / 12 · Learn

Before you start

Lesson 6 built classical logic from reversible gates, and Lesson 9 used an oracle $U_f$ without asking how it is made. This lesson builds oracles from gates and finds the catch: scratch work left behind in extra qubits quietly breaks the interference that quantum algorithms depend on.

By the end of this lesson you can:

build $U_f$ for small Boolean functions from $X$ , CNOT and Toffoli gates, with anti-controls and work qubits;
explain why a work qubit left holding $g(x)$ wrecks the interference in Deutsch’s algorithm, and what a mixed state is;
clean up with compute, copy, uncompute, and count what it costs;
turn a clean bit oracle into a phase oracle.

Check yourself

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

Deutsch’s algorithm for $f(x) = x$ , with one change: the oracle uses a work qubit $w$ , starting in $\ket0$ , for scratch work, and leaves it holding a copy of the input, $w = x$ . The output qubit is in $\ket-$ as usual, and nobody measures $w$ . What does the 0/1 measurement of the input qubit give after the last $H$ ?

A0 every time
BThe answer moves into $w$ : measuring $w$ would give $f(0)\oplus f(1)$
C1 every time, as in the algorithm without $w$
D0 or 1, each with probability $\tfrac12$

Show the answer

Answer: D. 0 or 1, each with probability $\tfrac12$

Before the last $H$ the state is $\tfrac{1}{\sqrt2}\big(\ket0\ket0 -\ket1\ket1\big)\ket-$ , so the input is entangled with $w$ . The last $H$ sends each branch to both outcomes of the input, but the branches land on different values of $w$ , so their amplitudes never add or cancel. Each outcome has probability $\tfrac12$ .

Why not the others

A. Nothing flips the answer. A leftover that records $x$ stops the two signs from meeting at all, so neither outcome is certain.
B. $w$ only ever holds $w = x$ , which says nothing about $f$ ; measured, it gives the input’s value, 0 or 1 at random. With $y$ in $\ket-$ , the values of $f$ become signs on the input’s branches, not bits in $w$ .
C. Nobody measures $w$ , but it is not idle: the branch $x = 0$ carries $w = 0$ and the branch $x = 1$ carries $w = 1$ . The last $H$ can only combine amplitudes that sit on the same basis state of every qubit, so the two signs never meet, and the input reads 0 or 1 at random.

Check yourself

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

Start with $x = 11$ , a work qubit $w = 0$ and the output $y = 0$ . Compute $x_0\wedge x_1$ into $w$ (one Toffoli from $x_0, x_1$ onto $w$ ). Copy $w$ into $y$ with a CNOT. Then uncompute: the same Toffoli again. What are $w$ and $y$ at the end?

A $w = 0$ , $y = 0$
B $w = 1$ , $y = 1$
C $w = 1$ , $y = 0$
D $w = 0$ , $y = 1$

Show the answer

Answer: D. $w = 0$ , $y = 1$

Compute: $w = f(11) = 1$ . Copy: $y = 0\oplus 1 = 1$ , and $w$ is left as it was. Uncompute: the compute gates in reverse order turn $w$ back into 0, and they never touch $y$ . So $w = 0$ and $y = 1$ .

Why not the others

A. That treats the uncompute as undoing everything. It runs only the compute gates backwards, and those never touch $y$ . The copy wrote $f(x) = 1$ into $y$ , and nothing undoes it: $y$ ends at $0\oplus 1 = 1$ .
B. The uncompute does clear $w$ . The copy only read $w$ , so $w$ still holds $f(x) = 1$ when the uncompute starts, and running the compute gates backwards turns it back into 0.
C. That leaves the answer stuck in $w$ . The copy CNOT has control $w = 1$ , so it does flip $y$ , to $1$ ; then the uncompute returns $w$ to 0.

2 / 12 · Learn

Oracles from reversible gates

Three reversible gates from Lesson 6 do all of classical logic:

$X$ is NOT: $\ket a\to\ket{\bar a}$ .
CNOT adds its control into its target: $\ket{a, b}\to\ket{a, b\oplus a}$ . With $b = 0$ it copies a bit, and two CNOTs into one target compute XOR.
Toffoli adds an AND: $\ket{a, b, c}\to\ket{a, b, c\oplus ab}$ . With $c = 0$ it computes $a\wedge b$ .

None of them destroys its inputs, and each is its own inverse. A gate that sent $a, b$ to just $a\wedge b$ would map three inputs to the same output 0, which no unitary can do. So to compute $f$ you build the oracle of Lesson 9, $U_f\ket{x, y} = \ket{x, y\oplus f(x)}$ : keep the input, and add the value into an output qubit $y$ .

Check yourself

Build $U_f$ for $f(x) = x_0\oplus x_1$ (XOR), with the inputs on the top two wires and $y$ on the bottom. The truth table shows what your circuit does to every basis input.

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

Hints

A CNOT adds one bit into its target. How many bits do you need to add into $y$ ?
One CNOT from $x_0$ onto $y$ , and one from $x_1$ onto $y$ .

Show the answer

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

Each CNOT adds one input into $y$ , so two of them give $y\oplus x_0\oplus x_1$ . Both inputs pass through unchanged, as $U_f$ requires.

Some functions need a gate that fires on a 0. An open circle, ○, is an anti-control: the gate acts when that qubit is 0. In code it is an $X$ before and after on that qubit, or Qiskit’s ctrl_state: qc.ccx(0, 1, 2, ctrl_state='00') fires only when q0 and q1 are both 0.

OR then follows from De Morgan’s law, $x_0\vee x_1 = \overline{\bar x_0\wedge\bar x_1}$ . A Toffoli with two anti-controls flips $y$ only on $00$ , which computes NOR. An $X$ on $y$ afterwards flips every row of the truth table, and turns NOR into OR. In general, a function that is 1 on most inputs is easiest to build from its complement plus one $X$ .

Check yourself

Build $U_f$ for $f(x) = x_0\vee x_1$ (OR). The palette’s ○ places an anti-control.

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

Hints

On which single input is OR equal to 0?
Flip $y$ on $00$ with a Toffoli that has two anti-controls; then flip $y$ on every input.

Show the answer

One circuit that works: controlled-X q0=0,q1=0→q2, then X on q2.

The anti-controlled Toffoli flips $y$ only on $00$ (NOR); the $X$ then flips it on every input. Net effect: $y$ is flipped on $01$ , $10$ and $11$ , exactly where $x_0\vee x_1 = 1$ . Three Toffolis with ordinary controls, one per input with $f = 1$ , would also work, at three times the cost.

3 / 12 · Learn

Work qubits

A Toffoli has only two controls, so a function of three bits often needs an intermediate result. Take $f(x) = (x_0\vee x_1)\wedge x_2$ . First compute $x_0\vee x_1$ into a work qubit $w$ that starts at 0 (Lesson 6 called such a helper an ancilla). Then one Toffoli from $w$ and $x_2$ writes the answer into $y$ .

The program below does this on the input $x = 101$ : its first two lines only prepare that input. Run it and read the final ket, then change the input lines and run it again.

Interactive

A code editor for Python with Qiskit’s circuit methods, run in the page: edit the program below and run it to see the circuit it builds, the state it leaves and, when it measures, the counts from 1,000 shots.

from qiskit import QuantumCircuit

qc = QuantumCircuit(5)   # q0, q1, q2: the input x;  q3: work w;  q4: output y
qc.x(0)                  # these two lines only set the input: x = 101
qc.x(2)

qc.ccx(0, 1, 3, ctrl_state='00')   # flips w when x0 = 0 and x1 = 0 (NOR) ...
qc.x(3)                            # ... and flips it back: now w = x0 OR x1
qc.ccx(2, 3, 4)                    # y = x2 AND w

Five qubits: q0–q2 the input, q3 the work qubit $w$ , q4 the output $y$ . The ket lists them in that order, so $\ket{10111}$ means $x = 101$ , $w = 1$ , $y = 1$ .

Open it in the app

Check yourself

A program on five qubits (q0–q2 the input, q3 the work qubit $w$ , q4 the output $y$ ) runs qc.ccx(0, 1, 3, ctrl_state='00'), then qc.x(3), then qc.ccx(2, 3, 4). The input is $x = 111$ , and $w$ and $y$ start at 0. What are $w$ and $y$ afterwards?

A $w = 0$ , $y = 0$
B $w = 0$ , $y = 1$
C $w = 1$ , $y = 0$
D $w = 1$ , $y = 1$

Show the answer

Answer: D. $w = 1$ , $y = 1$

$w = x_0\vee x_1 = 1\vee 1 = 1$ : the anti-controlled Toffoli computes NOR, and the $X$ turns it into OR. Then $y = x_2\wedge w = 1\wedge 1 = 1$ . The work qubit keeps $x_0\vee x_1$ , since nothing clears it.

Why not the others

A. The work qubit is not cleared: no gate here resets it. The first two gates leave $w = x_0\vee x_1 = 1$ , and it stays 1. The last Toffoli sets $y = x_2\wedge w = 1\wedge 1 = 1$ .
B. The work qubit is not cleared: no gate here resets it. The first two gates leave $w = x_0\vee x_1 = 1$ , and it stays 1.
C. The last Toffoli sets $y = x_2\wedge w = 1\wedge 1 = 1$ .

Look at what is left over: $w$ still holds $x_0\vee x_1$ . On a classical computer that is harmless junk, to be ignored or overwritten later. In a quantum circuit it is not harmless, as the next experiment shows.

4 / 12 · Explore

The trouble with leftovers

Predict, then see

A program runs Deutsch’s algorithm for $f(x) = x$ with one change. The oracle works in two steps: it copies $x$ into a work qubit $w$ , then writes $f(x) = w$ into $y$ , and it leaves $w$ as it is. Without the work qubit, the measurement of the input gives 1 every time ( $f$ is balanced). What do 1000 runs of this program give?

A0 every time: the extra CNOT flips the answer
B0 and 1, about 500 each
C1 every time: $w$ is never measured, so it can’t matter
DMostly 1, with a few 0s

Interactive

A code editor for Python with Qiskit’s circuit methods, run in the page: edit the program below and run it to see the circuit it builds, the state it leaves and, when it measures, the counts from 1,000 shots.

from qiskit import QuantumCircuit

qc = QuantumCircuit(3, 1)   # q0: input x;  q1: work w;  q2: output y
qc.x(2)
qc.h(2)                     # y in |−⟩, as in Deutsch’s algorithm
qc.h(0)                     # x in |+⟩

qc.cx(0, 1)                 # the oracle’s scratch work: w = x
qc.cx(1, 2)                 # write f(x) = w into y (here f(x) = x)

qc.h(0)
qc.measure(0, 0)

Press Run and read the counts. Then add the line qc.cx(0, 1) right after the line that writes into $y$ , and run again.

Open it in the app

Why does a qubit that nobody measures change the result? A sentence or two is enough.

Show what happens

What happens: B. 0 and 1, about 500 each

With $w$ holding a copy of $x$ , the input reads 0 or 1 at random, about 500 each. Adding qc.cx(0, 1) after the write undoes the scratch work: $w$ returns to 0 in both branches, and the input reads 1 every time again.

Why not the others

A. The extra CNOT doesn’t flip the answer to the other certainty. It records which branch is which, and then neither outcome is certain.
C. A qubit nobody looks at seems to be irrelevant. But $w$ took part in the circuit: it is entangled with the input, and the counts show the interference is gone.
D. A perfect copy spoils the interference completely, not a little: the counts are close to 50/50. A partial record does give something in between, as you will see shortly.

Follow the state, with $y$ in $\ket-$ throughout (it is left out of the kets below). After the first $H$ the input is $\tfrac{1}{\sqrt2}(\ket0 + \ket1)$ and $w = \ket0$ . The scratch CNOT gives $\tfrac{1}{\sqrt2}(\ket{00} + \ket{11})$ : the input and $w$ are now entangled. Writing into $y$ kicks back the sign $(-1)^{f(x)}$ : $\tfrac{1}{\sqrt2}(\ket{00} - \ket{11})$ .

The branches carry opposite signs, just as in Deutsch’s algorithm. But the last $H$ sends each branch to both $\ket0$ and $\ket1$ on the input, and the $x = 0$ branch lands on $w = 0$ while the $x = 1$ branch lands on $w = 1$ . Amplitudes add or cancel only when they sit on the same basis state of every qubit. Here nothing meets, so nothing cancels: four outcomes, each with probability $\tfrac14$ .

Nothing left in w

A copy of x left in w

Deutsch’s algorithm for $f(x) = x$ as a ledger. Each branch of the input sends an arrow carrying $\pm\tfrac12$ to each outcome of the last $H$ it can reach. With nothing left in $w$ , both branches reach the same two outcomes, so the arrows add on “reads 1” and cancel on “reads 0”. With a copy of $x$ left in $w$ , the branches reach different outcomes, so nothing cancels and each of the four has probability $\tfrac14$ .

Check yourself

Deutsch’s algorithm for $f(x) = x$ , where the oracle leaves its work qubit $w$ in the state below. In which cases does the input still read 1 every time?

Select all that apply.

A $w = \ket x$ , a copy of the input
B $w = \ket+$ for both inputs
C $w = \ket1$ for both inputs
D $w = \ket{\bar x}$ , the input flipped
E $w = \ket0$ for both inputs

Hint

Does $w$ differ between the branches $x = 0$ and $x = 1$ ?

Show the answer

Answers: B. $w = \ket+$ for both inputs; C. $w = \ket1$ for both inputs; E. $w = \ket0$ for both inputs

What matters is whether $w$ differs between the branches. If it is the same state for $x = 0$ and $x = 1$ , whatever state that is, it factors out and the branches interfere as usual. If it differs, as with $\ket x$ or $\ket{\bar x}$ , it records the branch and the interference is lost.

Why not the others

A. A copy differs between the branches: $\ket0$ for $x = 0$ , $\ket1$ for $x = 1$ . It records which branch is which, so the branches can’t interfere, and the input reads 0 or 1 at random.
D. Flipping the copy doesn’t help. $w$ still differs between the branches, so it still records which branch is which, and the interference is just as lost as with $w = \ket x$ .

5 / 12 · Learn

A qubit with no ket: mixed states

In the leaky circuit, after the write into $y$ , the input and $w$ share the state $\tfrac{1}{\sqrt2}(\ket{00} - \ket{11})$ , a Bell state up to a sign. The input has no ket of its own (Lesson 7). You can still ask what any measurement of the input alone would give: $\tfrac12$ each in the 0/1 basis, and $\tfrac12$ each in the $\pm$ basis too, because the branches can’t interfere. The same goes for $\ket{\pm i}$ .

Here is a way to picture that. Read a Bloch vector off the statistics:

r_x = P(+) - P(-),\quad r_y = P(+i) - P(-i),\quad r_z = P(0) - P(1).

For any qubit with a ket this vector has length 1 and points at the state. For the leaky input it is $(0, 0, 0)$ : the centre of the sphere.

Check yourself

In the clean algorithm for $f(x) = x$ , the input is $\ket-$ just before the last $H$ , so its Bloch vector’s component $r_x = P(+) - P(-)$ is $-1$ . In the leaky circuit, with $w$ holding a copy of $x$ , what is $r_x$ just before the last $H$ ?

$r_x = \;?$

Hints

What are $P(+)$ and $P(-)$ for the leaky input?
Measuring in the $\pm$ basis means an $H$ and then a 0/1 measurement, and with $w$ holding $x$ that gives each outcome half the time.

Show the answer

Answer: $r_x = 0$

$P(+) = P(-) = \tfrac12$ , so the component is $\tfrac12 - \tfrac12 = 0$ . The other two components are 0 as well: the vector has shrunk to the centre.

Common slips

$-1$ : That is the clean value. With $w$ holding $x$ , the branches can’t interfere in a $\pm$ measurement either, so $P(+) = P(-) = \tfrac12$ .
$\frac{1}{2}$ : That is one of the two probabilities. The component is their difference: $P(+) - P(-) = \tfrac12 - \tfrac12$ .
$1$ : A component of $+1$ would mean the input is certainly $\ket+$ . Here the $\pm$ measurement is a fair coin.

A qubit whose Bloch vector is shorter than 1 is in a mixed state. A mixed state is not a superposition. In Lesson 2, $\ket+$ and a coin that gives $\ket0$ or $\ket1$ both gave 50/50 in the 0/1 basis, but in the ± basis $\ket+$ gave $+$ every time while the coin stayed 50/50. The leaky input behaves like the coin: 50/50 in every basis. Gates on the input alone only rotate its Bloch vector, so none of them can make it longer: the information that would restore the interference now sits in $w$ .

Qubits with a ket sit on the surface of the sphere; mixed states sit inside it. The tool that makes this precise is the density matrix, which describes a qubit even when it has no ket of its own. This lesson doesn’t need it; the density-matrix course under Go further introduces it.

Check yourself

The leaky circuit has run up to just before the last $H$ , with $w$ holding a copy of $x$ . Which statement is true?

AAn $H$ on the input makes it definite again, as it does for $\ket+$
BMeasuring $w$ and throwing the result away restores the interference
CNo gate on the input alone can make it read 1 every time again
DThe input is still $\ket-$ ; $w$ only adds noise when the input is measured

Show the answer

Answer: C. No gate on the input alone can make it read 1 every time again

The input’s Bloch vector has length 0, and gates on the input alone only rotate the vector; they can’t lengthen it. What decides the branch is recorded in $w$ , so only a gate that acts on $w$ too, undoing the copy, can restore the interference.

Why not the others

A. That works for a superposition, whose branches can interfere. Here the branches are tagged by $w$ , so an $H$ on the input leaves it 50/50: it acts like the coin from Lesson 2, not like $\ket+$ .
B. Measuring $w$ tells you $x$ , which leaves the input in that one branch. A single branch gives 0 or 1 at random after the last $H$ . Only undoing the copy, in every branch at once, brings the interference back.
D. If the input were $\ket-$ , the last $H$ would give 1 every time. It is entangled with $w$ and has no ket of its own: its Bloch vector has length 0, not 1.

A full copy is the extreme case. Scratch work can also leave a partial record: say $w$ ends in $\ket{g_0} = \ket0$ when $x = 0$ and in $\ket{g_1} = \cos a\ket0 + \sin a\ket1$ when $x = 1$ . How alike the two records are is measured by their overlap, $c = \langle g_0|g_1\rangle = \cos a$ .

The branches can now interfere only through the part where the records agree. The same calculation as before gives an input Bloch vector of length $c$ , and the algorithm gives the right answer with probability $\tfrac12(1 + c)$ . Identical records ( $c = 1$ ) do no harm. Orthogonal records ( $c = 0$ ), such as a full copy, leave a coin toss. In between, the answer is right more often than not, but not every time.

The input qubit just before the last $H$ , in Deutsch’s algorithm for $f(x) = x$ ; each disc is the $x$ – $z$ slice of the Bloch sphere. The scratch work leaves $w$ in $\ket0$ for $x = 0$ and in the state shown for $x = 1$ . With no record the vector reaches $\ket-$ and the answer is certain; a full copy shrinks it to the centre. $P$ is the probability of the right answer, $\tfrac12(1 + \text{length})$ .

The two records in w

The input before the last H

The two records in $w$ , drawn as arrows in the plane of real amplitudes, $a = 45^\circ$ apart. Their overlap $\langle g_0|g_1\rangle = \cos a$ is the shadow of $\ket{g_1}$ on $\ket{g_0}$ , marked by the bar. The input before the last $H$ has a Bloch vector of exactly that length. Identical records do no harm; orthogonal ones leave a coin toss.

Check yourself

In Deutsch’s algorithm for a balanced $f$ , the oracle’s scratch work leaves the work qubit in $\ket{g_0} = \ket0$ when $x = 0$ and in $\ket{g_1} = \tfrac12\ket0 + \tfrac{\sqrt3}{2}\ket1$ when $x = 1$ . What is the probability that the algorithm gives the right answer?

$P = \;?$

Hints

Only the part of the two records that agrees can interfere. How much do they overlap?
The overlap is $c = \langle g_0|g_1\rangle$ , and the right answer comes out with probability $\tfrac12(1 + c)$ .
Here $\langle g_0|g_1\rangle$ is the $\ket0$ amplitude of $\ket{g_1}$ : $\tfrac12$ .

Show the answer

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

The records overlap by $\langle g_0|g_1\rangle = \tfrac12$ , so the right answer comes out with probability $\tfrac12\big(1 + \tfrac12\big) = \tfrac34$ .

Before the last $H$ the state is $\tfrac{1}{\sqrt2}\big(s_0\ket0\ket{g_0} + s_1\ket1\ket{g_1}\big)\ket-$ with signs $s_x = (-1)^{f(x)}$ , and $s_1 = -s_0$ since $f$ is balanced. The last $H$ makes the part with the input at 1, the right answer, equal to $\tfrac12\big(s_0\ket{g_0} - s_1\ket{g_1}\big) = \tfrac{s_0}{2}\big(\ket{g_0} + \ket{g_1}\big)$ . Its squared length is $\tfrac14\big(1 + 1 + 2\langle g_0|g_1\rangle\big) = \tfrac12\big(1 + \langle g_0|g_1\rangle\big)$ . Here $\langle g_0|g_1\rangle = \tfrac12$ , so $P = \tfrac34$ .

Common slips

$1$ : That would need the two records to be identical. These overlap only partly, so part of the interference is lost.
$\frac{1}{2}$ : A coin toss is what orthogonal records give, such as a full copy of $x$ . These records overlap, and the overlapping part still interferes.
$\frac{1}{4}$ : That squares the overlap. The overlap enters the probability once, through the cross term: $P = \tfrac12(1 + \text{overlap})$ .

6 / 12 · Learn

Compute, copy, uncompute

The cure is to clean up after yourself. Call the scratch part of an oracle $C$ : it writes $f(x)$ , and whatever else it needs on the way, into work qubits that start at 0. Then:

Compute: run $C$ . The work qubits now hold $g(x)$ , which includes $f(x)$ .
Copy: CNOT the qubit holding $f(x)$ into the output $y$ .
Uncompute: run $C^{-1}$ , the gates of $C$ in reverse order. $X$ , CNOT and Toffoli are their own inverses, so $C^{-1}$ uses the same gates, last one first.

Step 3 returns every work qubit to 0, in every branch at once. The net effect is $\ket x\ket0\ket y\to\ket x\ket0\ket{y\oplus f(x)}$ : exactly $U_f$ , with nothing left behind.

The pattern

Three-input AND, input 111

Compute, copy, uncompute. The pattern holds for any $f$ ; the shaded cells are the ones each step changes. The second table runs the three-input AND on $x = 111$ , with two work bits $w_1 = x_0\wedge x_1$ and $w_2 = w_1\wedge x_2$ . The answer reaches $y$ in the copy step and stays there while the work bits are cleared.

Why doesn’t step 3 erase the copied answer too? $C^{-1}$ consists of the gates of $C$ , and $C$ never touched $y$ ; only the copy wrote into it. And $C^{-1}$ really does undo $C$ , because the copy left the work qubits exactly as $C$ left them: on each basis branch a CNOT leaves its control unchanged.

This is Charles Bennett’s trick from 1973. The answer is copied out before the scratch work is undone, and the work qubits end where they began.

Check yourself

This is the leaky circuit from the experiment: $H$ on the input, the scratch CNOT ( $w = x$ ), the write into $y$ (which starts in $\ket-$ ), and the last $H$ . Column 4 is empty. Add one gate there so the input reads 1 every time.

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

Hints

Which step left $w$ holding $x$ ? Undo it, after the write and before the last $H$ .
A CNOT from $x$ onto $w$ , in column 4.

Show the answer

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

The scratch CNOT runs again after the write: $w = x\oplus x = 0$ in both branches. The state before the last $H$ is $\ket-\ket0\ket-$ , and the last $H$ gives $\ket1\ket0\ket-$ . The same CNOT after the last $H$ comes too late: by then the branches have already failed to interfere.

Two practical points. Order: $C^{-1}$ runs the gates of $C$ backwards. Each gate can only be undone while the qubits it reads still hold what they held when it ran, and that is true of the last gate first.

Cost: if $C$ uses $k$ gates and the answer has $c$ bits, the clean oracle uses $k$ to compute, $c$ CNOTs to copy and $k$ to uncompute, $2k + c$ in all: roughly twice the gates. In exchange the work qubits come back at 0, free to be used again by the next step of a larger circuit. Often the last step of $C$ can write straight into $y$ instead of a work qubit, which saves a qubit and two gates; the worked example below does that.

Check yourself

This compute part $C$ writes $\bar x_0\wedge x_1\wedge x_2$ into q4, using q3 for scratch: qc.x(0), then qc.ccx(0, 1, 3), then qc.ccx(2, 3, 4). A CNOT then copies q4 into the output qubit. Put the three gates of the uncompute in order, first at the top.

Put these in order.

qc.ccx(2, 3, 4)
qc.x(0)
qc.ccx(0, 1, 3)

Hints

Which gate of $C$ ran last? Its effect has to be removed first.
The uncompute is $C$ read from the end: same gates, reverse order.

Show the answer

qc.ccx(2, 3, 4)
qc.ccx(0, 1, 3)
qc.x(0)

Undo the last gate first: qc.ccx(2, 3, 4), then qc.ccx(0, 1, 3), then qc.x(0). Each gate is its own inverse, and each one can only be undone while the qubits it reads hold what they held when it ran. In the original order, qc.x(0) would restore $x_0$ first, and then qc.ccx(0, 1, 3) would add $x_0\wedge x_1$ to q3 instead of removing $\bar x_0\wedge x_1$ .

7 / 12 · Worked example

Worked example: oracles that clean up

In the first programs below, q0–q2 hold the input, q3 is the work qubit and q4 is the output.

Worked example

A three-input AND, then your turn

Goal: $U_f$ for $f(x) = x_0\wedge x_1\wedge x_2$ . A Toffoli has two controls, so the AND of three bits needs one intermediate result in the work qubit.

Compute
qc.ccx(0, 1, 3) writes $x_0\wedge x_1$ into the work qubit $w$ (q3).
Copy
qc.ccx(2, 3, 4) flips $y$ when $x_2 = 1$ and $w = 1$ , so $y$ becomes $y\oplus(x_0\wedge x_1\wedge x_2)$ . The last AND happens inside the copy step, which saves a second work qubit.
Uncompute
qc.ccx(0, 1, 3) again: $w$ held $x_0\wedge x_1$ , and the Toffoli adds $x_0\wedge x_1$ once more, giving 0. Trace for $x = 111$ , $y = 0$ : $\ket{111}\ket0\ket0\to\ket{111}\ket1\ket0\to\ket{111}\ket1\ket1\to\ket{111}\ket0\ket1$ . Three gates, one work qubit, nothing left behind.
Your turn: uncompute
The program computes $f(x) = (x_0\vee x_1)\wedge x_2$ the way the “Work qubits” step did, but it stops before the uncompute and leaves q3 holding $x_0\vee x_1$ .
Your turn
Add the uncompute lines at the end, so that q3 returns to 0 on every input. The grader tries all 16 basis inputs ( $x$ , and $y$ = 0 or 1), so don’t add gates that set the input.
```
from qiskit import QuantumCircuit

qc = QuantumCircuit(5)   # q0, q1, q2: the input x;  q3: work w;  q4: output y
# compute x0 OR x1 into the work qubit q3
qc.ccx(0, 1, 3, ctrl_state='00')   # flips q3 when q0 = 0 and q1 = 0
qc.x(3)                            # so now q3 = x0 OR x1

# copy: AND the work qubit with x2 into the output
qc.ccx(2, 3, 4)

# uncompute: undo the compute lines, last one first
```
Write the program in the app’s code editor (Python with Qiskit’s circuit methods), run it, and check it.
Hints
1. Which lines computed q3? Only those need undoing; the copy line stays.
2. Undo them last one first: qc.x(3), then the anti-controlled Toffoli.
Show the answer
One program that works:
```
from qiskit import QuantumCircuit

qc = QuantumCircuit(5)   # q0, q1, q2: the input x;  q3: work w;  q4: output y
# compute x0 OR x1 into the work qubit q3
qc.ccx(0, 1, 3, ctrl_state='00')   # flips q3 when q0 = 0 and q1 = 0
qc.x(3)                            # so now q3 = x0 OR x1

# copy: AND the work qubit with x2 into the output
qc.ccx(2, 3, 4)

# uncompute: undo the compute lines, last one first
qc.x(3)
qc.ccx(0, 1, 3, ctrl_state='00')
```
The compute part was the anti-controlled Toffoli and then qc.x(3). Run backwards: qc.x(3), then qc.ccx(0, 1, 3, ctrl_state='00'). That returns q3 to 0 on every input and leaves q4 holding $y\oplus f(x)$ .

One more, fully worked: $f(x) = \bar x_0\wedge x_1\wedge x_2$ , where the order of the uncompute matters.

Another worked example

Another example: a negated input

Compute
qc.x(0) flips the input $x_0$ for a moment, then qc.ccx(0, 1, 3) writes $\bar x_0\wedge x_1$ into $w$ . The compute part changed an input qubit, so the uncompute must change it back.
Copy
qc.ccx(2, 3, 4) adds $w\wedge x_2 = \bar x_0\wedge x_1\wedge x_2$ into $y$ .
Uncompute
Reverse order: qc.ccx(0, 1, 3) first, while $x_0$ is still flipped, so it removes $\bar x_0\wedge x_1$ from $w$ ; then qc.x(0) restores $x_0$ . Trace for $x = 011$ , $y = 0$ : $\ket{011}\ket0\ket0\to\ket{111}\ket0\ket0\to\ket{111}\ket1\ket0\to\ket{111}\ket1\ket1\to\ket{111}\ket0\ket1\to\ket{011}\ket0\ket1$ . The other order would restore $x_0$ too early and leave $w = x_0\wedge x_1\oplus\bar x_0\wedge x_1 = x_1$ behind.

Check yourself

Now without help: write $U_f$ for $f(x) = x_0\wedge x_1\wedge x_2\wedge x_3$ . q0–q3 hold $x$ , q4 and q5 are work qubits that must end at 0, and q6 is the output $y$ . The grader tries all 32 basis inputs.

from qiskit import QuantumCircuit

qc = QuantumCircuit(7)   # q0..q3: the input x;  q4, q5: work;  q6: output y
# compute, copy into q6, uncompute

Write the program in the app’s code editor (Python with Qiskit’s circuit methods), run it, and check it.

Hints

Build the AND up one input at a time: $x_0\wedge x_1$ into q4, then that with $x_2$ into q5.
The copy can be a Toffoli from q5 and $x_3$ into q6. Then undo the q5 line, then the q4 line.

Show the answer

One program that works:

from qiskit import QuantumCircuit

qc = QuantumCircuit(7)   # q0..q3: the input x;  q4, q5: work;  q6: output y
qc.ccx(0, 1, 4)          # compute: q4 = x0 AND x1
qc.ccx(2, 4, 5)          #          q5 = x0 AND x1 AND x2
qc.ccx(3, 5, 6)          # copy:    y ^= q5 AND x3
qc.ccx(2, 4, 5)          # uncompute, last line first
qc.ccx(0, 1, 4)

Compute $x_0\wedge x_1$ into q4 and $x_0\wedge x_1\wedge x_2$ into q5; a Toffoli from q5 and q3 writes the answer into q6; the two compute Toffolis then run again in reverse order. Five Toffolis in all, and both work qubits end at 0.

8 / 12 · Learn

Phase oracles from bit oracles

In Lesson 9, a target in $\ket-$ turned the bit oracle into signs: $U_f\ket x\ket- = (-1)^{f(x)}\ket x\ket-$ . That works for any clean $U_f$ , including one built with work qubits, since compute, copy, uncompute is $U_f$ . In circuit terms: put the output in $\ket-$ , compute, copy into the output (the sign kicks back onto the branch), uncompute.

The result is a phase oracle, $\ket x\to(-1)^{f(x)}\ket x$ , with the work qubits back at 0 and the output still $\ket-$ , so both can be reused. Without the uncompute the sign lands on $\ket x\ket{g(x)}$ instead, and any later interference fails, exactly as before. Grover’s search, later in this part, needs phase oracles built this way.

Check yourself

The inputs start in $\ket+\ket+$ and $y$ in $\ket-$ . Build the phase oracle for OR, so that the inputs end in $\tfrac12\big(\ket{00} - \ket{01} - \ket{10} - \ket{11}\big)$ and $y$ stays $\ket-$ .

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

Hints

A bit oracle for OR, with $y$ in $\ket-$ , is already a phase oracle.
Use the OR oracle you built earlier: a Toffoli with two anti-controls, then $X$ on $y$ .

Show the answer

One circuit that works: controlled-X q0=0,q1=0→q2, then X on q2.

The OR oracle flips $y$ on $01$ , $10$ and $11$ , and flipping $\ket-$ gives $-\ket-$ : those three branches pick up a minus sign. The anti-controlled Toffoli alone also passes. It flips $y$ only on $00$ , which gives the opposite signs, and that is the same state up to a global phase of $-1$ .

Check yourself

Both inputs start in $\ket+$ , a work qubit $w$ in $\ket0$ and the output $y$ in $\ket-$ . Compute $x_0\wedge x_1$ into $w$ (a Toffoli from $x_0, x_1$ onto $w$ ), then CNOT $w$ into $y$ , then run the compute gates again in reverse order. What is the state of the two inputs at the end?

A $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ , with $w$ back in $\ket0$ : a clean phase oracle
B $\ket+\ket+$ : the uncompute undoes the signs along with the scratch work
CEntangled with $w$ : the signs sit on $\ket x\ket{f(x)}$ , and the inputs have no ket of their own
D $\ket+\ket+$ , unchanged: the inputs are only controls

Show the answer

Answer: A. $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ , with $w$ back in $\ket0$ : a clean phase oracle

Compute: $\tfrac12\sum_x\ket x\ket{f(x)}\ket-$ . Copy into $\ket-$ : each branch gains the sign $(-1)^{f(x)}$ . Uncompute: $w$ returns to $\ket0$ in every branch, so the inputs are left in $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ , a product with $\ket0\ket-$ .

Why not the others

B. The uncompute undoes the compute gates, not the copy. The signs came from the copy into $\ket-$ , and they stay: the inputs end in $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ .
C. The uncompute returns $w$ to $\ket0$ in every branch, so $w$ factors out. What is left on the inputs is the sign pattern, $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ .
D. Kickback: the CNOT into $\ket-$ multiplies each branch by $(-1)^{f(x)}$ . Those signs differ between branches, so the inputs change even though they only act as controls.

9 / 12 · Practice

Practice

Three items, each with new numbers when it comes back. Hints are there if you need them.

Check yourself

Build $U_f$ for $f(x) = x_0\wedge x_1$ : inputs $x_0$ (top) and $x_1$ , output $y$ (bottom), so that $\ket{x_0, x_1, y}\to\ket{x_0, x_1, y\oplus f(x)}$ . The truth table shows what your circuit does to every basis input.

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

Hints

On which inputs is $f$ equal to 1? A Toffoli flips $y$ on exactly one input pattern, and an anti-control ○ asks for a 0 in that place.
If $f$ is 1 on three of the four inputs, flip $y$ on the one input where $f$ is 0, then flip $y$ on every input with an $X$ .
Here $f$ is 1 on $11$ .

Show the answer

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

One Toffoli: it flips $y$ only on $11$ . The truth table then matches $y\oplus f(x)$ on all eight rows.

Check yourself

Deutsch–Jozsa with two input qubits and the balanced function $f(x) = x_0\oplus x_1$ . The oracle is built with a work qubit and leaves it holding $g(x) = x_0\vee x_1$ ; the output is in $\ket-$ as usual. What is the probability that the two input qubits read $00$ at the end?

$P(00) = \;?$

Hints

On $\ket{00}$ every input $x$ contributes $(-1)^{f(x)}/4$ , but contributions add only when they also share the value of $w$ .
Group the four inputs by $g(x)$ . In each group add the signs and divide by 4; then square each group’s amplitude and add.
Here $g(x) = 0$ for $00$ , and $g(x) = 1$ for $01$ and $10$ and $11$ .

Show the answer

Answer: $P(00) = \frac{1}{8}$

Grouped by $w = g(x)$ : $w = 0$ : input $00$ , sign $+1$ , amplitude $\tfrac{1}{4}$ ; $w = 1$ : inputs $01$ and $10$ and $11$ , signs $-1, -1, +1$ , amplitude $-\tfrac{1}{4}$ . So $P(00) = \big(\tfrac{1}{4}\big)^2 + \big(-\tfrac{1}{4}\big)^2 = \tfrac{1}{8}$ .

After the last Hadamards, the amplitude of $\ket{00}\ket{w}\ket-$ is $\tfrac14\sum(-1)^{f(x)}$ over the inputs with $g(x) = w$ , because only those land on that basis state. $w = 0$ : input $00$ , sign $+1$ , amplitude $\tfrac{1}{4}$ . $w = 1$ : inputs $01$ and $10$ and $11$ , signs $-1, -1, +1$ , amplitude $-\tfrac{1}{4}$ . Square and add: $P(00) = \big(\tfrac{1}{4}\big)^2 + \big(-\tfrac{1}{4}\big)^2 = \tfrac{1}{8}$ . Without the leftover all four signs would share one sum, giving $0$ .

Common slips

$0$ : That is the answer without the leftover. Here $w$ holds $g(x)$ , so on $\ket{00}$ only inputs with the same value of $g(x)$ can add or cancel.
$\frac{1}{4}$ : That squares each input’s contribution on its own, as if every input had a different value of $w$ . Inputs with the same $g(x)$ do share a basis state, so their contributions add before you square.

Check yourself

The compute part $C$ of an oracle uses 7 gates, each an $X$ , CNOT or Toffoli, and leaves a 1-bit answer in work qubits. The clean oracle computes, copies each answer bit into an output qubit with one CNOT, and uncomputes. How many gates does it use?

Hints

What does the uncompute consist of, and how long is it?
The uncompute is $C$ backwards: 7 gates again. The copy is one CNOT per answer bit.

Show the answer

Answer: $15$

7 to compute, 1 to copy, 7 to uncompute: $2\cdot 7 + 1 = 15$ .

Common slips

$8$ : That leaves out the uncompute. Running $C$ backwards costs another 7 gates, the price of leaving nothing behind.
$14$ : That leaves out the copy: one CNOT per answer bit, 1 more.
$16$ : The answer is copied once, between the compute and the uncompute: one CNOT per answer bit, not two.

10 / 12 · Explain

Explain it

A friend says: “The work qubit is never measured, so whatever the oracle leaves in it can’t change the answer.” Using Deutsch’s algorithm, explain what goes wrong, and how compute, copy, uncompute fixes it.

Show a model answer

If the oracle leaves $w$ holding $x$ , the state before the last $H$ is $\tfrac{1}{\sqrt2}\big((-1)^{f(0)}\ket0\ket0 + (-1)^{f(1)}\ket1\ket1\big)\ket-$ : the input is entangled with $w$ . The last $H$ sends each branch to both outcomes of the input, but the two branches land on different values of $w$ , and amplitudes only add or cancel on the same basis state of every qubit. So the signs never meet, and the input reads 0 or 1 at random; nobody has to measure $w$ for this to happen. Uncomputing runs the scratch gates backwards after the answer has been copied into $y$ . That returns $w$ to $\ket0$ in every branch, so it factors out, the branches meet again, and the answer is certain.

A good answer covers

The leftover in $w$ differs between the branches, so the input is entangled with $w$
Interference needs the branches to land on the same basis state of all the qubits; with $w$ different they can’t add or cancel, so the result is 50/50
Uncomputing after the copy returns $w$ to $\ket0$ in every branch, so it factors out and the interference is back
The copied answer survives the uncompute, because the uncompute never touches $y$

11 / 12 · Mastery check

Mastery check

Check yourself

Deutsch’s algorithm for $f(x) = \bar x$ , with one change: the oracle uses a work qubit $w$ , starting in $\ket0$ , for scratch work, and leaves it holding a copy of the input, $w = x$ . The output qubit is in $\ket-$ as usual, and nobody measures $w$ . What does the 0/1 measurement of the input qubit give after the last $H$ ?

A0 or 1, each with probability $\tfrac12$
B0 every time
C1 every time, as in the algorithm without $w$
DThe answer moves into $w$ : measuring $w$ would give $f(0)\oplus f(1)$

Show the answer

Answer: A. 0 or 1, each with probability $\tfrac12$

Before the last $H$ the state is $\tfrac{1}{\sqrt2}\big(-\ket0\ket0 +\ket1\ket1\big)\ket-$ , so the input is entangled with $w$ . The last $H$ sends each branch to both outcomes of the input, but the branches land on different values of $w$ , so their amplitudes never add or cancel. Each outcome has probability $\tfrac12$ .

Why not the others

B. Nothing flips the answer. A leftover that records $x$ stops the two signs from meeting at all, so neither outcome is certain.
C. Nobody measures $w$ , but it is not idle: the branch $x = 0$ carries $w = 0$ and the branch $x = 1$ carries $w = 1$ . The last $H$ can only combine amplitudes that sit on the same basis state of every qubit, so the two signs never meet, and the input reads 0 or 1 at random.
D. $w$ only ever holds $w = x$ , which says nothing about $f$ ; measured, it gives the input’s value, 0 or 1 at random. With $y$ in $\ket-$ , the values of $f$ become signs on the input’s branches, not bits in $w$ .

Check yourself

Build $U_f$ for $f(x) = x_0\wedge x_1$ : inputs $x_0$ (top) and $x_1$ , output $y$ (bottom), so that $\ket{x_0, x_1, y}\to\ket{x_0, x_1, y\oplus f(x)}$ . The truth table shows what your circuit does to every basis input.

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

Hints

On which inputs is $f$ equal to 1? A Toffoli flips $y$ on exactly one input pattern, and an anti-control ○ asks for a 0 in that place.
If $f$ is 1 on three of the four inputs, flip $y$ on the one input where $f$ is 0, then flip $y$ on every input with an $X$ .
Here $f$ is 1 on $11$ .

Show the answer

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

One Toffoli: it flips $y$ only on $11$ . The truth table then matches $y\oplus f(x)$ on all eight rows.

Check yourself

Deutsch–Jozsa with two input qubits and the constant function $f(x) = 0$ . The oracle is built with a work qubit and leaves it holding $g(x) = x_0$ ; the output is in $\ket-$ as usual. What is the probability that the two input qubits read $00$ at the end?

$P(00) = \;?$

Hints

On $\ket{00}$ every input $x$ contributes $(-1)^{f(x)}/4$ , but contributions add only when they also share the value of $w$ .
Group the four inputs by $g(x)$ . In each group add the signs and divide by 4; then square each group’s amplitude and add.
Here $g(x) = 0$ for $00$ and $01$ , and $g(x) = 1$ for $10$ and $11$ .

Show the answer

Answer: $P(00) = \frac{1}{2}$

Grouped by $w = g(x)$ : $w = 0$ : inputs $00$ and $01$ , signs $+1, +1$ , amplitude $\tfrac{1}{2}$ ; $w = 1$ : inputs $10$ and $11$ , signs $+1, +1$ , amplitude $\tfrac{1}{2}$ . So $P(00) = \big(\tfrac{1}{2}\big)^2 + \big(\tfrac{1}{2}\big)^2 = \tfrac{1}{2}$ .

After the last Hadamards, the amplitude of $\ket{00}\ket{w}\ket-$ is $\tfrac14\sum(-1)^{f(x)}$ over the inputs with $g(x) = w$ , because only those land on that basis state. $w = 0$ : inputs $00$ and $01$ , signs $+1, +1$ , amplitude $\tfrac{1}{2}$ . $w = 1$ : inputs $10$ and $11$ , signs $+1, +1$ , amplitude $\tfrac{1}{2}$ . Square and add: $P(00) = \big(\tfrac{1}{2}\big)^2 + \big(\tfrac{1}{2}\big)^2 = \tfrac{1}{2}$ . Without the leftover all four signs would share one sum, giving $1$ .

Common slips

$1$ : That is the answer without the leftover. Here $w$ holds $g(x)$ , so on $\ket{00}$ only inputs with the same value of $g(x)$ can add or cancel.
$\frac{1}{4}$ : That squares each input’s contribution on its own, as if every input had a different value of $w$ . Inputs with the same $g(x)$ do share a basis state, so their contributions add before you square.

Check yourself

Start with $x = 10$ , a work qubit $w = 0$ and the output $y = 0$ . Compute $\overline{x_0\wedge x_1}$ into $w$ (a Toffoli, then $X$ on $w$ ). Copy $w$ into $y$ with a CNOT. Then uncompute: $X$ on $w$ , then the Toffoli. What are $w$ and $y$ at the end?

A $w = 0$ , $y = 0$
B $w = 0$ , $y = 1$
C $w = 1$ , $y = 1$
D $w = 1$ , $y = 0$

Show the answer

Answer: B. $w = 0$ , $y = 1$

Compute: $w = f(10) = 1$ . Copy: $y = 0\oplus 1 = 1$ , and $w$ is left as it was. Uncompute: the compute gates in reverse order turn $w$ back into 0, and they never touch $y$ . So $w = 0$ and $y = 1$ .

Why not the others

A. That treats the uncompute as undoing everything. It runs only the compute gates backwards, and those never touch $y$ . The copy wrote $f(x) = 1$ into $y$ , and nothing undoes it: $y$ ends at $0\oplus 1 = 1$ .
C. The uncompute does clear $w$ . The copy only read $w$ , so $w$ still holds $f(x) = 1$ when the uncompute starts, and running the compute gates backwards turns it back into 0.
D. That leaves the answer stuck in $w$ . The copy CNOT has control $w = 1$ , so it does flip $y$ , to $1$ ; then the uncompute returns $w$ to 0.

Check yourself

This compute part $C$ writes $x_0\wedge x_1\wedge x_2\wedge x_3$ into q6, using q4 and q5 for scratch: qc.ccx(0, 1, 4), then qc.ccx(2, 4, 5), then qc.ccx(3, 5, 6). A CNOT then copies q6 into the output qubit. Put the three gates of the uncompute in order, first at the top.

Put these in order.

qc.ccx(2, 4, 5)
qc.ccx(3, 5, 6)
qc.ccx(0, 1, 4)

Show the answer

qc.ccx(3, 5, 6)
qc.ccx(2, 4, 5)
qc.ccx(0, 1, 4)

Undo the last gate first: qc.ccx(3, 5, 6), then qc.ccx(2, 4, 5), then qc.ccx(0, 1, 4). Each gate is its own inverse, and each one can only be undone while the qubits it reads hold what they held when it ran. In the original order, qc.ccx(0, 1, 4) would clear q4 first, and then qc.ccx(2, 4, 5) could no longer clear q5, because it needs q4 to still hold $x_0\wedge x_1$ .

Check yourself

Both inputs start in $\ket+$ , a work qubit $w$ in $\ket0$ and the output $y$ in $\ket-$ . Compute $x_0\wedge x_1$ into $w$ (a Toffoli from $x_0, x_1$ onto $w$ ), then CNOT $w$ into $y$ , then run the compute gates again in reverse order. What is the state of the two inputs at the end?

A $\ket+\ket+$ : the uncompute undoes the signs along with the scratch work
B $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ , with $w$ back in $\ket0$ : a clean phase oracle
CEntangled with $w$ : the signs sit on $\ket x\ket{f(x)}$ , and the inputs have no ket of their own
D $\ket+\ket+$ , unchanged: the inputs are only controls

Show the answer

Answer: B. $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ , with $w$ back in $\ket0$ : a clean phase oracle

Compute: $\tfrac12\sum_x\ket x\ket{f(x)}\ket-$ . Copy into $\ket-$ : each branch gains the sign $(-1)^{f(x)}$ . Uncompute: $w$ returns to $\ket0$ in every branch, so the inputs are left in $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ , a product with $\ket0\ket-$ .

Why not the others

A. The uncompute undoes the compute gates, not the copy. The signs came from the copy into $\ket-$ , and they stay: the inputs end in $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ .
C. The uncompute returns $w$ to $\ket0$ in every branch, so $w$ factors out. What is left on the inputs is the sign pattern, $\tfrac12\big(\ket{00} + \ket{01} + \ket{10} - \ket{11}\big)$ .
D. Kickback: the CNOT into $\ket-$ multiplies each branch by $(-1)^{f(x)}$ . Those signs differ between branches, so the inputs change even though they only act as controls.

Check yourself

Write $U_f$ for $f(x) = \bar x_0\wedge x_1\wedge \bar x_2$ . q0–q2 hold $x$ , q3 is a work qubit that starts at 0 and must end at 0, and q4 is the output $y$ . For a negated input use an anti-control: an $X$ before and after on that input, or ctrl_state with a 0 in that place (its rightmost character belongs to the first control). The grader tries all 16 basis inputs ( $x$ , and $y$ = 0 or 1), so don’t add gates that set the input.

from qiskit import QuantumCircuit

qc = QuantumCircuit(5)   # q0, q1, q2: the input x;  q3: work w;  q4: output y
# compute into q3, combine with the third input into q4, then uncompute q3

Write the program in the app’s code editor (Python with Qiskit’s circuit methods), run it, and check it.

Show the answer

One program that works:

from qiskit import QuantumCircuit

qc = QuantumCircuit(5)   # q0, q1, q2: the input x;  q3: work w;  q4: output y
qc.ccx(0, 1, 3, ctrl_state='10')   # compute: w = NOT x0 AND x1
qc.ccx(2, 3, 4, ctrl_state='10')   # copy: y ^= w AND NOT x2
qc.ccx(0, 1, 3, ctrl_state='10')   # uncompute w

Compute the first two literals into $w$ , combine $w$ with the third into $y$ , and undo the first step: qc.ccx(0, 1, 3, ctrl_state='10'), qc.ccx(2, 3, 4, ctrl_state='10'), qc.ccx(0, 1, 3, ctrl_state='10'). In ctrl_state the rightmost character belongs to the first control, and a 0 makes that control an anti-control. An $X$ before and after on a negated input works too.

12 / 12 · Recap

Recap

From memory

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

Why does a work qubit left holding $g(x)$ spoil Deutsch’s algorithm? When is a leftover harmless?
Show the key points
- The leftover is entangled with the input: the branches carry different values of $w$
- Amplitudes add or cancel only on the same basis state of every qubit, so the last $H$ can’t make the branches interfere
- A leftover that is the same in every branch factors out and does no harm
Describe compute, copy, uncompute, and what it costs.
Show the key points
- Compute $f$ into work qubits with $C$ ; CNOT the answer into the output; run the gates of $C$ in reverse order
- The work qubits return to 0 and the copied answer stays, since $C^{-1}$ never touches the output
- About twice the gates of $C$ : $2k + c$ ; the work qubits are free again afterwards
How do you get a phase oracle from gates?
Show the key points
- Put the output in $\ket-$ : the copy step kicks back $(-1)^{f(x)}$
- Uncompute, so the work qubits are back at 0 and the inputs carry only the signs
- Without the uncompute the signs sit on $\ket x\ket{g(x)}$ and later interference fails

Key ideas

$X$ , CNOT and Toffoli, with anti-controls (○) where a 0 should fire the gate, build $U_f\ket{x,y} = \ket{x, y\oplus f(x)}$ for any Boolean $f$ . Functions of more bits need work qubits for intermediate results.
A work qubit left holding $g(x)$ is entangled with the input. Branches with different $w$ can’t interfere, so Deutsch’s algorithm becomes a coin toss when $w$ holds a copy of $x$ .
A qubit with no ket of its own still has measurement statistics, and they give a Bloch vector shorter than 1: a mixed state. Records that overlap by $c$ leave length $c$ and success probability $\tfrac12(1 + c)$ .
Compute, copy, uncompute gives $\ket x\ket0\ket y\to\ket x\ket0\ket{y\oplus f(x)}$ with $2k + c$ gates. The uncompute runs the gates backwards, last one first, and leaves the copied answer alone.
With the output in $\ket-$ , a clean bit oracle is a phase oracle: $\ket x\to(-1)^{f(x)}\ket x$ .

Go further

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

Fundamentals of quantum algorithms: Simulating classical computationsJohn Watrous, IBM Quantum · Course
Turns any Boolean circuit into Toffoli gates and shows why the garbage has to be cleaned up before it spoils interference.
UncomputationWikipedia · Article
A short reference on clearing work qubits by running a computation backwards, and how it changes interference.
Landauer’s principleWikipedia · Article
Why erasing a bit must give off heat, the original motive for computing reversibly.
General formulation of quantum information: Density matricesJohn Watrous, IBM Quantum · Course
Goes past this lesson’s mixed states to density matrices, which describe one part of an entangled system exactly.