Quantum Optimization, Semidefinite Programs, and Variational Algorithms

Conjugating the diagonal sum in [F5] entry by entry and using [F2] gives $\overline{\mathrm{tr}(AB)}=\mathrm{tr}((AB{)}^{\ast })$. For $n=0$, both sides are the empty sum $0$.

By [F1] and [F3], $(AB{)}^{\ast }=B^{\ast }{A}^{\ast }=BA$. Then [F4] gives $\mathrm{tr}(BA)=\mathrm{tr}(AB)$, so step 1.1 says $\mathrm{tr}(AB)$ equals its conjugate and is real.

Let $R=P^{1\mathrm{/}2}$ from [F2] and put $T=RQR$. Since $Q$ is nonnegative by [F1], self-adjointness of $R$ and the inner-product identity [F5] give $⟨Tx,x⟩=⟨QRx,Rx⟩\ge 0$ for every $x$. Thus every diagonal entry $⟨T{e}_j,e_j⟩$ in an orthonormal coordinate basis is nonnegative real; summing by [F4] gives $\mathrm{tr}(T)\ge 0$. This also holds in dimension zero because the trace is the empty sum.

Since $P=R^2$, [F3] applied to $U=R$ and $V=RQ$ gives $\mathrm{tr}(PQ)=\mathrm{tr}(R(RQ))=\mathrm{tr}((RQ)R)=\mathrm{tr}(RQR)=\mathrm{tr}(T)\ge 0$ by step 1.1.

If $p=1$, the direct flag outcome is good. If $0<p<1$, put $u=\sqrt{1-p}$, $v=\sqrt{p}$, $z=u+iv$, and $\xi =z^2=a+i\beta$, so $a=1-2p$ and $\beta =2\sqrt{p(1-p)}$. The orthonormal vectors $\mathrm{\mid }B⟩=(I-\mathrm{\Pi })\mathrm{\mid }\psi ⟩\mathrm{/}u$ and $\mathrm{\mid }G⟩=\mathrm{\Pi }\mathrm{\mid }\psi ⟩\mathrm{/}v$ give $\mathrm{\mid }\psi ⟩=u\mathrm{\mid }B⟩+v\mathrm{\mid }G⟩$. In this ordered basis the reflection about $\mathrm{\mid }\psi ⟩$ is $\left(\begin{array}{cc}a& \beta \\ \beta & -a\end{array}\right)$ and $I-2\mathrm{\Pi }=\mathrm{diag}(1,-1)$, so one Grover iteration has matrix $\left(\begin{array}{cc}a& -\beta \\ \beta & a\end{array}\right)$. It multiplies the complex coordinate $u+iv$ by $\xi$, hence after $j$ iterations the good amplitude is $\mathrm{Im}({\xi }^{j}z)=\mathrm{Im}(z^{2j+1})$.

If $p_{\mathrm{l}\mathrm{o}\mathrm{w}}<1\mathrm{/}2$, then $K\ge 2$ and minimality of $b=\lceil {\log }_{2}K\rceil$ gives $K\mathrm{/}{2}^b\ge 1\mathrm{/}2$. Conditional on $J<K$, the draw is uniform on $0,\dots ,K-1$. For $p\le 1\mathrm{/}2$, $(\mathrm{Im}w{)}^2=(1-\mathrm{Re}(w^2))\mathrm{/}2$ and the finite geometric sum of ${\xi }^{2j+1}$ give $\frac{1}{K}{\sum }_{j=0}^{K-1}(\mathrm{Im}(z^{2j+1}){)}^2=\frac{1}{2}-\frac{\mathrm{Im}({\xi }^{2K})}{4K\beta }\ge \frac{1}{2}-\frac{1}{4K\beta }\mathrm{.}$ Here $\beta =2\sqrt{p(1-p)}\ge \sqrt{2p}$ and $K\ge 1\mathrm{/}\sqrt{p_{\mathrm{l}\mathrm{o}\mathrm{w}}}$, so $K\beta \ge \sqrt{2}$ and the conditional mean success exceeds $1\mathrm{/}8$. Multiplication by $\mathrm{Pr}(J<K)\ge 1\mathrm{/}2$ gives randomized-branch success at least $1\mathrm{/}16$. For $p>1\mathrm{/}2$ the direct flag succeeds with probability greater than $1\mathrm{/}2$.

