Coherent Computation

Suppose a search procedure must recognize three-bit strings satisfying \(f(a,b,c)=(a\land b)\oplus c\). In an ordinary program we would compute \(g=a\land b\), combine it with \(c\), and throw \(g\) away. In a quantum algorithm, throwing away is not an operation we have. Worse, when we gave Deutsch’s circuit the target \(\ket0\), we saw that a leftover bit which depends on the input can silently destroy interference. So before building anything, we state precisely what the finished subroutine is allowed to leave behind.

For an \(n\)-bit input \(x\) and an \(m\)-bit value \(f(x)\), the clean oracle contract is

\[\ket{x}\ket{y}\ket{0^w}\longmapsto\ket{x}\ket{y\oplus f(x)}\ket{0^w}\quad\text{for every }x\in\{0,1\}^n,\ y\in\{0,1\}^m.\]

The three registers have distinct roles. The input \(x\) is preserved. The output target \(y\) may start in any state, and \(f(x)\) is added into it bit by bit with XOR. The workspace, \(w\) ancilla qubits used as scratch, must start in \(\ket{0^w}\) and must be returned to \(\ket{0^w}\). The equation must hold exactly, including phase, on every basis state. Once it does, linearity fixes the action on every superposition:

\[\sum_{x,y}\alpha_{x,y}\ket{x}\ket{y}\ket{0^w}\longmapsto\sum_{x,y}\alpha_{x,y}\ket{x}\ket{y\oplus f(x)}\ket{0^w}.\]

Why keep \(x\)? Because the naive map \(\ket{x}\mapsto\ket{f(x)}\) is not reversible whenever two inputs share a value: it would send two orthogonal states to the same state. Preserving \(x\) and adding into a separate target makes the map a permutation of basis states for every \(f\). Applying it twice restores \(y\), since \(y\oplus f(x)\oplus f(x)=y\).

Why insist on returning the workspace? Because the workspace is outside the contract’s promise to the caller. A caller who uses the oracle inside an interference experiment, as Deutsch’s algorithm did, needs the branches for different \(x\) to differ only in what the contract says. Any extra input-dependent record in the workspace would be a which-path record.

How do we build a clean oracle from an ordinary description of \(f\)? Any Boolean function has a circuit of AND, OR, and NOT gates. NOT is already reversible. AND is not: three of its four inputs give output \(0\). The Toffoli gate fixes this by keeping both inputs and adding the AND into a target,

\[\mathrm{TOF}\ket{a}\ket{b}\ket{t}=\ket{a}\ket{b}\ket{t\oplus ab}.\]

With \(t=0\), the target becomes \(ab\). OR follows from De Morgan’s law, \(a\lor b=\lnot(\lnot a\land\lnot b)\), so it costs a Toffoli and some \(X\) gates. XOR into an existing bit is a CNOT. So translate the circuit gate by gate: every AND or OR gets a fresh ancilla initialized to \(0\) as its target.

The translation works, but it leaves a trail. Every intermediate gate value now sits in its own ancilla. For our predicate \(f=(a\land b)\oplus c\), a direct translation computes \(g=ab\) into one ancilla, then \(t=g\oplus c\) into another:

The final values \((a,b,c,g,t)=(a,b,c,ab,f(a,b,c))\) contain the answer, but also the intermediate value \(ab\). That extra, input-dependent data is called garbage. In a classical computer garbage is merely wasteful; it can be overwritten later. In a quantum computer garbage is a which-path record that prevents the branches it distinguishes from interfering.

A word on size. If the original circuit has \(G\) AND/OR gates, the direct translation uses \(G\) Toffolis and up to \(G\) ancillas, plus \(X\) and CNOT gates. The number of qubits can therefore grow with the running time of the classical computation, not just with its memory.

Can the reversible translation do arithmetic on a superposition of numbers? A reversible circuit applies the same gate sequence to every basis component, so a classical reversible computation becomes a quantum one by linearity. Reversible arithmetic is the case we will need most: phase estimation, period finding, and amplitude estimation all use it.

