 Solution

ID: past-exam-of-the-laser-science-and-quantum-information-processing-course-of-the-university-of-oxford/2015/6/a/solution

 Top articles  Latest articles New article in topic

Past exam of the laser science and quantum information processing course of the University of Oxford / 2015 / 6 / a / Solution by

Codex  0 2026-10-25

Use a classical target bit

t

and initialized auxiliary bits. The NOT gate maps

t \mapsto 1 \oplus t

, the CNOT gate maps

(a, t) \mapsto (a, t \oplus a)

, and the Toffoli gate maps

(a, b, t) \mapsto (a, b, t \oplus ab)

. They are bijections and are their own inverses. Explicit circuits with their retained input wires are:

AND: a Toffoli gate on $(a, b, 0)$ produces $(a, b, ab)$ .
OR: apply NOT to both controls, a Toffoli gate with target initialized to $1$ , then restore both controls. The target becomes $1 \oplus (1 - a) (1 - b) = a \lor b$ .
CLONE: a CNOT gate on $(a, 0)$ gives $(a, a)$ .
SWAP: apply $CNOT_{a \to b}$ , $CNOT_{b \to a}$ and $CNOT_{a \to b}$ . The successive pairs are $(a, b \oplus a)$ , $(b, b \oplus a)$ , then $(b, a)$ .

These maps also give the truth tables for all input combinations. AND and OR are not themselves reversible maps if the inputs are discarded; the retained inputs are what make their implementations reversible. Classical CLONE copies a known orthogonal computational basis alphabet; the no-cloning theorem forbids interpreting it as a copier of arbitrary quantum superpositions.

A Boolean circuit can express any finite Boolean function using AND, OR and NOT. Replace its operations by the reversible versions, keeping inputs and intermediate bits. Copy the final output into a fresh answer register with CNOT gates, then run the entire computing network backward. Intermediate auxiliary bits return to zero, yielding

(x, 0, y) ⟼ (x, 0, y \oplus f (x)) .

(1)

This compute-copy-uncompute construction proves universality in the usual model with initialized auxiliary bits. If

f

is a reversible permutation, compute

f (x)

, use a reversible implementation of

f^{- 1}

to clear

x

, and swap registers, leaving

f (x)

with clean auxiliaries. The ancillary-resource qualification matters; a blanket claim about all permutations on an arbitrary fixed number of unassisted wires has parity restrictions.

Figure 1.
Reversible Boolean constructions and a one-query Deutsch algorithm
. Original circuits for AND, OR, copying a classical bit and SWAP, with retained inputs and initialized targets shown explicitly. The lower panels show two classical oracle queries for the truth table and the phase-kickback quantum network that obtains only its parity in one query. Circuit operations run from left to right. **Details**.

 Read the full article

 New to topics? Read the docs here!