If $p\le 1\mathrm{/}2$, the direct-then-randomized round succeeds with probability at least $1\mathrm{/}16$ by step 2.1; if $p>1\mathrm{/}2$ or $p_{\mathrm{l}\mathrm{o}\mathrm{w}}\ge 1\mathrm{/}2$, its direct flag succeeds with probability at least $1\mathrm{/}2$. Independent fresh rounds therefore fail altogether with probability at most $(15\mathrm{/}16{)}^N\le \rho$ by the exact cap test. The comparison loop terminates because $(16\mathrm{/}15{)}^N=(1+1\mathrm{/}15{)}^N\ge 1+N\mathrm{/}15$ by the binomial theorem, so $(15\mathrm{/}16{)}^N\le 15\mathrm{/}(15+N)\to 0$. If $N>1$, minimality gives $(15\mathrm{/}16{)}^{N-1}>\rho$; applying the increasing logarithm and using $\ln ((16\mathrm{/}15{)}^{N-1})=(N-1)\ln (16\mathrm{/}15)$, with $\ln (16\mathrm{/}15)>0$, gives $N-1<\ln (1\mathrm{/}\rho )\mathrm{/}\ln (16\mathrm{/}15)$. The same asymptotic bound holds for $N=1$, so $N=O(1+\ln (1\mathrm{/}\rho ))$. Since $K=O(p_{\mathrm{l}\mathrm{o}\mathrm{w}}^{-1\mathrm{/}2})$, the stated call bound follows.

Every successful branch is passed through the supplied flag-only instrument, so its returned state is the normalized good projection of that branch's input and no score, label, or work register is measured. Step 1.1 shows that each amplified good component is a scalar multiple of $\mathrm{\mid }G⟩$; direct success has the same good ray. Thus every successful return is $\mathrm{\Pi }V\mathrm{\mid }0⟩\mathrm{/}\sqrt{p}$ up to global phase. Each round uses at most $K-1$ Grover iterations, one direct preparation, at most one amplified preparation, and $b$ random bits; multiplying by $N$ proves the stated call and random-bit bounds, with each controlled, inverse, reflection, verifier, and output cost charged.

Since $M=M^{\ast }$, $M{M}^{\ast }=M^2=M^{\ast }M$, so [F1] gives an orthonormal eigenbasis $M{e}_k={\lambda }_k{e}_k$. For each unit $e_k$, [F2] and [F3] give ${\lambda }_k=⟨M{e}_k,e_k⟩=⟨e_k,M{e}_k⟩=\overline{{\lambda }_k}$, so ${\lambda }_k$ is real; [F13] gives $\mathrm{\mid }{\lambda }_k\mathrm{\mid }=\mathrm{\parallel }M{e}_k\mathrm{\parallel }\le \mathrm{\parallel }M\mathrm{\parallel }\le 1$. Thus the eigenvalues $(1\pm {\lambda }_k)\mathrm{/}2$ of $E_{\pm }$ and those of $I-E_{\pm }$ are nonnegative, so both operators are nonnegative and each $E_{\pm }$ is an effect by [F4] and [F5]. Direct addition gives $E_{+}+E_{-}=I$, hence the pair is a two-outcome POVM by [F6].

By [F6], the outcome weights are $p_{\pm }=\mathrm{tr}(\rho E_{\pm })$; representing endomorphisms in the orthonormal basis from step 1.1, [F9] makes them nonnegative. By [F8], [F11], [F7], and $E_{+}+E_{-}=I$, their sum is $p_{+}+p_{-}=\mathrm{tr}(\rho (E_{+}+E_{-}))=\mathrm{tr}(\rho )=1$. Their signed mean is $p_{+}-p_{-}=\mathrm{tr}(\rho (E_{+}-E_{-}))=\mathrm{tr}(\rho M)=\mathrm{tr}(M\rho )$ by [F8] and [F12], and it is real by [F10]. Thus the outcome law has mean $\mathrm{tr}(M\rho )$.