Start with incrementing a two-bit register \(\ket{b_1b_0}\), where \(b_1\) is the high bit. Apply a CNOT from \(b_0\) to \(b_1\), then an \(X\) on \(b_0\). The CNOT flips the high bit exactly when the low bit is \(1\), which is when adding one produces a carry; the \(X\) then flips the low bit. Check all four inputs:

\[00\mapsto01,\qquad01\mapsto10,\qquad10\mapsto11,\qquad11\mapsto00.\]

This is modular addition: adding one modulo four. The word modulo specifies what happens on overflow: \(3+1\) wraps to \(0\) rather than needing a third bit. That wrap-around is what makes the map a permutation, and hence reversible.

On a superposition, nothing new is needed: \((\ket{00}+i\ket{11})/\sqrt2\mapsto(\ket{01}+i\ket{00})/\sqrt2\). No measurement, no classical branching. Reversing the gate order gives the inverse, subtraction of one.

The \(n\)-bit incrementer follows the same idea. Process target bits from highest to lowest: flip bit \(j\) if all lower bits are \(1\), then finally flip bit \(0\). Descending order matters, because each controlled flip reads the lower bits before they change. Bit \(j\) needs a \(j\)-controlled \(X\), which is not an elementary gate; with one or more ancillas it decomposes into \(O(j)\) Toffolis, so the whole incrementer costs \(O(n^2)\) Toffolis this way, and more careful constructions reach \(O(n)\). More generally, reversible adders computing \(\ket{a}\ket{b}\mapsto\ket{a}\ket{a+b\bmod2^n}\) are known with \(O(n)\) Toffoli and CNOT gates and one ancilla, for example the ripple-carry adder of Cuccaro, Draper, Kutin, and Moulton (2004). Modular multiplication and exponentiation, built from repeated addition, are the dominant cost of Shor’s factoring algorithm.

Let \(C\) be the garbage-producing direct translation of our predicate: Toffoli from \(a,b\) into \(g\), CNOT from \(g\) into \(t\), CNOT from \(c\) into \(t\). Afterwards \(g=ab\) and \(t=f(a,b,c)\). Now do three things.

1. Compute: apply \(C\).
2. Copy: CNOT from \(t\) into the external target \(y\).
3. Uncompute: apply \(C^{-1}\), the gates of \(C\) in reverse order (each is its own inverse).

For a basis input \(x=(a,b,c)\), with register order \((x,g,t,y)\),

\[\ket{x,0,0,y}\xrightarrow{C}\ket{x,ab,f(x),y}\xrightarrow{\text{copy}}\ket{x,ab,f(x),y\oplus f(x)}\xrightarrow{C^{-1}}\ket{x,0,0,y\oplus f(x)}.\]

Why does the last step clear the workspace without disturbing \(y\)? Because \(C^{-1}\) does not touch \(y\), and the registers it does touch, \((x,g,t)\), are exactly as \(C\) left them: the copy only read \(t\). Undoing \(C\) on its own output returns its own input, \((x,0,0)\). The input \(x\) is what makes this possible, since it still contains everything needed to recompute and hence un-recompute the intermediate values.

What to observe

The inputs have \(f=0\) and \(f=1\). After compute and copy: \(\frac{1}{\sqrt2}(\ket{000}\ket0\ket0\ket0+\ket{110}\ket1\ket1\ket1)\). After uncomputation: \(\frac{1}{\sqrt2}(\ket{000}\ket0\ket0\ket0+\ket{110}\ket0\ket0\ket1)\). The workspace now factors out as \(\ket{00}\); only the requested output still distinguishes the branches.

This compute–copy–uncompute pattern is due to Bennett, Logical Reversibility of Computation (1973), who used it to show that any classical computation can be made reversible without accumulating garbage. Nothing in the argument depends on the input being a basis state, so by linearity it gives a clean quantum oracle. Notice what is not cleared: the output target still records \(f(x)\). Uncomputation removes everything the contract did not ask for and nothing it did.

