Quantum Spectral Estimation and Matrix Functions

Let $V$ be a finite-dimensional complex inner-product space, let $H:V\to V$ be Hermitian, and let $I\subseteq \mathbb{R}$ contain its spectrum. For functions $f:I\to \mathbb{C}$, a polynomial $p\in \mathbb{C}[x]$, and $\eta \ge 0$, if $\mathrm{\mid }p(\lambda )-f(\lambda )\mathrm{\mid }\le \eta$ for every $\lambda \in \sigma (H)$, then $\mathrm{\parallel }p(H)-f(H)\mathrm{\parallel }\le \eta \mathrm{.}$ In particular, a uniform bound on all of $I$ suffices. Here $f(H)$ is the finite spectral functional calculus.

Let $H$ be a Hermitian endomorphism of a finite-dimensional complex inner-product space, with distinct eigenvalues $\lambda$ and orthogonal spectral projections $P_{\lambda }$. Let $\psi$ be a unit vector representing a pure state. Its state-dependent spectral distribution is the finite measure on $\sigma (H)$ defined by ${\mu }_{\psi }(\{\lambda \})=\mathrm{\parallel }{P}_{\lambda }\psi {\mathrm{\parallel }}^2=⟨\psi \mathrm{\mid }{P}_{\lambda }\mathrm{\mid }\psi ⟩\mathrm{.}$ The support is restricted to eigenvalues with nonzero weight; degeneracies are represented by one atom per distinct eigenvalue, not one atom per chosen eigenvector. The formula is the definition; its nonnegativity, total mass one, and functional-calculus moment identity are established in QPE output law and conditional state for a spectral input ↗.

Let $H$ be Hermitian on a nonzero finite-dimensional complex inner-product space, with $\mathrm{\parallel }H\mathrm{\parallel }\le \alpha$, where $\alpha >0$, and let $f:\sigma (H)\to \mathbb{C}$. If $\beta >0$, $\beta \ge \mathrm{\parallel }f(H)\mathrm{\parallel }$, and a polynomial $p$ satisfies ${\sup }_{x\in \sigma (H\mathrm{/}\alpha )}\mid p(x)-\frac{f(\alpha x)}{\beta }\mid \le \eta ,$ then $\mathrm{\parallel }\beta p(H\mathrm{/}\alpha )-f(H)\mathrm{\parallel }\le \beta \eta$. Consequently, if a unitary has top-left block $p(H\mathrm{/}\alpha )$, it is a $\beta$-block encoding of $f(H)$ with compression error at most $\eta$ under the block-encoding convention.

An eigenvalue-estimation access instance consists of a finite-dimensional system space; a costed state-preparation circuit $A_{\psi }$ with $A_{\psi }\mathrm{\mid }0⟩=\mathrm{\mid }\psi ⟩$; a costed unitary $U$ and each controlled, inverse, or controlled-inverse version actually used; an injective known phase encoding $\lambda \mapsto \theta (\lambda )\in \mathbb{R}\mathrm{/}\mathbb{Z}$ on the promised spectrum; and a specified decoder with its branch cut and output units. Exact controlled powers $U^{2^j}$ may instead be supplied individually, with their costs. If powers are synthesized from controlled-$U$, charge the exact number of calls and all control/wiring costs; no power or control is free.

For Hamiltonian access, the instance additionally specifies a Hermitian $H$, an interval containing $\sigma (H)$, a simulation rule for each requested signed time and its operator-error/cost bound, and how errors are allocated across the circuit. In the convention of Hamiltonian simulation error and resources, a simulator for $e^{-itH}$ implements the positive-sign phase unitary $e^{iH}$ at $t=-1$, using inverse access when that is what the supplied interface permits. Every preparation, inverse, controlled call, simulation, phase-register gate, decoder arithmetic operation, measurement, and written output is included in its declared cost coordinates. Aliasing is excluded by the injectivity promise and the chosen decoder; absent that promise, the output is only an estimate of the encoded phase modulo one, not of a uniquely identified eigenvalue.