Each $S_{t-1}$ is Hermitian by [F2] and hence normal, so [F1] gives an orthonormal eigenbasis $S_{t-1}{e}_k={\lambda }_k{e}_k$. For each unit $e_k$, [F3] and [F4] give ${\lambda }_k=⟨S_{t-1}{e}_k,e_k⟩=⟨e_k,S_{t-1}{e}_k⟩=\overline{{\lambda }_k}$, so ${\lambda }_k\in \mathbb{R}$. By [F5] and [F6], the eigenvalues $\exp (-\eta {\lambda }_k)$ of $W_t$ are positive; hence $W_t$ is positive definite and [F7] gives $\mathrm{tr}(W_t)={\sum }_k\exp (-\eta {\lambda }_k)>0$. Therefore ${\rho }_t$ is defined.

Scaling the positive operator $W_t$ by its positive trace gives ${\rho }_t⪰0$, and the diagonal-sum definition of trace gives $\mathrm{tr}({\rho }_t)=\mathrm{tr}(W_t)\mathrm{/}\mathrm{tr}(W_t)=1$. Thus each update is a density matrix by [F8]. Since $M_t$ and ${\rho }_t$ are Hermitian, their product has real trace by [F9], so the round cost is a well-defined real number.

If $n=0$, there is one matrix $X$, all traces are zero, and primal nonemptiness implies $b_j\ge 0$ for every $j$. The primal singleton is compact with optimum $0$, while every $y\ge 0$ is dual feasible and $b\cdot y\ge 0$, with equality at $y=0$. The vector $q_1=m+1$, $q_j=1$ for $j\ge 2$ is strictly positive and its empty matrix slack is positive definite in the quadratic-form sense, since there is no nonzero vector. Thus all conclusions hold. Henceforth assume $n\ge 1$.