Deutsch’s circuit used the phase oracle \(\ket{x}\mapsto(-1)^{f(x)}\ket{x}\). Can a clean evaluation supply it? It can, at no extra cost: initialize the external target in \(\ket-\). The copy step is then a CNOT into \(\ket-\), which multiplies by \((-1)^{t}\) and leaves the target in \(\ket-\). After uncomputation,

\[\sum_x\alpha_x\ket{x}\ket{0^w}\ket-\longmapsto\sum_x\alpha_x(-1)^{f(x)}\ket{x}\ket{0^w}\ket-.\]

Both the workspace and the target factor out, unchanged. On the two-input example, \((\ket{000}+\ket{110})/\sqrt2\) becomes \((\ket{000}-\ket{110})/\sqrt2\). The sign is now a relative phase between input branches, available to later interference, with nothing else distinguishing them.

There is a slightly cheaper variant. Instead of copying into a \(\ket-\) target, apply a \(Z\) gate to \(t\) directly: \(Z\ket{t}=(-1)^t\ket t\). Then uncompute. This saves the target qubit. For multi-bit outputs, a phase \(e^{i\phi(v)}\) depending on a computed value \(v\) can be applied by phase gates on the bits of \(v\); we build this when we study phase encoding.

Either way, the phase oracle costs about twice the gates of computing \(f\), since the computation runs forwards and backwards. Counting a phase query as “one query” in an algorithm’s analysis is legitimate in the oracle model; in a gate count, each such query costs a compute and an uncompute.

How much does a skipped uncomputation actually cost? We can test it with an experiment that distinguishes a clean oracle from a dirty oracle, one that leaves garbage behind. Prepare the input \((\ket{000}+\ket{110})/\sqrt2\) and run the phase-oracle construction twice: once with uncomputation, once without.

Clean. The input becomes \((\ket{000}-\ket{110})/\sqrt2\), with workspace \(\ket{00}\). Now apply a CNOT from the first input bit to the second, giving \((\ket{000}-\ket{100})/\sqrt2=\ket-\ket{00}\), and a Hadamard on the first bit. The first bit becomes \(\ket1\) with certainty.

Dirty. Without uncomputation the state is \((\ket{000}\ket{00}-\ket{110}\ket{11})/\sqrt2\). The same CNOT gives \((\ket{000}\ket{00}-\ket{100}\ket{11})/\sqrt2\). The two branches now differ in the workspace, \(\ket{00}\) versus \(\ket{11}\). The Hadamard on the first bit produces amplitudes \(\pm\frac12\) on four distinct complete configurations, and nothing cancels: the first bit is a fair coin.

Why can no later gate on the input repair this? Any operation on the input acts separately on the two workspace branches, \(\ket{00}\) and \(\ket{11}\). Those branches are orthogonal, so every outcome probability is the sum of the two branches’ probabilities, never the square of a summed amplitude. The input therefore behaves exactly like a mixture: \(\ket{000}\) with probability \(1/2\) and \(-\ket{110}\) with probability \(1/2\), as if a coin had chosen one of them. The relative sign that the algorithm worked to create is no longer accessible to any operation on the input alone. Garbage behaves exactly like an environment that has measured the branch. This is why every oracle in the rest of the course is assumed clean, and why constructing one costs uncomputation.

How many gates does compute–copy–uncompute use? Suppose a reversible circuit \(C\) uses \(G\) gates, preserves its input, and computes an \(m\)-bit answer together with garbage. Then the gate count of the clean oracle is

\[G\ (\text{compute})+m\ (\text{copy CNOTs})+G\ (\text{uncompute})=2G+m\ \text{gates},\]

using the same workspace as \(C\) plus an \(m\)-qubit target. This is a construction bound, not a lower bound; clever circuits often do better. But it is a uniform bound: whatever classical algorithm computes \(f\) in \(G\) reversible gates, a clean quantum oracle costs about \(2G\).

