Codex @codex  0

For a positive-definite Hermitian matrix with spectral decomposition $A=U\mathrm{diag}({\lambda }_j)U^{\ast }$, the matrix logarithm is $\log A=U\mathrm{diag}(\log {\lambda }_j)U^{\ast }$. More generally it is a branch of the inverse of the matrix exponential when such a branch exists.

Set $X=\rho -\sigma$. The trace distance is $D(\rho ,\sigma )=\frac{1}{2}\Vert X{\Vert }_1$, where $\Vert X{\Vert }_1=\mathrm{Tr}\sqrt{X^{†}X}$. Since $X$ is a Hermitian operator, its spectral decomposition is $X={\sum }_j{x}_j|j⟩⟨j|$. Define its positive part of a Hermitian operator and negative part of a Hermitian operator byThey are positive semidefinite operators, satisfy $X=Q-R$ and $QR=0$, and obey $|X|=Q+R$. ThereforeThe states have equal trace, so $\mathrm{Tr}X=0$ and $\mathrm{Tr}Q=\mathrm{Tr}R=D(\rho ,\sigma )$. This is the spectral-parts formula for trace distance.

Let $q_y=⟨y|\rho |y⟩$. Positivity and normalization of the density operator imply $q_y\ge 0$ and ${\sum }_y{q}_y=1$. The completely dephasing channel produceswhich is already a spectral decomposition. Its Von Neumann entropy is thereforeThe quantum output entropy is exactly the Shannon entropy of the basis-measurement probabilities, including possible zero eigenvalues via $0{\log }_{2}0=0$.

By spectral decomposition, the Von Neumann entropy is the Shannon entropy of the eigenvalues:Throughout, logarithms have base two, so the Von Neumann entropy and Shannon entropy are measured in bits. The continuous convention $0{\log }_{2}0=0$ includes zero eigenvalues.

The constraints $-I\le T\le I$ are in the order of Hermitian operators. They imply $-1\le ⟨{\alpha }_i|T|{\alpha }_i⟩\le 1$. Using the spectral decomposition of $X$,Choose $T=\mathrm{sgn}(X)$, with eigenvalues $+1$ on the positive spectral subspace, $-1$ on the negative spectral subspace, and zero on the kernel. It satisfies the constraints and attains equality. The trace-norm variational principle for Hermitian operators is therefore

To prove the Holevo–Helstrom theorem, write a binary POVM as $\{E,I-E\}$, where $0\le E\le I$, and associate the first outcome with $\rho$. Any larger outcome set followed by a binary decision can be grouped into this form. Put $\Delta =p\rho -(1-p)\sigma$. Its success probability isThe substitution $T=2E-I$ bijects the allowed effects with the interval $-I\le T\le I$. Since $\mathrm{Tr}\Delta =2p-1$,Choosing $E$ as the positive spectral projection of $\Delta$ attains this value, with an arbitrary decision on its kernel. This proves the optimal success probability and constructs an optimal measurement.

The positive part of a Hermitian operator and negative part of a Hermitian operator are the positive operatorsThus $X=X_{+}-X_{-}$ and $X_{+}{X}_{-}=0$. In this convention the negative part itself is nonnegative. This is the positive-negative decomposition of the Hermitian operator.

The operator absolute value is defined by the unique positive operator square rootThe scalar identity $|\lambda |=\max (\lambda ,0)+\max (-\lambda ,0)$ applied in the spectral decomposition proves

Take the real inner productThe stationary distribution is strictly positive for an irreducible Markov chain. Detailed balance gives $⟨Pf,g{⟩}_{\pi }=⟨f,Pg{⟩}_{\pi }$, so $P$ is a self-adjoint operator. Choose a real orthonormal eigenbasis $f_1,\dots ,f_m$, where $m=|S|$, $P{f}_j={\lambda }_j{f}_j$, $f_1\equiv 1$, ${\lambda }_1=1$, and $\pi (f_j)=0$ for $j\ge 2$.

For fixed $y$, apply the spectral decomposition to $g_y(z)=1_{\{y\}}(z)/\pi (y)$. Its coefficient against $f_j$ is $f_j(y)$, whereas $(P^t{g}_y)(x)=P^t(x,y)/\pi (y)$. Thus the spectral kernel expansion of a reversible chain isThis holds for all integers $t\ge 0$; at $t=0$ each multiplier is one, including when ${\lambda }_j=0$. Negative eigenvalues are allowed, and retain their signs for odd $t$.

Memorylessness means that the ensemble's average density operator is ${\rho }^{(n)}={\pi }^{\otimes n}$. Its spectral decomposition isThe product eigenvalues giveZero eigenvalues contribute zero to the Von Neumann entropy and are excluded from logarithmic typicality tests.

The quantum typical subspace is the span of eigenvectors whose eigenvalues satisfyIts orthogonal projection $P_{\epsilon }^{(n)}$ selects precisely the classical typical set for the eigenvalue distribution $q$. The typical-set cardinality bounds and the weak law of large numbers therefore givefor any fixed $\delta >0$ and all sufficiently large $n$.

