Finite row-preparation access model for a Szegedy walk

For a nonempty finite row-stochastic kernel $(X,P)$, a row-preparation access model supplies an explicit bijection $\eta :X\to \{0,\dots ,\mathrm{\mid }X\mathrm{\mid }-1\}$; write ${\kappa }_x$ for the image of $x$ under this bijection. Every ket $\mathrm{\mid }x⟩$ below denotes the basis vector $\mathrm{\mid }{\kappa }_x⟩$. The model supplies a finite work register $W$ with a specified clean unit vector $\mathrm{\mid }{0}_W⟩$ and a unitary $V_P$ on the ordered register product ${\mathbb{C}}^X\otimes {\mathbb{C}}^X\otimes W$ satisfying

$V_P(\mathrm{\mid }x⟩\otimes \mathrm{\mid }0⟩\otimes \mathrm{\mid }{0}_W⟩)=(\mathrm{\mid }x⟩\otimes {\sum }_y\sqrt{P_{xy}}\mathrm{\mid }y⟩)\otimes \mathrm{\mid }{0}_W⟩(x\in X)\mathrm{.}$

The state encoding and its description are part of the supplied circuit interface and are included in the circuit description or uniform generator. The model separately declares access and costs for the forward call $V_P$, inverse call $V_P^{\ast }$, controlled $V_P$, controlled $V_P^{\ast }$, a direct range-reflection call, controlled range-reflection access, the clean-state reflection $R_0$, controlled $R_0$, the swap on the first two registers, and controlled swap access. The clean-state reflection is

$R_0:=2(I_X\otimes \mathrm{\mid }0,0_W⟩⟨0,0_W\mathrm{\mid })-I,$

where the second register and work register are in their specified clean states. When range reflection is implemented from row preparation, the supplied circuit word is $V_P{R}_0{V}_P^{\ast }$; the access-cost theorem proves that on the clean-work subspace it realizes the logical reflection $2T{T}^{\ast }-I$. The swap acts as $S$ on the first two registers and as the identity on $W$.

Query calls, gate counts, circuit-description bits, uniform-generation time, and precision are separate cost coordinates. A controlled walk implemented factor by factor needs controlled access to each constituent, including the preparation calls, $R_0$, and the swap. A matrix $P$ by itself supplies none of these circuits or efficient costs. For a family of encoded chains, a uniform circuit family is an additional explicit input, not a consequence of the finite matrix definition.