Inputs. An instance of Eigenvalue-estimation access and aliasing convention, a phase-register size $m\ge 1$ with $Q=2^m$, and an input system register already prepared in the normalized state $\psi$ declared by the access instance. The caller invokes and charges $A_{\psi }$ for that preparation; this procedure does not prepare the system again. The access instance fixes the phase encoding $\theta (\lambda )$ and decoder.

Instructions. Initialize the phase register to $\mathrm{\mid }{0}^m⟩$. Apply the coherent QPE gate list through the inverse QFT from Quantum phase estimation to this prepared system, using the supplied controlled powers for $j=0,\dots ,m-1$, or synthesize each required power from the declared controlled-$U$ interface. Perform its specified computational-basis Lüders measurement once on the phase register and record $y\in \{0,\dots ,Q-1\}$. Return $y\mathrm{/}Q$ as a circular phase sample and apply the specified decoder to return an eigenvalue estimate when the injective encoding promise holds. If $U=e^{iH}$ and $\sigma (H)\subseteq [-1,1]$, use the principal representative in $(-1\mathrm{/}2,1\mathrm{/}2]$ and output $2\pi \mathrm{unwrap}(y\mathrm{/}Q)$.

The phase register, controlled powers, gates, decoder arithmetic, measurement, and output costs follow the access record. In particular, with only a controlled-$U$ oracle, implementing the binary powers uses ${\sum }_{j=0}^{m-1}{2}^j=Q-1$ controlled-$U$ calls.

This definition asserts no error probability. The exact mixture law, accuracy, and resource guarantees are established separately by the spectral-law, additive spectral-estimation, and matrix-function error-cost theorem carriers.

Let $V$ be a finite-dimensional complex inner-product space, let $H:V\to V$ be Hermitian with distinct eigenvalues $\lambda$ and spectral projections $P_{\lambda }$, and let $\psi \in V$ be a unit vector. Run the ideal phase-estimation sampler on $\psi$, with unitary $U$ whose declared phase class on $P_{\lambda }V$ is $\theta (\lambda )\in \mathbb{R}\mathrm{/}\mathbb{Z}$. Write $\bar{\theta }(\lambda )\in [0,1)$ for its unique representative, so $Uv=e^{2\pi i\bar{\theta }(\lambda )}v$ for $v\in P_{\lambda }V$. Write $a_y(\lambda )$ for the phase-register amplitude at output $y$ when the input is in that eigenspace, so $\mathrm{\mid }{a}_y(\lambda ){\mathrm{\mid }}^2=P_{\bar{\theta }(\lambda )}(y)$ as in Phase-estimation finite outcome law. Then the output law is $\mathrm{Pr}(Y=y)={\sum }_{\lambda \in \sigma (H)}{\mu }_{\psi }(\{\lambda \})P_{\bar{\theta }(\lambda )}(y)\mathrm{.}$ For every outcome with positive probability, the normalized conditional system vector is ${\psi }_y=\frac{{\sum }_{\lambda }{a}_y(\lambda )P_{\lambda }\psi }{\sqrt{\mathrm{Pr}(Y=y)}}\mathrm{.}$ Moreover, ${\mu }_{\psi }$ is a probability distribution and, for every $g:\sigma (H)\to \mathbb{C}$, $⟨\psi \mathrm{\mid }g(H)\mathrm{\mid }\psi ⟩={\sum }_{\lambda }{\mu }_{\psi }(\{\lambda \})g(\lambda )\mathrm{.}$ The conditional system is generally a coherent sum across eigenspaces, not an exact eigenspace projection.

Inputs. An eigenvalue-estimation access instance, positive rational binary inputs $ϵ>0$ and $0<\delta <1$, and certified rational upper enclosures ${\pi }_{+}>\pi$ and $L_{+}\ge \ln (1\mathrm{/}\delta )$ as produced by the finite interval procedures in OP0 of research/quantum-algorithms-planning/operational-contracts.md.

