Exact cut comparison and safe discrepancies
On this page · Permalink · Source line 92
CLAIM C01
Theorem 14.1: Cut-comparison identity and complete coverage
Let a restored oracle be written \(\mathcal C=Q\circ P\), and put \(R=Q^{-1}\). Suppress zero ancillas in boundary arguments and define
These are vectors indexed by all registers. Then
Consequently, the coordinate discrepancies \(H_i=A_i+B_i\) satisfy
Proof
For a boundary state with target \(z\), correctness of the full circuit gives
When \(f(x)=0\), this says \(B(x)=A(x)\). When \(f(x)=1\), it says \(B(x)=P(x,1)\), and the discrepancy is \(D(x)\). Both cases are summarized by (14.1).
The prefix \(P\) is a permutation. Its images of the two distinct boundary states \((x,0)\) and \((x,1)\) are different, so \(D(x)\) is a nonzero vector.
If \(f(x)=0\), every discrepancy is zero. If \(f(x)=1\), at least one discrepancy is one. These are precisely the safety and complete-coverage assertions in (14.2).