Finite circuit resource accounting

Fix a finite gate alphabet $G$ with maximum arity $k:=\max (\{r(g):g\in G\}\cup \{0\})$ and a circuit from Finite circuit syntax and ordered wire labels. The declared size is the number of gate occurrences, equivalently ${\sum }_{t=1}^d\mathrm{\mid }{L}_t\mathrm{\mid }$; the declared depth is the number $d$ of explicit layers, not a minimum over alternate layerings; the width is the number $n$ of all wires, including workspace wires. The operation model may also assign weighted gate costs, classical bit costs, and query costs; these are separate coordinates and are summed over the calls actually made.

A workspace wire is an ancilla. A clean-ancilla promise specifies computational-basis zero states for the ancillas and requires their exact return for every allowed data input: if $U$ is the implemented unitary, $V_D$ is the declared data unitary, and $\mathrm{\mid }{0}_A⟩$ is the specified joint zero vector, then $U(x\otimes \mathrm{\mid }{0}_A⟩)=V_{D}x\otimes \mathrm{\mid }{0}_A⟩$ for every allowed data vector $x$. A dirty-ancilla promise permits an arbitrary ancilla state independent of the data input; it may be correlated with an untouched reference. Exact dirty-ancilla restoration means the implemented unitary on data and ancillas is $V_D\otimes I_A$ on the entire joint space, where $V_D$ is the declared unitary on data. The same operator equality then holds after tensoring with the identity on any finite untouched reference. Consequently, product input between the data and the combined ancilla/reference system remains product after the operation. No uncorrelated-output claim is made for an initially data-correlated ancilla.

A controlled or inverse operation is counted only when the operation model explicitly grants that access or supplies a construction; its charge is recorded separately from an ordinary call. Inverse availability and query or gate charges are also recorded separately from controlled forward access. In particular, the matrix of $U$ alone supplies neither a controlled call nor an inverse query, in accordance with Controlled Unitary Access and Inverse Unitary Access.