Reversible Computation

A reversible computation preserves enough information to reconstruct every declared input from its output. For a finite logical state space this means a bijection on the complete state space, not merely an injective rule on the subset of inputs that happens to be used. A promise-subspace action can be useful, but it becomes a physical gate only after one specifies a bijective extension to all basis states.

This distinction is the bridge from classical functions to quantum circuits. Ideal closed-system quantum gates are unitary and therefore invertible. Many-to-one Boolean functions, measurements, reset, discard, noise, and reduced dynamics on visible subsystems need not be reversible on the displayed registers. To use an ordinary classical function coherently, one must embed it in a larger reversible transformation, name every auxiliary register, and remove temporary records without destroying interference.

Required background. Bits, Qubits, Qudits, and Modes supplies computational-basis registers and their encodings. Unitary Operators supplies inner-product preservation, adjoints, and inverse operators.

Logical Reversibility of Classical Maps

Let $X$ and $Y$ be finite sets and let $f:X\to Y$ be deterministic. The map is injective when distinct inputs have distinct outputs, surjective when every declared output occurs, and bijective when both conditions hold. A deterministic operation on one complete finite logical state space is reversible precisely when it is bijective. Its inverse then assigns one and only one predecessor to every output.

For equal-size bit registers, a reversible operation is therefore a permutation of all bit strings. NOT is reversible because it exchanges $0$ and $1$. The one-output AND map is not: $00$, $01$, and $10$ all map to $0$. The two-input XOR function is also many-to-one when written as

$$(a,b)\longmapsto a\oplus b,$$

but the two-wire controlled-NOT action

$$(a,b)\longmapsto(a,a\oplus b)$$

is bijective because the retained first bit distinguishes the two XOR fibers.

The fiber of $f$ over $z\in Y$ is

$$f^{-1}(z)=\{x\in X:f(x)=z\}.$$

Fiber size measures exactly how much distinguishing information the output value $z$ fails to retain. This page develops that finite-map language locally. Sets, Functions, and Maps owns the general mathematical theory.

A promise changes the question but not the gate requirement. Suppose an operation is requested only on $P\subset X$. Injectivity on $P$ is necessary for a reversible promised action, yet it says nothing about inputs in $X\setminus P$. A complete circuit must state the ambient register space and give a permutation on every basis string, or prove that the promised isometry extends to such a permutation.

The Ten-Field Reversible-Circuit Record

Every reversible-implementation claim should fill the following record. Write N/A and justify it when a field genuinely does not apply. Leaving the field blank is not an acceptable convention.

1. Classical task, domain, codomain, and promise — Give the function or relation, the complete finite sets, and any promised input subset.
2. Register names, order, widths, and basis encoding — Name every register, fix the tensor-factor order, state bit significance, and identify the computational basis.
3. Input, output, and preservation contract — Say which input data remain, which register holds the useful result, and what must be reconstructible.
4. Clean and dirty ancilla assumptions — A clean ancilla begins in a named standard state; a dirty ancilla may be unknown and must be returned to exactly that state.
5. Reversible embedding and explicit inverse — State the full map on all basis strings, not only the intended input slice, and give or derive its inverse.
6. Gate alphabet and phase semantics — Declare ideal primitives, allowed constants and wire permutations, and whether a phase-free permutation or a relative-phase implementation is required.
7. Garbage, copied data, and cleanup condition — Identify unwanted records, copied basis labels, reusable lines, and the state to which each line must return.
8. Width, size, depth, and maximum live workspace — Keep simultaneous wires, primitive count, scheduling layers, and peak temporary storage as separate quantities.
9. Exactness, error metric, and verification evidence — Report truth-table coverage, inverse and norm residuals, phase-sensitive tests, and, for approximate blocks, a declared operator or channel metric.
10. Licensed conclusion and canonical handoff — State only the achieved reversible contract and route synthesis, hardware, algorithmic, or thermodynamic questions to their owners.

A basis truth table is necessary but not sufficient for a coherent quantum implementation. It verifies where basis labels go, but it cannot detect input-dependent phases. At least one superposition test is required whenever the phase convention matters.

Why Many-to-One Logic Cannot Be Unitary

Assume that two distinct classical inputs $x\ne x'$ have the same function value:

$$f(x)=f(x').$$

Their computational-basis states are orthogonal,

$$\langle x'|x\rangle=0.$$

If a closed-system operator attempted to implement the output-only rule

$$|x\rangle\longmapsto|f(x)\rangle,$$

then these two orthogonal states would be sent to the same normalized state. Their output inner product would be one:

$$\langle f(x')|f(x)\rangle=1.$$

No unitary can change an inner product from zero to one. The obstruction is not specifically quantum; it is the absence of a single-valued logical inverse. Quantum mechanics makes the obstruction especially sharp because inner products, including relative phase information, must be preserved by closed-system evolution.

There are three distinct resolutions, and they must not be conflated:

• retain enough input or history to distinguish the fibers;
• export the distinguishing record to an auxiliary system, making the enlarged evolution reversible; or
• use an irreversible operation such as reset, measurement with a forgotten record, discard, or a noisy channel on the displayed system.

The second option does not make information disappear. If a unitary maps

$$|x\rangle|0\rangle_E \longmapsto |f(x)\rangle|e_x\rangle_E,$$

then the environment records $|e_x\rangle_E$ must distinguish inputs that share the same visible output. Discarding $E$ produces irreversible reduced dynamics on the visible register even though the enlarged transformation is unitary. General dilations and reduced channels belong to Quantum Channels and Noise.

Reversible Embeddings and Permutation Matrices

Let $\pi$ be a permutation of a finite basis-label set. Its phase-free quantum representation is

$$U_\pi = \sum_x |\pi(x)\rangle\langle x|.$$

Because a permutation relabels an orthonormal basis,

$$U_\pi^\dagger=U_{\pi^{-1}}, \qquad U_\pi^\dagger U_\pi=I.$$

Thus every finite classical reversible gate defines a unitary permutation matrix. The converse is false: most unitaries create superpositions and are not permutation matrices.

For an $m$-bit function $f$, the standard XOR embedding retains the input and adds its value into an $m$-bit target:

$$U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle.$$

Bitwise XOR is its own inverse, so

$$U_f^2=I$$

for every declared target value $y$, not only for a clean target $y=0$. Replacing XOR by addition in another finite group still yields a reversible embedding, but the inverse then uses the group inverse and need not equal the forward map.

An alternative embedding may omit the original input and produce a useful result plus a garbage label:

$$x\longmapsto\bigl(f(x),g(x)\bigr).$$

The pair $(f,g)$ must be injective. If $G$ is the garbage alphabet, every element of the largest fiber requires a distinct garbage label:

$$|G| \geq \max_z |f^{-1}(z)|.$$

For a binary garbage register of width $r$,

$$r \geq \left\lceil \log_2\!\left(\max_z |f^{-1}(z)|\right) \right\rceil.$$

This lower bound applies only when the original input is not retained. In the XOR embedding, $x$ already distinguishes the fibers, so it is not an additional-garbage lower bound.

Register dimensions must balance as well. If $(f,g)$ occupies more output wires than the logical input, the implementation needs named input ancillas. An injective rule on the clean-ancilla slice must then be extended to a full permutation of all basis strings. Specifying only

$$|x,0^a\rangle\longmapsto|f(x),g(x)\rangle$$

does not define what the gate does when an ancilla is not zero.

Toffoli and Fredkin Gates

The Toffoli gate, or controlled-controlled-NOT, acts on ordered bits $(a,b,t)$ as

$$T(a,b,t)=(a,b,t\oplus ab).$$

It is an involution because applying the same conditional XOR twice cancels:

$$T^2=I.$$

With $t=0$, the target receives AND while the two inputs remain available. With $t=1$, the target receives NAND. Toffoli is universal for reversible Boolean computation only after one declares initialized constants, allowed ancillas, wire permutations, and garbage-output conventions. The symbol alone says nothing about whether a device implements it natively or how it is synthesized.

The Fredkin gate is a controlled swap. For ordered bits $(c,a,b)$,

$$F(c,a,b) = \bigl(c,(1-c)a+cb,(1-c)b+ca\bigr).$$

When $c=0$, it leaves $a,b$ fixed; when $c=1$, it exchanges them. Fredkin is also an involution and preserves Hamming weight. Its conservative universality depends on the encoding and allowed auxiliary resources. Weight conservation is a stronger restriction than logical reversibility, not a property shared by every reversible gate.

Multi-Qubit Gates owns the full matrix conventions, entangling behavior, and native-versus-compiled interpretation of multi-qubit gates. Here Toffoli and Fredkin serve as reversible-logic primitives. A relative-phase Toffoli may realize the same classical label permutation but is not automatically an exact replacement in a coherent circuit.

Ancillas, Garbage, and Workspace

An ancilla is an auxiliary register with an explicit state contract. A clean ancilla begins in a known standard state such as $|0\rangle$. A dirty ancilla begins in an unknown state that the computation may temporarily modify but must restore exactly. Calling a line “workspace” does not determine which contract applies.

For example, applying CNOT from a data bit $x$ to a target initially in $w_0$ produces

$$w'=w_0\oplus x.$$

This target holds $x$ only when $w_0=0$. If $w_0$ is unknown, it can still serve as dirty workspace inside a larger construction, but the final circuit must return it to $w_0$.

Garbage means an output record that is not part of the useful answer but is needed to keep the transformation invertible. Preserved inputs are not intrinsically garbage; they become unwanted residual records only relative to a task that requests the function value alone. Temporary work values are likewise harmless if they are coherently returned to their initial states.

Garbage becomes operationally important on superpositions. Suppose a computation produces

$$|\Psi\rangle = \sum_x \alpha_x |x\rangle|f(x)\rangle|g(x)\rangle.$$

If the work states $|g(x)\rangle$ differ, discarding the work register multiplies each retained off-diagonal term by

$$\langle g(x')|g(x)\rangle.$$

Orthogonal garbage records erase coherence between the corresponding branches of the reduced state. The global state remains pure; the apparent irreversibility arises because a distinguishing record has been ignored.

Workspace accounting should therefore state both maximum live occupancy and final occupancy. A line that is eventually cleaned may still determine the peak width, routing burden, or fault-tolerant qubit requirement. Circuit Model owns the general definitions of width, size, depth, and register semantics.

Compute–Copy–Uncompute

Assume an exact reversible block computes an $m$-bit basis label while retaining its input:

$$V_f|x\rangle|0^a\rangle|0^m\rangle = |x\rangle|g(x)\rangle|f(x)\rangle.$$

Running $V_f^\dagger$ immediately would clean the workspace but also erase the computed result. Bennett’s compute–copy–uncompute pattern first transfers the orthogonal result label to a separate clean register:

$$\begin{aligned} \sum_x\alpha_x|x,0^a,0^m,0^m\rangle &\xrightarrow{V_f} \sum_x\alpha_x|x,g(x),f(x),0^m\rangle \\ &\xrightarrow{\text{basis-label copy}} \sum_x\alpha_x|x,g(x),f(x),f(x)\rangle \\ &\xrightarrow{V_f^\dagger} \sum_x\alpha_x|x,0^a,0^m,f(x)\rangle. \end{aligned}$$

For bit strings, the middle operation is a bank of CNOTs or controlled additions. It copies an orthogonal computational-basis label, not an arbitrary unknown state. The resulting state can still entangle the input with the useful output. No-Cloning and No-Signaling owns the theorem that forbids copying arbitrary unknown quantum states.

Uncomputation has three essential preconditions:

• the controls and other inputs required by $V_f^\dagger$ remain coherently available;
• the implemented inverse matches the actual forward block, including relative phases; and
• the useful result has been transferred without disturbing the promised basis-label semantics.

Resetting, measuring, or discarding a work register is not uncomputation. Those operations can clean a visible line only by exporting entropy or a classical record. If an approximate inverse is used, the audit must choose a norm or channel metric and measure residual population, phase error, and entanglement in the supposedly clean registers.

Uncomputation can reduce final garbage while increasing size and depth. Reversible simulation more generally trades time, space, and irreversible erasures; there is no convention-independent constant-overhead theorem for every computation.

Basis Permutations, Relative Phases, and Quantum Coherence

A classical truth table records only the output basis label. A coherent quantum gate may instead be a monomial unitary

$$U|x\rangle=e^{i\theta_x}|\pi(x)\rangle.$$

This gate and the phase-free permutation $U_\pi$ have the same basis-label truth table. They are equivalent on every coherent input only when the phases form one global phase, or when the surrounding declared circuit cancels all relative phases.

The smallest counterexample compares $I$ and $Z$. Both leave the labels $0$ and $1$ unchanged, but

$$I|+\rangle=|+\rangle, \qquad Z|+\rangle=|-\rangle.$$

A basis-state measurement cannot distinguish them on the inputs $|0\rangle$ and $|1\rangle$; an interference experiment can. Similarly, a relative-phase Toffoli may be cheaper in a chosen synthesis model and entirely correct inside a circuit where the phases cancel, while failing a contract that demands the exact phase-free Toffoli.

Phase-sensitive verification can prepare superpositions, apply the candidate and ideal inverse, and measure in complementary bases. For an exact finite gate, a direct matrix check can report

$$\|U_{\mathrm{candidate}}-e^{i\phi}U_{\mathrm{ideal}}\|$$

after minimizing over one allowed global phase. The norm, tolerance, and whether the comparison is on the full space or a promise subspace must be stated.

Permutation unitaries are therefore a strict subset of quantum gates. They coherently implement classical reversible logic, but general unitaries can rotate amplitudes and phases without corresponding to any deterministic classical truth function. Universal Gate Sets owns exact and approximate universality for the larger unitary group.

Universality, Cost Models, and Physical Reversibility

“Universal” is meaningful only relative to a target class and a resource contract. Toffoli with initialized constants and garbage conventions supports universal reversible Boolean computation. Fredkin supports a conservative form of universality with an appropriate encoding and auxiliaries. Neither statement establishes universality for arbitrary quantum unitaries, efficient synthesis in a hardware alphabet, or a useful fault-tolerant implementation.

For a forward block of abstract size $G$ and depth $D$ that computes an $m$-bit result, a simple compute–parallel-copy–uncompute estimate is

$$G_{\mathrm{clean}}=2G+m, \qquad D_{\mathrm{clean}}=2D+1.$$

These formulas require the inverse gates to have the same abstract cost, all $m$ copy operations to fit in one layer, sufficient connectivity, and no hidden routing or scheduling overhead. Width, maximum live workspace, primitive counts, and depth remain separate. Gate Decomposition owns synthesis into a chosen gate alphabet and topology, while Resource Estimation Tools owns propagation to logical, fault-tolerant, physical, and operational resources.

Query cost is another distinct abstraction. A reversible predicate may be counted as one oracle query while hiding arithmetic, data access, workspace, copying, and cleanup. Phase Kickback owns the clean XOR-to-phase consequence and its compute–phase–uncompute audit; this page retains reversible embeddings, workspace, garbage, and the generic uncomputation construction. Quantum Oracles owns the query domain and promises, complete full-space extension, separately licensed forward, inverse, controlled, and powered access, reductions between oracle forms, and the oracle-specific fair comparator. Algorithmic Primitives owns how a declared access interface composes with phase, interference, and readout, while Grover Search owns the complete search-query interpretation.

Logical reversibility is also not time-reversal symmetry. A logically reversible truth table does not specify a Hamiltonian, a time-reversed protocol, thermal isolation, control precision, error rate, or switching speed. Real implementations can dissipate energy through control, noise, error correction, leakage, and reset even when the ideal logical operation is a permutation.

Landauer Principle owns the thermodynamic statement that entropy-reducing erasure under declared bath and cycle assumptions has a heat or work lower bound. That bound is not a fixed energy charge per Toffoli, unitary, measurement, or gate symbol. Logical reversibility removes one source of compulsory erasure; it does not by itself prove a zero-dissipation, finite-time, reliable computer.

Worked Audit: AND through a Toffoli Embedding

This exact synthetic analytic audit treats $f(a,b)=ab$ with no promise. The register order is the big-endian basis $|abt\rangle$, and $t$ is a clean target.

1. Classical task, domain, codomain, and promise — Evaluate AND from $\{0,1\}^2$ to $\{0,1\}$ on all four inputs.
2. Register names, order, widths, and basis encoding — Use three one-bit registers in order $(a,b,t)$ and basis order $000,001,\ldots,111$.
3. Input, output, and preservation contract — Initialize $t=0$, preserve $a,b$, and return $ab$ in $t$.
4. Clean and dirty ancilla assumptions — The target is clean $|0\rangle$; there are no dirty ancillas.
5. Reversible embedding and explicit inverse — Use $T(a,b,t)=(a,b,t\oplus ab)$. Its inverse is the same Toffoli.
6. Gate alphabet and phase semantics — Use one ideal phase-free Toffoli; compilation and native realization are outside this audit.
7. Garbage, copied data, and cleanup condition — No temporary workspace is created. The preserved input pair is part of the output record, not erased data.
8. Width, size, depth, and maximum live workspace — Width $3$, size one Toffoli, depth $1$, and no separate temporary line. Compiled, native, fault-tolerant, and physical costs are N/A in this abstract audit.
9. Exactness, error metric, and verification evidence — Verify all eight basis states, the inverse, normalization, and the coherent $|++0\rangle$ test below; every exact residual is zero.
10. Licensed conclusion and canonical handoff — This is one exact ideal reversible embedding of AND. Multi-qubit matrices, synthesis, hardware, and thermodynamics remain with their accepted owners.

The full permutation is

000 → 000    001 → 001
010 → 010    011 → 011
100 → 100    101 → 101
110 → 111    111 → 110

It fixes six strings and exchanges $110\leftrightarrow111$. Hence

$$T^2=I, \qquad T^\dagger T=I,$$

and the exact permutation, inverse, and state-norm residuals vanish. On the clean-target slice,

$$|a,b,0\rangle\longmapsto|a,b,ab\rangle.$$

If the input pair were not retained, output-only AND would have fiber sizes three and one. At least three garbage labels, hence two garbage bits, would be necessary. A three-output-wire construction would need a named clean third input wire and a full eight-state permutation extending

$$|a,b,0\rangle \longmapsto |ab,g_1(a,b),g_2(a,b)\rangle.$$

The ordinary Toffoli embedding instead uses the retained $a,b$ to distinguish the fibers.

For the coherent input $|++0\rangle$, the output is

$$|\Psi\rangle = \frac12 \left( |000\rangle+|010\rangle+|100\rangle+|111\rangle \right).$$

Tracing out $a,b$ gives target probabilities and eigenvalues $3/4$ and $1/4$. With base-two logarithms,

$$S(t)=h_2(1/4)=0.811278\ \text{bits}.$$

The global state is pure; the target is mixed because it is correlated with the preserved inputs. This audit licenses no native, synthesized, fault-tolerant, energetic, or thermodynamic cost claim.

Worked Audit: Coherent Parity with and without Cleanup

This second exact synthetic analytic audit computes $p=x_1\oplus x_0$ using register order $(x_1,x_0,w,z)$. The line $w$ is temporary workspace and $z$ is the durable output.

1. Classical task, domain, codomain, and promise — Evaluate two-bit parity on all four source strings, with no promise.
2. Register names, order, widths, and basis encoding — Use ordered one-bit registers $(x_1,x_0,w,z)$ and the computational basis in that order.
3. Input, output, and preservation contract — Preserve $x_1,x_0$, return parity in $z$, and restore $w$ to zero.
4. Clean and dirty ancilla assumptions — Both $w$ and $z$ begin in $|0\rangle$. The dirty-work variant below shows why this matters.
5. Reversible embedding and explicit inverse — Compute parity into $w$, copy it to $z$, then reverse the two parity CNOTs.
6. Gate alphabet and phase semantics — Use five ideal phase-free CNOTs in the stated order.
7. Garbage, copied data, and cleanup condition — The orthogonal parity label is copied once; $w$ must finish in $|0\rangle$, leaving no final garbage.
8. Width, size, depth, and maximum live workspace — Width $4$, size $5$, strict serial depth $5$, one temporary work qubit, and zero final workspace occupancy.
9. Exactness, error metric, and verification evidence — Check the clean-input basis slice, inverse action, zero norm residual, and the reduced-state coherence metrics below.
10. Licensed conclusion and canonical handoff — Exact uncomputation restores reusable workspace and parity-sector interference; it assigns no reset, hardware, or physical energy cost.

Apply the gates in this order:

CNOT x1→w
CNOT x0→w
CNOT w→z
CNOT x0→w
CNOT x1→w

Every gate touches $w$, so no two gates in this sequence share a scheduling layer. On the clean-input slice,

0000 → 0000
0100 → 0101
1000 → 1001
1100 → 1100

The first two CNOTs compute $w=p$, the middle CNOT copies that orthogonal basis label to $z$, and the final two apply the inverse computation. The exact permutation, inverse, and state-norm residuals are zero.

The clean promise is consequential. For a general initial work value $w_0$,

$$z\longmapsto z\oplus w_0\oplus p,$$

even though the final two gates restore $w_0$. The advertised parity-output contract therefore requires $w_0=0$.

Starting from $|++\rangle_X|0\rangle_w|0\rangle_z$, the cleaned state is

$$\frac12 \left( |00\rangle|0\rangle_w|0\rangle_z +|01\rangle|0\rangle_w|1\rangle_z +|10\rangle|0\rangle_w|1\rangle_z +|11\rangle|0\rangle_w|0\rangle_z \right).$$

To quantify the effect of omitted cleanup, define normalized retained-register states

$$|e\rangle = \frac{|00\rangle_X|0\rangle_z+|11\rangle_X|0\rangle_z}{\sqrt2},$$ $$|o\rangle = \frac{|01\rangle_X|1\rangle_z+|10\rangle_X|1\rangle_z}{\sqrt2}.$$

Before the two inverse CNOTs, the full state is

$$|\Omega\rangle = \frac{|e\rangle|0\rangle_w+|o\rangle|1\rangle_w}{\sqrt2}.$$

Discarding $w$ gives

$$\rho_{Xz}^{\mathrm{dirty}} = \frac12|e\rangle\langle e| +\frac12|o\rangle\langle o|.$$

The desired cleaned retained state is

$$|\psi_{Xz}\rangle = \frac{|e\rangle+|o\rangle}{\sqrt2}.$$

Using squared state fidelity and trace distance

$$D(\rho,\sigma)=\frac12\|\rho-\sigma\|_1,$$

the omitted-cleanup state has

$$\operatorname{Tr}\!\left[(\rho_{Xz}^{\mathrm{dirty}})^2\right] =\frac12, \qquad \langle\psi_{Xz}|\rho_{Xz}^{\mathrm{dirty}}|\psi_{Xz}\rangle =\frac12, \qquad D=\frac12.$$

After uncomputation the corresponding purity, fidelity, and trace-distance values are $1$, $1$, and $0$. The calculation establishes coherent cleanup, not a universal need to retain parity forever or a cost for physically resetting a device.

Common Failure Modes and Canonical Handoffs

Calling a many-to-one function a unitary. The rule $|x\rangle\mapsto|f(x)\rangle$ fails when two inputs share an output. Retain a distinguishing register, give a full reversible embedding, or model an irreversible channel.

Verifying only the clean slice. A rule on ancillas initialized to zero may define an isometry on a promise subspace without defining the gate elsewhere. Give a full permutation and its inverse.

Treating every ancilla as clean. A dirty target changes an XOR-computed result unless its unknown initial value is included in the contract. State both its initial promise and its required final state.

Silently discarding garbage. Garbage can be entangled with useful registers. Tracing it out may dephase the useful state even though all basis-label probabilities look correct.

Calling reset uncomputation. Uncomputation applies the coherent inverse and restores workspace without exporting a record. Reset, measurement, and discard are different operations owned by the general circuit and channel formalisms.

Confusing basis copying with cloning. Controlled addition can copy an orthogonal basis label into a clean target. It cannot copy an arbitrary unknown superposition.

Ignoring relative phase. Two gates may share a classical truth table and differ on superpositions. State whether relative-phase variants are allowed and include an interference test.

Overstating universality. Toffoli and Fredkin universality claims require constants, encodings, auxiliaries, garbage rules, and allowed wire permutations. Universal Gate Sets owns quantum-unitary universality.

Mixing resource currencies. Abstract gate size is not oracle-query count, Clifford+$T$ cost, physical duration, control energy, or wall-clock time. Algorithmic Primitives, Grover Search, and Gate Decomposition own those downstream distinctions.

Equating logical and physical reversibility. Logical invertibility is not time-reversal symmetry and does not guarantee dissipation-free hardware. Unitary Time Evolution owns closed-system physical evolution; Landauer Principle owns erasure thermodynamics.

The Gates, Circuits, and Computation Models guide routes the remaining gate and computation-model questions. The Quantum Information and Computation volume, What Is Quantum Information?, and the Quantum Information Roadmap place reversible computation in the broader curriculum, while Math Needed for Quantum Information supplies the supporting map and matrix language.

Exercises

1. Noninjective maps cannot be unitary

Let $f(00)=f(01)=0$. Prove that no closed-system unitary can implement $|x\rangle\mapsto|f(x)\rangle$ on both inputs.

Solution

The inputs are orthogonal:

$$\langle01|00\rangle=0.$$

The proposed outputs are the same normalized state, so

$$\langle f(01)|f(00)\rangle=\langle0|0\rangle=1.$$

A unitary preserves inner products, so it cannot implement this map without another register retaining a distinguishing record.

2. Minimum garbage for three-bit majority

Let $M(x_2,x_1,x_0)$ equal one when at least two inputs equal one. Find the minimum number of garbage bits needed for a reversible output $(M(x),g(x))$ that does not retain $x$, and construct an explicit bijection.

Solution

The zero fiber is

$$\{000,001,010,100\},$$

and the one fiber is

$$\{011,101,110,111\}.$$

Each has size four, so $|G|\ge4$ and at least two garbage bits are necessary. They are sufficient: assign labels $00,01,10,11$ within each fiber, for example

000 → (0,00)    001 → (0,01)
010 → (0,10)    100 → (0,11)
011 → (1,00)    101 → (1,01)
110 → (1,10)    111 → (1,11)

The eight outputs are distinct and exhaust the three-bit output space, so this is a bijection.

3. NAND from Toffoli

Show how a Toffoli gate evaluates NAND, and explain why the resulting operation is reversible even though NAND alone is not.

Solution

Initialize the target to one. Toffoli gives

$$T(a,b,1)=(a,b,1\oplus ab)=(a,b,\neg(ab)).$$

The target is the NAND value, while $a,b$ remain in the output. Those retained inputs distinguish the three input pairs that produce NAND value one. The full three-bit Toffoli is a permutation and is its own inverse; output-only NAND is many-to-one.

4. Fredkin audit

List the full Fredkin truth table, identify its nontrivial exchange, and verify both involution and Hamming-weight conservation.

Solution

With register order $(c,a,b)$,

000 → 000    001 → 001
010 → 010    011 → 011
100 → 100    101 → 110
110 → 101    111 → 111

The sole nontrivial exchange is $101\leftrightarrow110$; all other strings are fixed. Applying the same exchange twice returns every string, so $F^2=I$. Exchanging $a,b$ leaves the number of ones unchanged, and the control is unchanged, so total Hamming weight is conserved on every row.

5. Same truth table, different coherent gate

Explain why $I$ and $Z$ have the same computational-basis label truth table but are not the same coherent gate.

Solution

Both gates preserve the basis labels:

$$I|0\rangle=|0\rangle, \quad I|1\rangle=|1\rangle,$$

whereas

$$Z|0\rangle=|0\rangle, \quad Z|1\rangle=-|1\rangle.$$

The minus sign is invisible to a basis-label truth table but is relative on a superposition:

$$I|+\rangle=|+\rangle, \qquad Z|+\rangle=|-\rangle.$$

An $X$-basis measurement distinguishes the outputs perfectly.

6. Compute–phase–uncompute

Let $f(a,b)=a\lor b$. Starting with a uniform two-bit input and a clean work bit, apply $U_f$, then $Z$ to the work bit, then $U_f$ again. Find the final amplitudes and work state.

Solution

For each basis input,

$$|x\rangle|0\rangle \xrightarrow{U_f} |x\rangle|f(x)\rangle \xrightarrow{Z} (-1)^{f(x)}|x\rangle|f(x)\rangle \xrightarrow{U_f} (-1)^{f(x)}|x\rangle|0\rangle.$$

OR is zero only for $00$. Therefore the final state is

$$\frac12 \left( |00\rangle-|01\rangle-|10\rangle-|11\rangle \right)|0\rangle.$$

The input amplitudes have phase pattern $(1,-1,-1,-1)$ and the work bit is exactly clean.

7. Complete ten-field resource audit

A forward block on an $n$-bit input uses 12 Toffolis, depth 9, three clean scratch bits, and a four-bit clean computed-result register. A separate four-bit durable output is available. Audit the full compute–parallel-copy–uncompute construction.

Solution

1. Classical task, domain, codomain, and promise — An otherwise unspecified four-bit function of an $n$-bit input; no promise is supplied, so the audit applies to the complete $n$-bit input space.
2. Register names, order, widths, and basis encoding — Input $X$ has $n$ bits, scratch $W$ has three, computed result $R$ has four, and durable output $Z$ has four; computational-basis order is $(X,W,R,Z)$.
3. Input, output, and preservation contract — Preserve $X$, place the useful four-bit value in $Z$, and restore $W,R$ to zero.
4. Clean and dirty ancilla assumptions — All three $W$ bits, four $R$ bits, and four $Z$ bits begin at zero; no dirty ancilla is licensed.
5. Reversible embedding and explicit inverse — Apply the declared forward block, four bitwise CNOT copies $R\to Z$, and the exact inverse block.
6. Gate alphabet and phase semantics — The forward and inverse costs are stated in ideal Toffolis; copying uses four ideal phase-free CNOTs. Any lower-level synthesis is N/A here.
7. Garbage, copied data, and cleanup condition — $Z$ keeps the copied result. The three scratch and four computed-result lines, seven lines total, return to zero.
8. Width, size, depth, and maximum live workspace — Maximum width is $n+3+4+4=n+11$. The full size is $12+4+12=28$ gates: 24 Toffolis and four CNOTs. Parallel copying gives depth $9+1+9=19$. Peak temporary occupancy is seven lines, final temporary occupancy zero.
9. Exactness, error metric, and verification evidence — The prompt declares exact forward and inverse blocks; a completed implementation must still test the full permutation, inverse, and relative phases. No approximate metric is supplied, so approximation error is N/A.
10. Licensed conclusion and canonical handoff — The abstract cleanup ledger is size 28, depth 19, and width $n+11$. Compilation, routing, fault tolerance, and hardware cost require downstream analysis.

8. Thermodynamic boundary

Using the exact Boltzmann constant, evaluate $k_BT\ln2$ at $T=300\ \mathrm K$ and the corresponding value for $10^9$ ideal unbiased erasures. Explain what the calculation does not establish.

Solution

With

$$k_B=1.380649\times10^{-23}\ \mathrm{J\,K^{-1}},$$

one obtains

$$k_BT\ln2 = (1.380649\times10^{-23})(300)\ln2 = 2.87098\times10^{-21}\ \mathrm J.$$

For $10^9$ ideal erasures,

$$10^9k_BT\ln2 = 2.87098\times10^{-12}\ \mathrm J.$$

This is the familiar lower bound for resetting one initially equiprobable, uncorrelated bit to one fixed logical state in an isothermal cycle with a bath at $300\ \mathrm K$, in the ideal quasistatic limit that exports the entropy decrease $k_B\ln2$. It assumes no usable side information or correlations that change the conditional entropy. It is not an engineering dissipation estimate, an energy per Toffoli, or a charge attached to every logically reversible gate. Biased memories, correlations, finite baths, error constraints, and nonideal cycles require a more complete thermodynamic record.

References

• A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary gates for quantum computation,” Physical Review A 52, 3457–3467 (1995), doi:10.1103/PhysRevA.52.3457.
• C. H. Bennett, “Logical reversibility of computation,” IBM Journal of Research and Development 17(6), 525–532 (1973), doi:10.1147/rd.176.0525.
• C. H. Bennett, “The thermodynamics of computation—a review,” International Journal of Theoretical Physics 21, 905–940 (1982), doi:10.1007/BF02084158.
• C. H. Bennett, “Time/space trade-offs for reversible computation,” SIAM Journal on Computing 18(4), 766–776 (1989), doi:10.1137/0218053.
• R. P. Feynman, “Quantum mechanical computers,” Foundations of Physics 16(6), 507–531 (1986), doi:10.1007/BF01886518.
• E. Fredkin and T. Toffoli, “Conservative logic,” International Journal of Theoretical Physics 21(3–4), 219–253 (1982), doi:10.1007/BF01857727.
• R. Landauer, “Irreversibility and heat generation in the computing process,” IBM Journal of Research and Development 5(3), 183–191 (1961), doi:10.1147/rd.53.0183.
• M. Li and P. M. B. Vitányi, “Reversibility and adiabatic computation: trading time and space for energy,” Proceedings of the Royal Society A 452(1947), 769–789 (1996), doi:10.1098/rspa.1996.0039.
• D. Maslov, “Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization,” Physical Review A 93, 022311 (2016), doi:10.1103/PhysRevA.93.022311.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• A. Peres, “Reversible logic and quantum computers,” Physical Review A 32, 3266–3276 (1985), doi:10.1103/PhysRevA.32.3266.
• T. Toffoli, “Reversible computing,” in Automata, Languages and Programming, J. W. de Bakker and J. van Leeuwen, eds., Lecture Notes in Computer Science 85, Springer, 632–644 (1980), doi:10.1007/3-540-10003-2_104.