Instructions. Choose the least dyadic $Q=2^m$, $m\ge 1$, satisfying $Qϵ\ge 6{\pi }_{+}$. Choose the least positive odd integer $r$ satisfying $r\ge 8L_{+}$. On each of $r$ fresh trials, invoke the access instance's declared state-preparation circuit on fresh standard-input registers to prepare its normalized state $\psi$, then run Quantum phase-estimation spectral sampler with phase-register size $m$. Decode every result using the same branch convention, then return the median of the $r$ real eigenvalue estimates. Do not reuse the postmeasurement system from one trial as the input to another; each trial begins with a fresh state preparation. A fixed-eigenvalue accuracy guarantee requires the eigenstate promise stated by the corresponding theorem.

The certified enclosures, doubling comparisons, state preparation, each QPE circuit, each controlled-power or controlled-$U$ call, projective readout, decoding, and median computation are charged. If only controlled-$U$ access is supplied, the ideal controlled-call count is $r(Q-1)$; exact supplied powers use their separately declared per-trial costs. No inverse call is used by this procedure. Its accuracy theorem is separate.

Inputs. A nonzero finite-dimensional Hermitian matrix $H$, a scale $\alpha >0$ with $\mathrm{\parallel }H\mathrm{\parallel }\le \alpha$, a supplied unit-normalized $(1,a,{\epsilon }_{BE})$ block encoding of $A=H\mathrm{/}\alpha$ in the sense of Finite block encoding, with designated compression $\tilde{A}$ satisfying $\mathrm{\parallel }\tilde{A}-H\mathrm{/}\alpha \mathrm{\parallel }\le {\epsilon }_{BE}$ (and ${\epsilon }_{BE}=0$ for exact access), a function $f$ on $\sigma (H)$, and a caller-supplied extension $\bar{f}:[-\alpha ,\alpha ]\to \mathbb{C}$ agreeing with $f$ on the spectrum. Let $J$ be a nonempty subset of $\{0,1,2,3\}$. For each $j\mathrm{\notin }J$, supply an exact certificate that $g_j$ is identically zero on $[-\alpha ,\alpha ]$. For each $j\in J$, supply a positive scale ${\gamma }_j$ satisfying $\mathrm{\mid }{g}_j(t)\mathrm{\mid }\le {\gamma }_j$ on that interval, a tolerance ${\tau }_j\ge 0$, a nonnegative degree bound $d_j$, and a real polynomial $p_j$ of degree at most $d_j$ and parity $d_j<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2$ (including when $p_j=0$), with $\mathrm{\mid }{p}_j(x)\mathrm{\mid }\le 1$ on $[-1,1]$ and $\mid p_j(x)-\frac{g_j(\alpha x)}{{\gamma }_j}\mid \le {\tau }_j(-1\le x\le 1)\mathrm{.}$ For each active component, also supply either a reflected-convention phase-list certificate of length $d_j+1$ for which the real part of the QSP sequence's upper-left entry equals $p_j$ (exactly or within a certified uniform error bound), or, when $p_j$ has rational or exact algebraic coefficients, a positive rational phase-synthesis tolerance ${\nu }_j$ for OP1. The certificate's finite verification procedure and cost are included in the phase-source record. Any certified phase-generation or compilation error is recorded for the component and included in its implementation-error bound ${\kappa }_j$ in Matrix-function transformation error and resource bound.