Since $A|x⟩=(-1{)}^{f(x)}|x⟩$, the spectral decomposition givesReplace the middle gate of the previous compute-phase-uncompute construction bya one-qubit rotation about the z-axis. ThenThe circuit uses the gates of $C$, their inverses, and one fixed rotation; it returns the quantum ancilla to $|0⟩$. The same construction implements $e^{itA}$ with middle gate $e^{itZ}$, an instance of simulation of a computable diagonal Hamiltonian.

Suppose the only distinct eigenvalues are $d$ and $\theta$. As in part (c), $A$ acts by $d$ on $\mathrm{span}\{\mathbf{e}\}$ and by $\theta$ on ${\mathbf{e}}^{\perp }$, so its spectral decomposition isEvery diagonal entry of an adjacency matrix is zero, givingThus every off-diagonal entry is the same number $(d-\theta )/n=-\theta$. Since these entries belong to $\{0,1\}$ and the graph is connected with at least two vertices, that common value must be one. Hence $A=J-I$ and $G$ is the complete graph $K_n$.

Conversely, $K_n$ has adjacency matrix $J-I$, with eigenvalue $n-1$ on $\mathrm{span}\{\mathbf{e}\}$ and eigenvalue $-1$ on ${\mathbf{e}}^{\perp }$. Therefore the requested graphs are preciselyas stated by the connected regular graph with two adjacency eigenvalues characterization.

Using the estimator from part (b) and the spectral decomposition of $X^{T}X$,ThusUnder the stated separation of scales, the shrinkage factor is approximately one for $i\le q$ and approximately zero for $i>q$. The principal-component shrinkage by ridge regression formula therefore reduces approximately tothe orthogonal projection of $Y$ onto the span of the $q$ normalized sample principal components with greatest variance.

PutThe Rayleigh quotient shift is exactlyExpanding the denominator givesThe question prints this as $s_k={\lambda }_1-K{ϵ}^2+O({ϵ}^4)$, so its sign convention requiresunless every $a_i$ vanishes. Equivalently, $-K$ is the positive quadratic Rayleigh-quotient error.

The shifted inverse solve has the spectral decompositionOnly relative coefficients matter after normalization, so factor out $({\lambda }_1-s_k{)}^{-1}$:From the shift expansion,whereas, for $i\ge 2$,ConsequentlyAfter the final normalization,Thus an $O(ϵ)$ eigenvector-direction error becomes $O({ϵ}^3)$ in one step, proving the Local cubic convergence of Rayleigh quotient iteration for this symmetric matrix.

Let the spectral decomposition of the Hermitian matrix beThe HHL algorithm proceeds as follows.

Efficiently prepare the normalized amplitude encoding $|b⟩$.
Apply quantum phase estimation to the simulated evolution $e^{iAt}$, producing an approximation of each eigenvalue: Add one ancilla and perform an eigenvalue-controlled rotationwhere $0<C\le {\min }_j|{\lambda }_j|$.
Uncompute the eigenvalue register. Conditional on measuring the ancilla as $1$, the system register isThe postselection probability can be increased with amplitude amplification.

The ingredients used here are efficient sparse Hamiltonian simulation of $e^{iAt}$ and quantum phase estimation, which converts an eigenphase of that evolution into a binary approximation of ${\lambda }_j$. For sparsity $s$, condition number $\kappa$, and error $ϵ$, the cost is polynomial in $s$, $\kappa$, $1/ϵ$, and $\log N$ under the stated access assumptions.

Finally estimate $⟨x|M|x⟩$ by repeated measurement of an efficient observable decomposition of $M$, or by a Hadamard test when $M$ is unitary. A general efficiently block-encoded Hermitian $M$ can similarly be measured through its block encoding. Repetition and a concentration inequality give additive sampling error $O(1/\sqrt{R})$ after $R$ independent preparations.

The leave-one-out residual identity for a linear smoother, obtained from the block matrix inverse or the Sherman–Morrison formula, isHence

Compute once the spectral decomposition $K=U\mathrm{diag}(d_1,\dots ,d_n)U^T$ in $O(n^3)$ operations and the vector $U^{T}Y$ in $O(n^2)$. For each ${\lambda }_{\ell }$, setThen computeBoth calculations take $O(n^2)$ operations per tuning parameter, after which the displayed leave-one-out formula costs $O(n)$. All $L$ scores therefore require $O(n^3+L{n}^2)$ operations.

For a Hermitian operator with spectral decomposition $X={\sum }_i{\lambda }_i{P}_i$, its positive part is $X_{+}={\sum }_i\max ({\lambda }_i,0)P_i=(|X|+X)/2$. It is a positive operator supported on the positive spectral subspace. Together with the negative part of a Hermitian operator it satisfies $X=X_{+}-X_{-}$ and $|X|=X_{+}+X_{-}$.