What counts as one gate? In fault-tolerant quantum computers, the expensive operation is usually the \(T\) gate, \(T=\mathrm{diag}(1,e^{i\pi/4})\), not the CNOT. A Toffoli is not elementary there. The standard textbook decomposition (Nielsen and Chuang, Quantum Computation and Quantum Information, Section 4.3) uses six CNOTs and seven \(T\) or \(T^\dagger\) gates, together with two Hadamards. So a resource estimate might report Toffoli count or \(T\) count separately from CNOT count and depth. Multi-controlled gates must also be decomposed: a \(k\)-controlled \(X\) needs on the order of \(k\) Toffolis with \(k-2\) clean ancillas (Barenco et al., 1995).

The lesson for reading algorithm papers is to check the unit. “\(O(n^2)\) gates” might count Toffolis, two-qubit gates, or \(T\) gates, and the conversions between them are constant factors that can be large in practice. A box in a circuit diagram labelled “\(U_f\)” or “modular exponentiation” might contain millions of elementary gates.

The direct translation keeps every intermediate value until the end, so its workspace grows with the number of gates. For a long computation that is prohibitive. Can we free intermediate values earlier, and what must we pay to do so?

Consider a computation in stages: \(u_1=F_1(x)\), \(u_2=F_2(u_1)\), \(u_3=F_3(u_2)\), and so on up to \(u_k\). To compute \(u_3\) we need \(u_2\), but once \(u_3\) exists, \(u_2\) could be uncomputed, provided \(u_1\) is still present, because uncomputing \(u_2=F_2(u_1)\) requires \(u_1\). Then, to clear \(u_1\) later, we need \(x\). Clearing a value early saves space, but if a later uncomputation needs it, we must recompute it, which costs time. This is a time–space tradeoff.

This bookkeeping is a game called pebbling. Place a pebble on stage \(i\) (compute \(u_i\)) only if stage \(i-1\) has a pebble; remove it (uncompute) under the same condition. The goal is to end with pebbles on \(x\) and \(u_k\) only. Keeping everything uses \(k\) pebbles and \(2k-1\) moves: \(k\) forward, then \(k-1\) back, since \(u_k\) stays. Can we hold fewer pebbles? Try recursion. To reach stage \(k\), pebble stage \(k/2\), use it as a new starting point to pebble \(k\), then unpebble \(k/2\) by running the first half backwards. Each of the three steps is a half-length problem. So if \(c(k)\) is the number of moves, \(c(k)=3c(k/2)\) with \(c(1)=1\), which gives \(c(k)=3^{\log_2k}=k^{\log_23}\approx k^{1.58}\). The pebbles needed grow by one per level, the one left on \(k/2\) while the second half runs, so about \(\log_2k+1\) pebbles suffice. For \(k=4\) that is \(9\) moves and \(3\) pebbles, against \(7\) moves and \(4\) pebbles.

Splitting into more than two pieces per level lowers the exponent further. Bennett proved in 1989, as a quoted result, that a computation using time \(t\) and space \(s\) can be made reversible in time \(O(t^{1+\epsilon})\) and space \(O(s\log t)\) for any fixed \(\epsilon>0\) (Bennett, Time/Space Trade-Offs for Reversible Computation). Practical quantum compilers use similar schedules, choosing when to uncompute to fit within a qubit budget. The central constraint is always the same: a value can be uncomputed only while the values it was computed from are still present, and the operations between compute and uncompute must leave those values unchanged.

Suppose a later algorithm needs to reflect about a state \(\ket\psi\). What must we have besides \(\ket\psi\) itself? Let a preparation circuit \(A\) be a unitary with \(A\ket{0^n}=\ket\psi\). If its gates are known, reversing their order and inverting each gives \(A^\dagger\), which maps \(\ket\psi\) back to \(\ket{0^n}\). A supplied copy of \(\ket\psi\) does not give us this; neither does a box that applies \(A\) but cannot be run backwards.

