Additive spectral-estimation accuracy and cost

For the prepared eigenvector of eigenvalue $\lambda \in [-1,1]$, put ${\theta }_0=\lambda \mathrm{/}(2\pi )$ and let $\bar{\theta }\in [0,1)$ be the representative of its encoded phase class. By [F9], $U\psi =e^{2\pi i\bar{\theta }}\psi$. Set $\eta =ϵ\mathrm{/}(2\pi )$; then $Q\eta =Qϵ\mathrm{/}(2\pi )\ge 3$, so $K=\lfloor Q\eta \rfloor \ge 3$. Apply [F1] to $\bar{\theta }$: except with probability at most $1\mathrm{/}(2(K-1))\le 1\mathrm{/}4$, the circular phase error is less than $\eta$. On this event, the definition of the circular distance in [F1] gives an integer $k$ with $\mathrm{\mid }y\mathrm{/}Q+k-\bar{\theta }\mathrm{\mid }<\eta$. Write $\bar{\theta }={\theta }_0+n$ for an integer $n$; then $y\mathrm{/}Q+k-n={\theta }_0+e$ for some $\mathrm{\mid }e\mathrm{\mid }<\eta \le 1\mathrm{/}(2\pi )$. Consequently $\mathrm{\mid }{\theta }_0+e\mathrm{\mid }<1\mathrm{/}\pi <1\mathrm{/}2$ by [F7], so this lift is the principal representative and the specified decoder returns an estimate with error $2\pi \mathrm{\mid }e\mathrm{\mid }<ϵ$. Thus each exact trial succeeds with probability at least $3\mathrm{/}4$.

With controlled-$U$ access, the QPE phase register uses powers $U^{2^j}$ for $j=0,\dots ,m-1$, whose repeated-call implementation uses ${\sum }_j{2}^j=Q-1$ calls per trial. There are $r$ trials; each begins with a fresh charged state preparation and has one projective readout and one decoder. Exact supplied powers replace this count by their declared per-trial costs. No uncontrolled resource coordinate is inferred.

The rational schedule search in [F2] terminates. Since $ϵ>0$ and ${\pi }_{+},L_{+}$ are finite rationals, [F8] gives an integer $N\ge 1$ with $N>6{\pi }_{+}\mathrm{/}ϵ$ and $N>8L_{+}$. The bound $2^n\ge n+1$ follows by induction: it is equality at $n=0$, and $2^{n+1}\ge 2(n+1)\ge n+2$ whenever it holds at $n$. Thus $2^Nϵ\ge (N+1)ϵ>6{\pi }_{+}$ and the dyadic doubling search stops by exponent $N$. The odd integer $2N+1$ exceeds $8L_{+}$, so the increasing odd search also stops by then. Each least schedule value is therefore found by a finite search, with rational comparisons.

Let $X_i$ be the indicator of success on trial $i$ and $S={\sum }_{i=1}^r{X}_i$. Exact independent fresh preparations make the $X_i$ independent, with $p_i=\mathrm{Pr}(X_i=1)\ge 3\mathrm{/}4$ by step 1.1. For $t=\ln 3>0$, on $S\le r\mathrm{/}2$ we have $e^{-tS}\ge e^{-tr\mathrm{/}2}$, so summing the nonnegative finite expectation over this event gives $\mathrm{Pr}(S\le r\mathrm{/}2)\le e^{tr\mathrm{/}2}\mathbb{E}(e^{-tS})=e^{tr\mathrm{/}2}{\prod }_i(1-p_i+p_i{e}^{-t})\le (\sqrt{3}\mathrm{/}2{)}^r$. Each factor decreases in $p_i$ and at $p_i=3\mathrm{/}4$ the product factor is $\sqrt{3}(1\mathrm{/}4+1\mathrm{/}4)=\sqrt{3}\mathrm{/}2$. Since $2\mathrm{/}\sqrt{3}>8\mathrm{/}7$ (both sides are positive and $4\mathrm{/}3>64\mathrm{/}49$ because $196>192$) and [F10] applies to $L$ on $[1,8\mathrm{/}7]$, there is $c\in (1,8\mathrm{/}7)$ with $\ln (8\mathrm{/}7)=L(8\mathrm{/}7)-L(1)=(1\mathrm{/}7)L^{\mathrm{\prime }}(c)=1\mathrm{/}(7c)>1\mathrm{/}8$. Thus [F5] gives $\ln (2\mathrm{/}\sqrt{3})>1\mathrm{/}8$, and [F6] implies $(\sqrt{3}\mathrm{/}2{)}^r\le e^{-r\mathrm{/}8}$. The schedule gives $r\mathrm{/}8\ge L_{+}\ge \ln (1\mathrm{/}\delta )$, so [F6] and monotonicity of the exponential yield $e^{-r\mathrm{/}8}\le e^{-\ln (1\mathrm{/}\delta )}=\delta$. An odd median is inaccurate only if at least half the trials are inaccurate, which is contained in $\{S\le r\mathrm{/}2\}$; this proves the exact claim.

