Complete-graph continuous-time search

Inputs: An integer $N\ge 2$, an integer $m\ge \lceil {\log }_{2}N\rceil$, an injective label encoding $\mathsf{e}\mathsf{n}\mathsf{c}:[N]\to \{0,1{\}}^m$, and the corresponding $m$-qubit register. Its active subspace is $S:=\mathrm{span}\{e_{\mathsf{e}\mathsf{n}\mathsf{c}(x)}:x\in [N]\}$; bit strings outside the image of $\mathsf{e}\mathsf{n}\mathsf{c}$ are unused labels. The marked label $w\in [N]$ is available through the declared oracle/access model, not as an inspected classical value.

On $S$, define the complete-graph adjacency by $A{e}_{\mathsf{e}\mathsf{n}\mathsf{c}(x)}:={\sum }_{y\in [N],y\mathrm{\ne }x}{e}_{\mathsf{e}\mathsf{n}\mathsf{c}(y)},$ and extend $A$ by zero on $S^{\perp }$. Define $P_{w}z:=⟨z,e_{\mathsf{e}\mathsf{n}\mathsf{c}(w)}⟩e_{\mathsf{e}\mathsf{n}\mathsf{c}(w)}$ on the full register and the self-adjoint generator $H:=-A\mathrm{/}N-P_w$.

The input also supplies:

• a state-preparation circuit $A_s$ whose label-register output from the specified zero input is the pure state $e_s:=N^{-1\mathrm{/}2}{\sum }_{x\in [N]}{e}_{\mathsf{e}\mathsf{n}\mathsf{c}(x)}$; if its implementation uses workspace, the model states its initialization, final state, and separate query, gate, and description-bit costs;
• the total Boolean function $f_w:\{0,1{\}}^m\to \{0,1\}$ defined by $f_w(\mathsf{e}\mathsf{n}\mathsf{c}(x))=1$ exactly when $x=w$ and $f_w(z)=0$ on every unused label, together with the full unitary XOR-oracle access and its cost from Coherent XOR function oracle; and
• a Hamiltonian-access contract that supplies either the ideal $U_H(t)$ or a unitary simulator $V_{H,t,\rho }$ with a supplied certificate $\mathrm{\parallel }{V}_{H,t,\rho }-U_H(t){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \rho$, including all query, gate, description-bit, precision, and classical-construction costs.

The function oracle does not itself supply the continuous-time operation $U_H(t)$: any conversion from its marked predicate to evolution under $P_w$, and any simulation of the adjacency term, must be separately declared and charged under Continuous-time Hamiltonian access cost model.

Procedure: Prepare $e_s$, apply the supplied ideal evolution or simulator for $t=\pi \sqrt{N}\mathrm{/}2$, and measure the register in its computational basis using Finite projective measurements. Decode a measured string in the image of $\mathsf{e}\mathsf{n}\mathsf{c}$ to its label and return it; return FAIL on an unused string. If $N=2^n$ and $\mathsf{e}\mathsf{n}\mathsf{c}$ is the standard $n$-bit encoding, the supplied preparation may be $A_s=H^{\otimes n}$ by Hadamard preparation of a uniform binary state; charge $n$ gates when $H$ is primitive and the declared synthesis costs otherwise. For arbitrary $N$, $A_s$ is a supplied, charged input. No query, gate, or runtime bound follows from the finite matrix description alone.