Full-list uniform quantum circuit family

A full-list uniform quantum circuit family is a sequence $(C_n{)}_{n\ge 0}$ together with one fixed deterministic one-tape Turing machine $G$ and constants $c\ge 1$ and $k\in \mathbb{N}$ such that, on input the unary word $1^n$, $G$ halts within $c(n+1{)}^k$ transitions and its final tape is a valid self-delimiting binary description of the entire circuit $C_n$. The machine output convention is that of Deterministic one-tape Turing machines with designated accept and reject states and Partial functions computed by a machine under fixed encodings, and running time is as in Worst-case time and space complexity of a machine.

The following fixed-order code makes the full circuit and its designated input/output wires effective. A unary natural $r\in \mathbb{N}$ is written $1^{r}0$, including the one-symbol code $0$ for $r=0$. A self-delimiting binary natural $r$ is written $1^{\mathrm{\mid }\mathrm{bin}(r)\mathrm{\mid }}0\mathrm{bin}(r)$, where $\mathrm{bin}(r)$ is its ordinary binary numeral with no leading zeros and $\mathrm{bin}(0)=0$. The header gives the input-wire count $n$ and total wire count $m$ in unary, followed by the gate count $g$ as a self-delimiting natural; validity requires $m\ge n$.

Each gate record consists of a two-bit label ($00,01,10,11$ for $H,T,T^{†},\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}$ respectively), followed by one self-delimiting wire index for $H,T,T^{†}$ and two ordered self-delimiting indices for CNOT. Every index is less than $m$; CNOT indices are distinct, with the first the control and the second the target. The list contains exactly $g$ records. After the gate list, an output-count self-delimiting natural is followed by that many ordered, pairwise distinct wire indices, each less than $m$. Parsing rejects every other label, malformed or out-of-range index, repeated output index, truncated field, or trailing bit. This defines a total decoder by returning a fixed malformed-code symbol on any invalid word; effective binary encodings and total decoders are as in Effective binary encodings and total decoders.

The gate labels and matrices are the fixed finite library $H,T,T^{†},\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}$ of Clifford+T gate library and exact matrices, with entries in $\mathbb{Q}({\zeta }_8)=\mathbb{Q}(i,\sqrt{2})$; CNOT is control-first. The remaining $m-n$ wires are auxiliary wires; their initial states are determined when a family is used in a computation model. This family convention adopts full-list generation. It makes no equivalence claim with indexed-gate uniformity and, in particular, does not assert that an indexed-gate generator can be expanded to the full list in polynomial time.

When a family is used in a promise computation, its output predicate is supplied separately by that computation model; the predicate is not an uncharged quantum gate (Finite quantum promise-computation model).