13.2 The restored classical oracle
On this page · Permalink · Source line 30
A legal NOT changes one target bit. A CNOT adds a control bit to a distinct target. A Toffoli adds the product of two distinct controls to a third distinct wire. Gates have positive controls and are self-inverse. Their composition is a permutation of all register states.
A restored oracle is a circuit satisfying
for every logical input \(x\) and both initial target values \(y\in{\{0,1\}}\). The zero-workspace condition is imposed at the boundary, not at intermediate times. The circuit may disturb logical inputs, use output feedback, reuse intermediate values, and make arbitrary reversible excursions before restoring the required registers.
NOT and CNOT are free only when counting \(T\). They are charged in \(L\). This distinction is essential in the projection example. There are no measurements, quantum phases, discarded work registers, or unverified ancilla initializations in this model.