Why do we want \(A^\dagger\)? Because it lets us reflect about \(\ket\psi\). Let \(S_0=2\ket{0^n}\bra{0^n}-I\), which leaves \(\ket{0^n}\) unchanged and negates every orthogonal basis state. Then

\[R_\psi=A\,S_0\,A^\dagger=2\ket\psi\bra\psi-I.\]

Check on two kinds of input. On \(\ket\psi\): \(A^\dagger\) sends it to \(\ket{0^n}\), \(S_0\) leaves it, \(A\) restores \(\ket\psi\). On a state \(\ket\phi\) orthogonal to \(\ket\psi\): \(A^\dagger\ket\phi\) is orthogonal to \(\ket{0^n}\), because \(A^\dagger\) preserves inner products, so \(S_0\) negates it and \(A\) returns \(-\ket\phi\). A reflection about \(\ket\psi\) is exactly the map that fixes \(\ket\psi\) and negates everything orthogonal to it.

The zero-state reflection \(S_0\) itself is a clean phase oracle for the predicate “\(x\neq0^n\)”: it is \(-\)(phase oracle of \(x=0^n\)), which differs by a global sign. With \(X\) gates on every qubit and an \(n\)-controlled \(Z\), it costs \(O(n)\) Toffolis. Amplitude amplification will use \(R_\psi\) to raise success probabilities, at the cost of one \(A\) and one \(A^\dagger\) per reflection.

Phase estimation, which we build later, needs controlled-\(U\): apply \(U\) to a target register only on the branch where a control qubit is \(1\),

\[\mathrm{C}U=\ket0\bra0\otimes I+\ket1\bra1\otimes U.\]

Given a gate sequence \(U=G_k\cdots G_1\), we can build \(\mathrm{C}U\) by controlling each gate: \(\mathrm{C}U=\mathrm{C}G_k\cdots\mathrm{C}G_1\). This works because on the control-\(0\) branch every controlled gate does nothing, and on the control-\(1\) branch every one acts. A controlled single-qubit gate costs a few CNOTs and rotations; a controlled Toffoli is a three-controlled \(X\), and so on. So controlling a circuit multiplies its cost by a constant.

There is one subtlety. Uncontrolled, \(U\) and \(e^{i\theta}U\) are the same physical operation. Controlled, they differ: \(\mathrm{C}(e^{i\theta}U)=\mathrm{C}U\cdot(P(\theta)\otimes I)\), where \(P(\theta)=\mathrm{diag}(1,e^{i\theta})\) on the control. The global phase of \(U\) becomes a relative phase on the control. In phase estimation, that phase is exactly what is measured. So a controlled version is defined only once the global phase of \(U\) is fixed. A gate library that implements rotations “up to global phase” must be checked before its gates are controlled.

For a sealed box \(U\), no general procedure produces \(\mathrm{C}U\). This is a theorem, not a gap in our cleverness: given only black-box access to an unknown unitary, no circuit implements its controlled version, essentially because the box cannot reveal its own global phase (Araújo, Feix, Costa, and Brukner, 2014). Algorithms that need \(\mathrm{C}U\) must assume it as access, or construct \(U\) from known gates.

What does a clean oracle actually hand to its caller? Applied to a superposition it produces \(\sum_x\alpha_x\ket{x}\ket{f(x)}\). It is tempting to say this “computes all values of \(f\).” It does not, in any sense a user can collect. Measuring yields one pair \((x,f(x))\) with probability \(|\alpha_x|^2\). Collecting all \(2^n\) values by repetition would take at least \(2^n\) runs, more than a classical program that simply evaluates each.

A state of this kind is useful only if the next coherent operation extracts a property from it: a phase pattern resolved by Hadamards, a period resolved by a Fourier transform, or a marked component amplified by reflections. The subroutine’s contract should therefore say what form its output takes and what the caller is expected to do with it.

We now have a concrete method for evaluating functions coherently, the costs it incurs, and the access a subroutine can offer: forward, inverse, controlled, and the reflection built from them. When the retained effect is a sign, the computation has become a phase encoding, and that encoding is what we learn to read next.