Sparse Hamiltonian no-fast-forwarding

The maximum weight satisfies $1\mathrm{/}2\le {\max }_i{w}_i\le 1$: $i(n+1-i)\le (n+1{)}^2\mathrm{/}4\le n^2$ gives the upper bound, and a central integer $i$ has $i(n+1-i)\ge n^2\mathrm{/}4$ for the lower bound. Every edge satisfies $i(n+1-i)-n=(i-1)(n-i)\ge 0$, so $w_i\ge w_1=1\mathrm{/}\sqrt{n}>\eta$. The grid spacing $2^{-b}\le 1\mathrm{/}(3\pi n)=2\eta$, hence nearest rounding gives $\mathrm{\mid }{q}_i-w_i\mathrm{\mid }\le \eta$ and $q_i>0$; the support is unchanged. It follows that each row and column of $E_x={\tilde{H}}_x-H_x$ has at most two nonzero entries, each of magnitude at most $\eta$, and $2\mathrm{/}9<{\max }_i{q}_i<2$; in particular $2{\max }_i{q}_i$ is bounded above and below by positive constants independent of $n,x$.

Order path vertices lexicographically by $(i,b_0)$. A location query's predecessor slot, when present, uses only $x_i$, and its successor slot, when present, uses only $x_{i+1}$; their order is fixed by the path index. For an arbitrary candidate pair of vertices, the value query tests the single relevant edge bit and returns the known dyadic $q_i$ or zero. Each oracle function can thus be computed reversibly using one parity-bit query into scratch, an XOR into the requested target, and a second parity-bit query to erase scratch. The same construction controls the target XOR by any query-control bit, so each controlled or uncontrolled sparse-oracle call costs at most two calls to the parity-bit oracle. The x-independent $q_i$ table is generated by integer arithmetic: binary search finds the nearest grid point by comparing squared integers with $2^{2b}i(n+1-i)\mathrm{/}{n}^2$, using $O(\log (n+1))$-bit numbers and polynomially many steps in $n$. The location and value encodings are total, including sentinels, and this x-independent arithmetic is part of the fixed inter-query circuit.

For any vector $v$, Cauchy–Schwarz in each row gives $\mathrm{\mid }(E_{x}v{)}_r{\mathrm{\mid }}^2\le ({\sum }_c\mathrm{\mid }(E_x{)}_{rc}\mathrm{\mid })({\sum }_c\mathrm{\mid }(E_x{)}_{rc}\mathrm{\mid }\mathrm{\mid }{v}_c{\mathrm{\mid }}^2)\mathrm{.}$ Summing over $r$, each row sum and each column sum of $\mathrm{\mid }{E}_x\mathrm{\mid }$ is at most $2\eta$. Hence $\mathrm{\parallel }{E}_{x}v{\mathrm{\parallel }}^2\le (2\eta )(2\eta )\mathrm{\parallel }v{\mathrm{\parallel }}^2$, proving $\mathrm{\parallel }{\tilde{H}}_x-H_x{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le 2\eta$.

For $0\le s\le t$, differentiate $G(s)=e^{-i(t-s){\tilde{H}}_x}{e}^{-is{H}_x}$. By [F3], $G^{\mathrm{\prime }}(s)=i{e}^{-i(t-s){\tilde{H}}_x}({\tilde{H}}_x-H_x)e^{-is{H}_x}\mathrm{.}$ The two outside factors are unitary, so [F4] gives $\mathrm{\parallel }{G}^{\mathrm{\prime }}(s){\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le \mathrm{\parallel }{\tilde{H}}_x-H_x{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$. Integrating from $0$ to $t$ and using step 2.1 yields $\mathrm{\parallel }{e}^{-it{\tilde{H}}_x}-e^{-it{H}_x}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le t(2\eta )=\pi n\eta =\frac{1}{6}\mathrm{.}$

Apply the assumed simulator to the initial state $\mathrm{\mid }0,0⟩$ with clean work registers. The triangle inequality, step 3.1, and [F2] show that its output vector is within $1\mathrm{/}3+1\mathrm{/}6=1\mathrm{/}2$ of $J_{\mathrm{o}\mathrm{u}\mathrm{t}}(-i{)}^n\mathrm{\mid }n,\mathrm{parity}(x)⟩$. The orthogonal projection onto outcomes whose second path bit is not $\mathrm{parity}(x)$ annihilates this target vector. Its norm on the simulator output is therefore at most $1\mathrm{/}2$, so measuring the path bit computes parity with error at most $1\mathrm{/}4$. This is a valid bounded-error parity algorithm on every $x$.

Replacing each of the algorithm's $q$ sparse-oracle calls by this reversible simulation yields a parity algorithm using at most $2q$ bit queries and error at most $1\mathrm{/}4\le 1\mathrm{/}3$. By [F7], $2q\ge n\mathrm{/}2$, hence $q\ge n\mathrm{/}4$. From step 1.1 the sparse normalization is $\mathrm{\Theta }(1)$, and $t=\pi n\mathrm{/}2$, so the lower bound is equivalently $\mathrm{\Omega }(n)=\mathrm{\Omega }(t)=\mathrm{\Omega }({\alpha }_{\mathrm{s}\mathrm{p}}t)$ on this family.