Regard the Hermitian matrices $H_n$ as a real space with coordinates the $n$ real diagonal entries and the real and imaginary parts above the diagonal, giving ${\mathbb{R}}^{n^2}$. Direct diagonal summation yields $\mathrm{tr}(UV)={\sum }_i{U}_{ii}{V}_{ii}+2{\sum }_{i<j}\mathrm{Re}(U_{ij}\overline{V_{ij}})$ for Hermitian $U,V$. This is a real inner product, with norm $\mathrm{\parallel }U{\mathrm{\parallel }}_F=({\sum }_{i,j}\mathrm{\mid }{U}_{ij}{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$; all finite linear maps below are continuous in these coordinates. The cone $K=\{X\in H_n:X⪰0\}$ is convex and closed, being the intersection over $v\in {\mathbb{C}}^n$ of the closed real half-spaces $v^{\ast }Xv\ge 0$.

Direct summation gives $\mathrm{tr}(Dv{v}^{\ast })=v^{\ast }Dv$. For $X\in K$, write $X={\sum }_i{\lambda }_i{v}_i{v}_i^{\ast }$ in an orthonormal eigenbasis, with ${\lambda }_i\ge 0$. Then $\mathrm{tr}(X)={\sum }_i{\lambda }_i$ and $\mathrm{\parallel }X{\mathrm{\parallel }}_F^2=\mathrm{tr}(X^2)={\sum }_i{\lambda }_i^2$, so $\mathrm{\parallel }X{\mathrm{\parallel }}_F\le \mathrm{tr}(X)$. For $D\in K$, $\mathrm{tr}(DX)={\sum }_i{\lambda }_i{v}_i^{\ast }D{v}_i\ge 0$. Conversely, a Hermitian $D$ pairing nonnegatively with every $X\in K$ has $v^{\ast }Dv\ge 0$ by testing $X=v{v}^{\ast }$, so $D\in K$. Thus $K$ is self-dual for the real trace pairing. If $D$ is Hermitian with $\mathrm{\parallel }D\mathrm{\parallel }\le 1$, [F4] gives $\mathrm{\mid }{v}^{\ast }Dv\mathrm{\mid }\le \mathrm{\parallel }v{\mathrm{\parallel }}^2$, whence $-I⪯D⪯I$ and $\mathrm{\mid }\mathrm{tr}(DX)\mathrm{\mid }\le \mathrm{tr}(X)$ for $X\in K$.

The first constraint gives $0\le \mathrm{tr}(X)\le R$ for every primal feasible $X$. That feasible set is nonempty, closed by step 1.2 and continuity of its finitely many constraints, and bounded by $\mathrm{\parallel }X{\mathrm{\parallel }}_F\le R$. Hence [F5] and [F7] give compactness and attainment of the primal maximum. Step 2.1 with $D=C$ gives $\mathrm{\mid }\mathrm{tr}(CX)\mathrm{\mid }\le R$, so $p^{\ast }\in [-R,R]$.

Set $q_1=m+1$ and $q_j=1$ for $j\ge 2$. Step 2.1 gives $S_0:={\sum }_j{q}_j{A}_j-C⪰((m+1)-(m-1)-1)I=I$, so $q$ has strictly positive coordinates and positive definite matrix slack. For primal feasible $X$ and dual feasible $y$, self-duality gives $b\cdot y-\mathrm{tr}(CX)={\sum }_j{y}_j(b_j-\mathrm{tr}(A_{j}X))+\mathrm{tr}(({\sum }_j{y}_j{A}_j-C)X)\ge 0$. Thus $p^{\ast }\le d^{\ast }\le b\cdot q$, and the dual infimum is finite.

Put $A(X)=(\mathrm{tr}(A_{j}X){)}_j$ and $\mathrm{\Phi }(X,s,a)=(A(X)+s,\mathrm{tr}(CX)-a)$. The image $S=\mathrm{\Phi }(K\times {\mathbb{R}}_{+}^m\times {\mathbb{R}}_{+})$ is a nonempty convex cone containing $(0,0)$. To prove it closed, fix $z=(u,t)\in \bar{S}$ and the open neighborhood $V=\{(u^{\mathrm{\prime }},t^{\mathrm{\prime }}):\mathrm{\mid }{u}_j^{\mathrm{\prime }}-u_j\mathrm{\mid }<1\text{ for all }j,\mathrm{\mid }{t}^{\mathrm{\prime }}-t\mathrm{\mid }<1\}$. For every point of $S\cap V$ and every witness $(X,s,a)$, step 4.1 gives $\mathrm{tr}(X)+{\sum }_j{s}_j+a\le \mathrm{tr}(S_{0}X)+q\cdot s+a=q\cdot u^{\mathrm{\prime }}-t^{\mathrm{\prime }}\le {\sum }_j{q}_j(\mathrm{\mid }{u}_j\mathrm{\mid }+1)+\mathrm{\mid }t\mathrm{\mid }+1$. With $B={\sum }_j{q}_j(\mathrm{\mid }{u}_j\mathrm{\mid }+1)+\mathrm{\mid }t\mathrm{\mid }+2$, all these witnesses belong to the closed bounded set $E=\{(X,s,a):X\in K,\mathrm{tr}(X)\le B,0\le s_j\le B,0\le a\le B\}$ in ${\mathbb{R}}^{n^2+m+1}$. By [F5] and [F6], $\mathrm{\Phi }(E)$ is compact and closed, and $S\cap V\subseteq \mathrm{\Phi }(E)\subseteq S$. Every neighborhood $U$ of $z$ has $U\cap V$ meeting $S$, so [F8] gives $z\in \overline{S\cap V}\subseteq \mathrm{\Phi }(E)\subseteq S$. Thus $S$ is closed; no sequence of witness selections was used.

Fix $\gamma >p^{\ast }$. If $A(X)+s=b$ with $X\in K,s\ge 0$, then $X$ is primal feasible and $\mathrm{tr}(CX)-a\le p^{\ast }<\gamma$ for $a\ge 0$. Hence $(b,\gamma )\mathrm{\notin }S$. By [F9] there are $w\in {\mathbb{R}}^m$ and $\alpha ,\beta \in \mathbb{R}$ with $w\cdot u+\alpha t\le \beta <w\cdot b+\alpha \gamma$ for every $(u,t)\in S$. The points $(0,-a)\in S$ for all $a\ge 0$ force $\alpha \ge 0$. Fix one primal feasible $X_f$ and set $s_f=b-A(X_f)\ge 0$; then $(b,\mathrm{tr}(C{X}_f))\in S$. If $\alpha =0$, that point gives the contradiction $w\cdot b\le \beta <w\cdot b$. Thus $\alpha >0$, using no strictness of $X_f$ or its scalar inequalities.

The coordinate rays $(s,0)\in S$ force $w_j\le 0$. Scaling $(A(X),\mathrm{tr}(CX))\in S$ by arbitrarily large nonnegative scalars forces $\mathrm{tr}(({\sum }_j{w}_j{A}_j+\alpha C)X)\le 0$ for every $X\in K$. Self-duality therefore makes $y=-w\mathrm{/}\alpha \ge 0$ dual feasible. Since $(0,0)\in S$, separation gives $0\le \beta <w\cdot b+\alpha \gamma$, so $b\cdot y<\gamma$. Consequently every $\gamma >p^{\ast }$ exceeds some dual feasible objective. If $d^{\ast }>p^{\ast }$, taking $\gamma =(p^{\ast }+d^{\ast })\mathrm{/}2$ contradicts the definition of $d^{\ast }$. Thus $d^{\ast }\le p^{\ast }$, and weak duality gives equality. Step 3.1 supplies primal attainment and the interval. An additionally promised optimal dual witness satisfies $b\cdot y^{\ast }=d^{\ast }=p^{\ast }$ and retains its promised norm bound.

Write $p=\mathrm{Pr}(\text{score}<v)$ for an incumbent. By the good/bad decomposition in [F2], after $q$ Grover iterations the success probability is $\mathrm{\mid }\mathrm{Im}(z^{2q+1}){\mathrm{\mid }}^2$ for $z=\sqrt{1-p}+i\sqrt{p}$; the same exact two-coordinate recurrence as in that lemma applies. The flag-only good branch has the normalized good projection, whose score/label measurement is therefore distributed as the original sampler conditioned on score $<v$. Direct successes have this same conditional distribution. Thus every verified improvement has that conditional distribution, with probability zero of improvement when $p=0$. For $0<p<1$, the finite geometric sum in [F2] also gives the random-iteration average $\frac{1}{2}-\mathrm{Im}(z^{4K})\mathrm{/}(4K\beta )$, where $\beta =2\sqrt{p(1-p)}$ and $K$ is the current stage cap.

Suppose the sampler preserves a uniform input index $j\in [m]$ and has bad-estimate probability at most $\nu$ for each $j$. In analysis only, replace its per-index output by the normalized good projection. The good subspace can depend on the true value; no implementation of that projector is assumed. For each $j$, a two-dimensional rotation takes the actual unit output to its good normalization with operator distance at most $2\sqrt{\nu }$: its angle has cosine $\sqrt{1-p_{bad}}$, so $2\sin (\gamma \mathrm{/}2)\le 2\sqrt{\nu }$. The direct sum of these rotations over the preserved index gives a unitary sampler replacement with the same operator bound. Inverses and controlled versions have the same bound. For at most $Q$ sampler calls, telescoping products gives output-vector error at most $2Q\sqrt{\nu }$, and any measured event changes by at most $4Q\sqrt{\nu }$. This also covers adaptive classical branches by retaining measurement results as orthogonal history registers.

If $p=0$, no improvement is possible and the incumbent already has strict-lower mass zero. For $0<p\le 1\mathrm{/}2$, put $\beta =2\sqrt{p(1-p)}\ge \sqrt{2p}$, $t=5\mathrm{/}(2\beta )\ge 5\mathrm{/}2$, and let $J$ be the first stage with $K_J\ge t$. For every subsequent stage, step 1.1 gives conditional Grover success at least $2\mathrm{/}5$; five bounded bit attempts make the random part accepted with probability at least $31\mathrm{/}32$, so stage survival is at most $49\mathrm{/}80$. The pre-threshold charge is at most $42t$: use ${\sum }_{j\le J}(4K_j+4)\le 12(3\mathrm{/}2{)}^J+8(J+1)$, $(3\mathrm{/}2{)}^J<(3\mathrm{/}2)t$, and $J+1\le 3t$. The remaining expected charge is at most ${\sum }_{h\ge 0}(49\mathrm{/}80{)}^h(6t(3\mathrm{/}2{)}^h+8)=960t\mathrm{/}13+640\mathrm{/}31$. Together these are below $128t$, hence below $256\mathrm{/}\sqrt{p}$. If $p>1\mathrm{/}2$, the direct sample alone makes stage survival at most $1\mathrm{/}2$, and total expected charge is at most ${\sum }_{j\ge 0}{2}^{-j}(4(3\mathrm{/}2{)}^j+8)=32\le 256\mathrm{/}\sqrt{p}$. Thus every verified improvement has expected charge at most $256\mathrm{/}\sqrt{p}$.

For clarity choose dyadic rank bands $[a,2a)$, $a=2^{\mathrm{\ell }}\mathrm{/}N$, truncated at one. If an incumbent lies in such a band, the next improvement has probability at least $1\mathrm{/}2$ of having rank below $a$. Indeed, under the distribution conditioned below the incumbent, the total mass of scores whose strict lower cumulative mass is less than $a$ is at least $a$; an atom crossing that cumulative threshold is included, so discreteness cannot reduce that mass. The conditional mass is at least $a\mathrm{/}q(v)\ge 1\mathrm{/}2$. Ranks decrease, so each band is entered at most once and has at most two visits in expectation. The expected charge until rank is below $1\mathrm{/}N$ is therefore at most $1+512\sqrt{N}{\sum }_{\mathrm{\ell }\ge 0}{2}^{-\mathrm{\ell }\mathrm{/}2}<2048\sqrt{N}$. Markov's inequality at the declared finite cap $100000\lceil \sqrt{N}\rceil$ gives trial failure below $1\mathrm{/}8$. Truncation is coupled to the precharged unbounded procedure: on paths whose hitting charge is within the cap, no precharge check stops the trial before its successful incumbent.

Independent trials each succeed with probability at least $7\mathrm{/}8$. Returning their smallest score preserves success whenever one trial succeeds, so the all-failure probability is at most $8^{-R}\le \delta$ by the exact rational cap test in [F1]. If $R>1$, minimality gives $8^{-(R-1)}>\delta$; applying the increasing logarithm and using $\ln (8^{R-1})=(R-1)\ln 8$ yields $R-1<\ln (1\mathrm{/}\delta )\mathrm{/}\ln 8$, with $\ln 8>0$ since $8>1$. This also gives $R=O(1+\ln (1\mathrm{/}\delta ))$ when $R=1$. A cutoff with $q(v)<1\mathrm{/}N$ is at or below any score whose cumulative mass is at least $1\mathrm{/}N$; this proves the minimum specialization. No probability of an exact score atom is assumed beyond the stated quantile/minimum promise.

Run the quantile algorithm with $N=m$ and confidence $\delta \mathrm{/}2$ on that ideal cleaned sampler, and choose $\nu \le (\delta \mathrm{/}(16Q){)}^2$. The ideal output is good and has less than $1\mathrm{/}m$ strict-lower score mass. Thus no index can have every good output score strictly below the returned score: that one index alone would contribute probability $1\mathrm{/}m$. The hybrid bound transfers this good-output/nondomination property to the implemented sampler with failure at most $\delta$. It does not require the selected score atom to have probability $1\mathrm{/}m$, does not union-bound unmeasured branches as classical samples, and does not infer a simultaneous deterministic table of all estimates. The separate planar oracle proof handles compatible completion of its two score orders.