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.

Helpful 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\}.$$

The fiber size counts how many input labels a given output fails to distinguish. It gives a worst-case storage requirement below; it is not an average information entropy without a probability distribution on inputs. Sets, functions and maps develops the underlying definitions.

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.

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. Quantum channels and noise explains this relation between a unitary dilation and irreversible reduced dynamics.

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 gives the matrix conventions and entangling actions. Here Toffoli and Fredkin illustrate reversible logic. 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. A clean ancilla begins in a known standard state such as $|0\rangle$. A dirty ancilla may begin in an unknown state, possibly entangled with an inaccessible reference, and must be restored without disturbing those original correlations. Returning only its reduced density operator is not sufficient. For example, dephasing half of a Bell pair leaves that half in $I/2$ but destroys the pair’s coherence. The desired complete action is the data computation tensored with the identity on the borrowed register, on the intended input space.

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.

Both the peak number of work qubits and their final states matter. A line that is eventually cleaned may still determine the peak width, routing burden, or fault-tolerant qubit requirement. Circuit model defines width, size and depth.

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 explains why arbitrary unknown states cannot be copied.

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. Reset can restore a standard local state while leaving a distinguishing record in the environment; it need not restore the coherence of the useful registers. For an approximate inverse, check residual population and correlations with the work register, as well as the output error in a stated norm or channel metric.

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 explains exact and approximate synthesis for the larger unitary group.

Universality, Cost Models, and Physical Reversibility

The target class of operations determines what “universal” means. 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 treats synthesis into a chosen gate alphabet and connectivity; resource estimation tools extends these counts to fault-tolerant implementations.

A reversible predicate may count as one oracle query while containing substantial arithmetic, data access and cleanup. Phase kickback uses such predicates to change amplitudes’ relative phases; algorithmic primitives explains how that access is combined with interference and readout.

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 relates entropy-reducing erasure to heat and work under specified bath and cycle assumptions. 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 example: AND through a Toffoli embedding

To evaluate $f(a,b)=ab$, prepare the target in $|0\rangle$ and apply one ideal phase-free Toffoli. The register order is $|abt\rangle$. The output retains $a,b$ and puts $ab$ in $t$; this uses three wires, one abstract gate, and no further workspace.

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,$$

which establishes reversibility on the entire three-bit basis. 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. The one-Toffoli count describes the abstract operation; its decomposition into available physical gates is a separate calculation.

Worked example: coherent parity with and without cleanup

Compute $p=x_1\oplus x_0$ using register order $(x_1,x_0,w,z)$. The line $w$ is temporary workspace and $z$ holds the answer. Both begin in $|0\rangle$. Two CNOTs compute parity into $w$, a third transfers that basis label to $z$, and the last two reverse the computation into $w$.

Read left to right. Each filled dot controls an $X$ gate at the circled cross. The first two gates compute $p=x_1\oplus x_0$ into $w$; the middle gate transfers that basis label to $z$; the final two restore $w$ to zero. The same circuit acts coherently on superpositions of the input labels.

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 complete circuit is reversible, since each of its five gates is reversible.

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$. Thus returning the original work bit is not enough: the output also has to be independent of that unknown bit. This five-gate circuit 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, squared fidelity and trace-distance values for the retained joint system $Xz$ are $1$, $1$ and $0$. The useful output $z$ still records parity. If it too is discarded, the input $X$ loses coherence between even and odd sectors. Cleaning temporary workspace preserves the intended joint computation; it does not erase the correlations with the useful answer.

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 and Hamming weight

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. Count the complete computation

A reversible block preserves an $n$-bit input and computes a four-bit result using 12 Toffolis at depth 9, three clean scratch bits, and four clean result bits. A separate four-bit output register is available. Find the width, gate counts, depth and final workspace state for compute–parallel-copy–uncompute. Assume all four copying CNOTs can be run simultaneously and the inverse has the same cost as the forward block.

Solution

The input, scratch, result and copied output use $n+3+4+4=n+11$ wires. Computation and its inverse use 24 Toffolis; copying adds four CNOTs. Thus the total abstract count is 28 gates, and the depth is $9+1+9=19$. The three scratch and four original result bits all return to zero. The separate output keeps the function value and can remain entangled with the input.

The depth assumes disjoint copying pairs and sufficient connectivity. A device needing routing or a decomposition of Toffoli has different counts. This calculation alone says nothing about gate duration or energy dissipation.

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 the corresponding thermodynamic analysis.

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.