A finite-grid quantum subgradient from approximate values

Put $\tau =r_2$, $D_i(z)=(f(z+\tau e_i)-2f(z)+f(z-\tau e_i))\mathrm{/}{\tau }^2$, $D={\sum }_i{D}_i$, and $p_i(z)=(f(z+\tau e_i)-f(z-\tau e_i))\mathrm{/}(2\tau )$. The bound on $\delta$ gives $\tau \le r_1$. Convexity makes every $D_i\ge 0$. On the query rectangle each $D_i$ and $D$ is a finite linear combination of translates of the $L$-Lipschitz function $f$, hence is Lipschitz there; all sections are likewise Lipschitz and Riemann integrable. Uniform grid Darboux sums have gaps bounded by the Lipschitz constant times cell diameter times total volume, so [F1] applies. For $d=1$, use the one-dimensional integral directly; for $d\ge 2$, apply [F1] to the first coordinate and the remaining $d-1$ coordinates. On any coordinate line, cancellation of shifted integrals leaves two pairs of boundary strips of length $\tau$. The absolute value of each pair is at most $L{\tau }^2$, so ${\int }_{-r_1}^{r_1}(f(t+\tau )-2f(t)+f(t-\tau ))dt\le 2L{\tau }^2$. Thus $\mathbb{E}D(Z)\le dL\mathrm{/}{r}_1\le nL\mathrm{/}{r}_1$ for uniform $Z$.

Coupling $Z$ to its cell center $z$, each of the four terms in a second difference moves by at most its Lipschitz constant times $\sqrt{d}{h}_0\mathrm{/}2$. Thus $\mathrm{\mid }D(z)-D(Z)\mathrm{\mid }\le 4n^{2}L{h}_0\mathrm{/}{\tau }^2\le (\rho \mathrm{/}1000)L\mathrm{/}(2r_1)$. For the finite uniform center distribution, Markov's inequality follows by summing its nonnegative weights. Therefore $D(z)\le 2nL\mathrm{/}({\rho }_0{r}_1)$ except with probability at most ${\rho }_0\mathrm{/}2+(\rho \mathrm{/}1000){\rho }_0\mathrm{/}(4n)$.

Fix such a good center. On the symmetric points $\pm \tau e_i$, the convex function $q(u)=f(z+u)-f(z)-⟨p(z),u⟩$ has value ${\tau }^2{D}_i(z)\mathrm{/}2\le {\tau }^{2}D(z)\mathrm{/}2$. Every point of the ${\mathrm{\ell }}_1$ ball of radius $\tau$ is a convex combination of these points. Convexity gives the upper bound there; applying convexity to $u,-u$ and $q(0)=0$ gives the same lower bound. Hence $\mathrm{\mid }q(u)\mathrm{\mid }\le {\tau }^{2}D(z)\mathrm{/}2\le \delta$ on that ball. The cube $a[-1\mathrm{/}2,1\mathrm{/}2{]}^d$ lies in it. Lipschitzness gives $\mathrm{\mid }{p}_i(z)\mathrm{\mid }\le L$.

Put $\gamma =ap(z)\mathrm{/}(3B_{\ast })$; then $\mathrm{\parallel }\gamma {\mathrm{\parallel }}_{\mathrm{\infty }}\le 1\mathrm{/}3$. The ideal affine phase on the product grid produces independent one-coordinate Fourier distributions centered at $M{\gamma }_i$. For an integer output at circular distance $D$ from this center, summing the geometric progression gives probability ${\sin }^2(\pi M{\gamma }_i)\mathrm{/}(M^2{\sin }^2(\pi D\mathrm{/}M))\le 1\mathrm{/}(4D^2)$ for $0<D\le M\mathrm{/}2$. Thus the probability of circular error greater than four is at most $\frac{1}{2}{\sum }_{j\ge 4}{j}^{-2}\le 1\mathrm{/}6$, since $j^{-2}\le 1\mathrm{/}(j(j-1))$ for $j\ge 4$ and ${\sum }_{j\ge 4}1\mathrm{/}(j(j-1))=1\mathrm{/}3$ by telescoping. Because $M\ge 32$ and $\mathrm{\mid }{\gamma }_i\mathrm{\mid }\le 1\mathrm{/}3$, the signed interval endpoints are farther than four from the center; circular error at most four therefore also gives ordinary signed error at most four.

The affine error from step 3.1 plus value error is at most $2\delta$. Since $B_{\ast }=28\pi \delta M$, the phase angle perturbation is at most $1\mathrm{/}21$ at every address. The Euclidean distance of the resulting unit vectors is at most $1\mathrm{/}21$; a measurement event changes by at most that distance, as follows by resolving the two pure states in their two-dimensional span and maximizing the projection difference. The allowed implemented-phase operator error adds at most $1\mathrm{/}1000$. Each coordinate therefore has ordinary signed error at most four with probability greater than $1-1\mathrm{/}6-1\mathrm{/}21-1\mathrm{/}1000>2\mathrm{/}3$. The decoded gradient error on this event is at most $12B_{\ast }\mathrm{/}(aM)=336\pi \delta \mathrm{/}a$.

For fixed $z$, the runs are independent trials for this same coordinate, not independently sampled target functions. A median fails only if at least half the runs fail. The bound from [F2] is at most $2e^{-N\mathrm{/}18}$, because the expected bad count is at most $N\mathrm{/}3$ and the excess is at least $N\mathrm{/}6$. The chosen count and a union bound give simultaneous coordinate accuracy except with probability at most $\rho \mathrm{/}500$. Every phase run uses one value query and its inverse, giving $2N\le 36\ln (1000n\mathrm{/}\rho )+8=O(\log (n\mathrm{/}\rho ))$ calls combined.

Let $s$ be any subgradient at the good center. Applying [F5] at the two coordinate offsets yields $\mathrm{\mid }{s}_i-p_i(z)\mathrm{\mid }\le \tau D_i(z)\mathrm{/}2$, hence $\mathrm{\parallel }s-p(z){\mathrm{\parallel }}_{\mathrm{\infty }}\le nL\tau \mathrm{/}({\rho }_0{r}_1)$. Add the gradient error from step 6.1 and use ${\tau }^2=\delta r_1{\rho }_0\mathrm{/}(nL)$. This gives $\mathrm{\parallel }s-v{\mathrm{\parallel }}_{\mathrm{\infty }}\le (1+168\pi )\sqrt{\delta n^{3}L\mathrm{/}({\rho }_0{r}_1)}<{23}^2\sqrt{\delta n^{3}L\mathrm{/}({\rho }_0{r}_1)}$ by [F4].

The subgradient inequality gives $f(y)\ge f(z)+⟨s,y-z⟩$. Both $\mathrm{\mid }f(z)-f(0)\mathrm{\mid }$ and $\mathrm{\mid }⟨s,z⟩\mathrm{\mid }$ are at most $L\sqrt{n}{r}_1$. Replacing $s$ by $v$ costs at most $\mathrm{\parallel }s-v{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{\parallel }y{\mathrm{\parallel }}_1\le \sqrt{n}\mathrm{\parallel }s-v{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{\parallel }y\mathrm{\parallel }$. Step 7.1 gives exactly the displayed inequality. The total failure is at most ${\rho }_0\mathrm{/}2+(\rho \mathrm{/}1000){\rho }_0\mathrm{/}(4n)+\rho \mathrm{/}500<\rho$. The query count is that of step 6.1; choosing the finite shift costs no function query.