For one approximate trial, write the exact and implemented normalized vectors as $v,w$ and put $d=v-w$. For each readout projector $P_y$, the identity $P_y=P_y^{\ast }=P_y^2$ gives $⟨d,P_{y}v⟩=⟨P_{y}d,P_{y}v⟩$ and $⟨w,P_{y}d⟩=⟨P_{y}w,P_{y}d⟩$. Applying [F11] termwise, then [F4] to the nonnegative real lists of projected-vector norms and using [F12], bounds each of ${\sum }_y\mathrm{\mid }⟨d,P_{y}v⟩\mathrm{\mid }$ and ${\sum }_y\mathrm{\mid }⟨w,P_{y}d⟩\mathrm{\mid }$ by $\mathrm{\parallel }d\mathrm{\parallel }\le \xi$, since $\mathrm{\parallel }v\mathrm{\parallel }=\mathrm{\parallel }w\mathrm{\parallel }=1$. Expanding $⟨v,P_{y}v⟩-⟨w,P_{y}w⟩$ as the sum of those two terms shows that the ${\mathrm{\ell }}^1$ distance of the outcome laws is at most $2\xi$, hence their total variation distance is at most $\xi$. For finite probability laws $p,q$ and an event $E$, $p(E)-q(E)=\frac{1}{2}({\sum }_{y\in E}(p_y-q_y)-{\sum }_{y\mathrm{\notin }E}(p_y-q_y))$, so $\mathrm{\mid }p(E)-q(E)\mathrm{\mid }\le \frac{1}{2}{\sum }_y\mathrm{\mid }{p}_y-q_y\mathrm{\mid }$. In a product of $r$ trial laws, inserting hybrids that replace one factor at a time and using that every unchanged factor has mass one bounds the total variation distance by the sum of the single-trial distances, at most $r\xi$. Applying the event bound to the median-success event and the exact probability from step 2.1 gives probability at least $1-\delta -r\xi$.

The eigenstate promise cannot be dropped from the generic phase-access procedure. Consider the access instance $U=\mathrm{diag}(1,-1)$ with encoded eigenvalue labels $0$ and $1\mathrm{/}2$ assigned to phases $0$ and $1\mathrm{/}2$, and input $\psi =(\mathrm{\mid }0⟩+\mathrm{\mid }1⟩)\mathrm{/}\sqrt{2}$. Choose any $0<ϵ<1\mathrm{/}4$ and a dyadic $Q$ satisfying $Qϵ\ge 6\pi$; then $Q$ is even. Both phases lie exactly on the QPE grid, so [F1] gives output $0$ or $1\mathrm{/}2$ with probability $1\mathrm{/}2$ each. Fresh repetitions are independent; pairing each length-$r$ sequence with the sequence obtained by swapping every $0$ and $1\mathrm{/}2$ shows the median is each encoded eigenvalue with probability exactly $1\mathrm{/}2$. The two $ϵ$-neighborhoods are disjoint, so neither fixed label has success probability above $1\mathrm{/}2$. This counterexample uses the generic injective phase-encoding interface [F3], and shows why this theorem states the Hamiltonian guarantee for eigenstate input only.