Finite quantum promise-computation model

Let $\mathrm{\Pi }=(Y,N)$ be a promise problem: $Y,N\subseteq \{0,1{\}}^{\ast }$ are disjoint, and no answer is required outside $Y\cup N$ (Promise problem). For every input length $n\ge 0$, let $a(n)\in \mathbb{N}$ be the number of auxiliary qubits. The $n$ input wires are ordered with the first wire most significant: for $x=(x_0,\dots ,x_{n-1})$, $\mathrm{\mid }x⟩$ is the computational-basis vector indexed by ${\mathrm{enc}}_n(x)={\sum }_{k<n}{x}_k{2}^{n-1-k}$ (Finite registers and their ordered computational bases, Big-endian encoding of ordered bit strings). The auxiliary register has $a(n)$ wires and is initialized to $\mathrm{\mid }{0}^{a(n)}⟩$. When $n=0$ or $a(n)=0$, the corresponding zero-qubit register is the one-dimensional space $\mathbb{C}$, not the zero vector space.

For each $n$, a finite circuit $C_n$ acts on the ordered register of $n+a(n)$ wires and has the unitary denotation $U_{C_n}$ specified by Finite circuit syntax and ordered wire labels and Denotational semantics of a finite layered circuit. The circuit syntax designates an ordered tuple of distinct output-wire indices; an acceptance specification uses that same tuple $O_n$, whose indices lie in $\{0,\dots ,n+a(n)-1\}$. It consists of this tuple and a total predicate $A_n(x,z)\in \{0,1\}$ for $x\in \{0,1{\}}^n$ and $z\in \{0,1{\}}^{\mathrm{\mid }{O}_n\mathrm{\mid }}$. The tuple may be empty; then its measured output set contains only the empty word. Auxiliary wires are initialized to zero, but this definition does not require them to return to zero after the computation; that stronger clean-ancilla condition is defined in Clean and dirty ancillas.

A finite quantum promise computation is the data $(\mathrm{\Pi },(C_n{)}_{n\ge 0},a,O,A)$ with these registers and predicates. Its output is classical: measure only the named output wires in the computational basis and accept exactly when $A_n(x,z)=1$. No intermediate measurement is part of this base model. Unless a full-list uniformity condition is imposed separately, the family need not be generated uniformly. When uniformity or cost is claimed, $A$ is supplied by one fixed deterministic Turing machine with an explicit polynomial worst-case time bound in the encoded pair $(x,z)$ (Deterministic one-tape Turing machines with designated accept and reject states, Partial functions computed by a machine under fixed encodings, Worst-case time and space complexity of a machine). This is a mathematical finite-circuit model and makes no assertion about physical realization.