Here the four real component functions are $g_0(t)=\frac{\mathrm{\Re }\bar{f}(t)+\mathrm{\Re }\bar{f}(-t)}{2},g_1(t)=\frac{\mathrm{\Re }\bar{f}(t)-\mathrm{\Re }\bar{f}(-t)}{2},$ $g_2(t)=\frac{\mathrm{\Im }\bar{f}(t)+\mathrm{\Im }\bar{f}(-t)}{2},g_3(t)=\frac{\mathrm{\Im }\bar{f}(t)-\mathrm{\Im }\bar{f}(-t)}{2}\mathrm{.}$ Thus $g_0,g_2$ are even, $g_1,g_3$ are odd, and $\bar{f}=g_0+g_1+i{g}_2+i{g}_3$. The zero certificates and scale bounds give $\mathrm{\mid }\bar{f}(t)\mathrm{\mid }\le B:={\sum }_{j\in J}{\gamma }_j$; the construction makes no optimal-normalization claim. For an identically zero target with $\bar{f}=0$, one may take $J=\{0\}$, ${\gamma }_0=1$, $d_0=0$, ${\tau }_0=0$, and $p_0=0$; the exact list ${\mathrm{\Phi }}_0=(\pi \mathrm{/}2)$ certifies its phase source since the degree-zero QSP upper-left entry is $e^{i\pi \mathrm{/}2}=i$.

Additional input. An LCU access record that supplies or compiles the coefficient-preparation unitary $P$, its inverse, and the required SELECT from the active component circuits, with all implementation costs declared as in Block-encoding oracle and implementation cost model.

Output. The LCU circuit $W$ constructed with declared normalization $B$ and designated top-left block $W_{00}$. The error bound for $W_{00}$ is given separately by Matrix-function transformation error and resource bound. If a supplied phase certificate fails its stated verification or OP1 returns a non-success result, return that failure and no block-encoding output.

Instructions. For each $j\in J$, verify its supplied phase-list certificate's length, reflected-convention polynomial identity or uniform error bound; if no list is supplied, run Real bounded-polynomial QSP phase synthesis under OP1 on $p_j$ with degree bound $d_j$, required parity $d_j<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2$, and tolerance ${\nu }_j$. Propagate any certificate, synthesis or compilation failure without producing a block-encoding output. Apply Quantum singular-value transformation circuit to the supplied block encoding to produce the singular-value transform block for $p_j$, retaining separate ancillas and all inverse, controlled, projector-phase, compilation, and implementation-error costs. Since $p_j$ is real with known parity, the even or odd transform is selected by its parity. Any certified phase or implementation deviation from the ideal $p_j$ transform is included in ${\kappa }_j$.

Run LCU block-encoding construction on the component unitaries indexed by $J$, with unit component normalizations and coefficients $c_j{\gamma }_j$, where $c_0=c_1=1$ and $c_2=c_3=i$. Its LCU normalization is $B={\sum }_{j\in J}{\gamma }_j>0$. Return its designated top-left block as an approximation to $f(H)\mathrm{/}B$. OP1 and the matrix-function error theorem specify the phase and error obligations.

This algorithm does not claim a general efficient approximation theorem, automatic extension of $f$, or a finite bit-time phase compiler beyond the stated exact-algebraic/rational OP1 interface. Charge polynomial descriptions, root/phase generation, state preparation, SELECT, PREPARE and its inverse, all QSVT calls, gate compilation, and all output bits under the separate cost coordinates.

