Uniform verifier interface with a quantum witness

For an input length $n$, let $X_n={\mathcal{Q}}_n$ be the ordered classical-input register, $W_n={\mathcal{Q}}_{w(n)}$ a witness register, and $A_n={\mathcal{Q}}_{a(n)}$ a zero-initialized workspace register; $w(n),a(n)$ are polynomially bounded and zero qubits means the one-dimensional space $\mathbb{C}$. A verifier family is one full-list uniform family of finite circuits on $X_n\otimes W_n\otimes A_n$, generated in polynomial time from $1^n$. The widths $w(n)$ and $a(n)$ must also be computed from $1^n$ by one fixed polynomial-time algorithm. Equivalently, a fixed polynomial-time wrapper outputs the widths together with the full circuit description, whose circuit component is a valid full-list code; the register metadata does not alter that code or its measured wire indices. Its gate order and unitary denotation are those of Full-list uniform quantum circuit family, Finite circuit syntax and ordered wire labels, and Denotational semantics of a finite layered circuit. The first register holds the classical basis input $\mathrm{\mid }x⟩$, the witness may be any density operator $\rho$ on $W_n$, and the workspace qubits start in $\mathrm{\mid }{0}^{a(n)}⟩$. Thus this definition adds an explicit quantum witness register to the classical-input, zero-ancilla promise-computation convention of Finite quantum promise-computation model; a witness is not an initialized ancilla. The workspace need not return to zero; the exact clean-return subroutine contract of Clean and dirty ancillas is a separate requirement when invoked.

Let $O_n$ be the ordered tuple of distinct terminally measured wires. One fixed total polynomial-time algorithm evaluates the predicate ${\mathrm{Acc}}_n(x,z)$ and determines acceptance from the measured output string $z$. Let $J_x:W_n\to X_n\otimes W_n\otimes A_n$ be $J_x\psi =\mathrm{\mid }x⟩\otimes \psi \otimes \mathrm{\mid }{0}^{a(n)}⟩$, and let $P_x$ be the orthogonal projection onto all computational-basis output strings accepted by ${\mathrm{Acc}}_n(x,\cdot )$, tensored with the identity on every unmeasured wire. Define the witness acceptance effect and its probability by

$E_x:=J_x^{\ast }{U}_n^{\ast }{P}_x{U}_n{J}_x,p_V(x,\rho ):=\mathrm{Tr}(E_x\rho )\mathrm{.}$

The projection $P_x$ sums over every unmeasured output wire. The positivity of this compression and its equality with the terminal outcome law are proved separately. The matrix input, gate list, generator, output predicate, and all circuit and classical costs are charged according to Circuit-family and computation cost model; no intermediate measurement or free random source is assumed in this base interface.