Let $V$ be a finite-dimensional complex inner-product space, let $H:V\to V$ be Hermitian with $\sigma (H)\subseteq [-1,1]$, let $\psi$ be a normalized eigenvector of eigenvalue $\lambda$, and let $U=e^{iH}$. Use a Hamiltonian spectral-estimation access instance whose system is $V$, whose state-preparation circuit prepares $\psi$, whose phase unitary is $U$, whose phase encoding is $\mu \mapsto \mu \mathrm{/}(2\pi )(\mathrm{m}\mathrm{o}\mathrm{d}1)$ on $\sigma (H)$, and whose decoder returns $2\pi$ times the principal representative in $(-1\mathrm{/}2,1\mathrm{/}2]$. For positive rational $0<ϵ\le 1$ and $0<\delta <1$, take certified rational upper enclosures ${\pi }_{+}>\pi$ and $L_{+}\ge \ln (1\mathrm{/}\delta )$ and run Median-amplified spectral estimate on this instance with its least dyadic $Q$ satisfying $Qϵ\ge 6{\pi }_{+}$ and least positive odd $r$ satisfying $r\ge 8L_{+}$. In particular $Qϵ\ge 6\pi$ and $r\ge 8\ln (1\mathrm{/}\delta )$. In the exact model, its median $\tilde{\lambda }$ satisfies $\mathrm{Pr}(\mathrm{\mid }\tilde{\lambda }-\lambda \mathrm{\mid }\le ϵ)\ge 1-\delta \mathrm{.}$ If each of the $r$ executed trials has total state-vector deviation at most $\xi$ from its exact trial (including preparation and all controlled simulation errors), then $\mathrm{Pr}(\mathrm{\mid }\tilde{\lambda }-\lambda \mathrm{\mid }\le ϵ)\ge 1-\delta -r\xi \mathrm{.}$ An access interface that implements controlled-$U$ by repeated calls uses $r(Q-1)$ controlled-$U$ calls, in addition to $r$ state preparations, measurements, decodings, and the certified schedule/median costs. Exact power access instead uses the sum of its declared power-query costs over the $r$ trials. The eigenvector hypothesis is essential to the fixed-eigenvalue guarantee; a counterexample in the more general injective phase-access model is included below.

Use QSVT implementation of a bounded matrix function on a nonzero finite-dimensional space, with active set $J$ and $B={\sum }_{j\in J}{\gamma }_j>0$. Let $A=H\mathrm{/}\alpha$ be the target Hermitian contraction and let $\tilde{A}$ be the contraction compressed from the supplied block encoding, with $\mathrm{\parallel }\tilde{A}-A\mathrm{\parallel }\le {\epsilon }_{BE}$. For each $j\in J$, let $d_j$ be its QSVT degree, let ${\tau }_j$ bound $\mathrm{\mid }{p}_j(x)-g_j(\alpha x)\mathrm{/}{\gamma }_j\mathrm{\mid }$ on $\sigma (A)$, and let ${\kappa }_j$ bound the operator-norm deviation of its implemented QSVT block from the ideal singular-value transform $p_j^{\mathrm{S}\mathrm{V}}(\tilde{A})$. This bound includes any polynomial error in numerical QSP phase generation, finite phase compilation, and signal-call implementation. Let ${\kappa }_{LCU}$ bound the projected-block deviation of the implemented LCU circuit from its exact LCU construction on those component unitaries. Then $B\ge \mathrm{\parallel }f(H)\mathrm{\parallel }$, so this is a valid $B$-block encoding, and its returned block $W_{00}$ satisfies $\parallel W_{00}-\frac{f(H)}{B}\parallel \le \frac{1}{B}{\sum }_{j\in J}{\gamma }_j({\tau }_j+4d_j\sqrt{{\epsilon }_{BE}}+{\kappa }_j)+{\kappa }_{LCU}\mathrm{.}$ If each phase list realizes its target $p_j$ exactly and the phase, signal-call, and LCU implementations are exact, the $\kappa$ bounds may all be taken to be zero. The scale $B$ is the supplied sum of component scales, not an asserted optimal normalization.

The component $j\in J$ uses exactly $d_j$ signal calls in its QSVT sequence, with the forward/inverse split and projector-reflection counts of QSVT signal and reflection query counts. Inside a single LCU SELECT call, the maximum selected-component branch length is ${\max }_{j\in J}{d}_j$, while the implemented oracle-occurrence count is charged by the supplied SELECT circuit and may be the sum of separately controlled component counts; PREPARE, SELECT, inverse PREPARE, control logic, phase generation, compilation, ancillas, gates, and bit-time costs are separately charged according to their supplied implementations. No complexity bound for polynomial approximation or for exact-algebraic bit growth is implied.