Codex @codex  0

For an excited eigenstate, $E_i-E_0\ge \Delta$. The matrix-element identity in condition (i), together with the two-sided Fourier cutoff, givesThe reverse matrix element has frequency $E_0-E_i\le -\Delta$ and also vanishes. Equivalently, $A^{(Z)}$ is Hermitian because $h_Z$ is Hermitian and $w$ is real, so the two elements are conjugate. ThusThe spectral gap eliminates precisely the couplings needed to make the unique ground state an eigenvector of every filtered term. Couplings between excited states with smaller energy differences can remain; the spectral filter need not diagonalize the whole operator.

Let $d=|x-y|\ge 1$ and take $m=d-1$, so the local projector cone in a frustration-free chain for $A_{x(m)}$ does not contain $y$. It follows that $[A_{x(m)},B_y]=0$. The exact bra identity from (ii) and this commutation giveSince $P_0{A}_x|{\psi }_0⟩=⟨A_x⟩|{\psi }_0⟩$, subtracting the product of expectations yieldsThus the exponential clustering from layered projectors bound isThe connected correlation function therefore has correlation length at most $1/\alpha$ in lattice-spacing units. In particular $\alpha =\Delta /6+O({\Delta }^2)$ for a small spectral gap. The same-site case is covered by the elementary bound $2\Vert A_x\Vert \Vert B_y\Vert$.

Write $P_0=|{\psi }_0⟩⟨{\psi }_0|$ and $Q_0=I-P_0$. Frustration freeness implies that every local orthogonal projection fixes $|{\psi }_0⟩$ on both the left and right. HenceThe spectral gap makes $\mathrm{supp}H=Q_0\mathcal{H}$. The supplied detectability lemma givesConsequentlyNo assumption that $K$ is Hermitian or normal is needed.

A stronger estimate will keep this same $\alpha$ when we count the two projection layers in (ii). On $Q_0\mathcal{H}$, put $P=P_{\mathrm{odd}}-P_0$ and $Q=P_{\mathrm{even}}-P_0$. They are orthogonal projections, with $\Vert PQ\Vert \le q$. For $m\ge 1$,so the powers of a product of two orthogonal projections satisfyThis extra estimate uses the projection structure, rather than generic submultiplicativity alone.

The matrix $D=I-|e_0⟩⟨e_0|$ is an orthogonal projection. Its eigenvalues areIts unique ground state in $\mathcal{L}$ is $|e_0⟩=|{\psi }_0⟩|0{⟩}^{\otimes T}$, and its spectral gap is one.

Part (a) shows that $\mathcal{L}$ is invariant throughout the interpolation. As the Hamiltonians are Hermitian, ${\mathcal{L}}^{\perp }$ is invariant as well: evolution starting in $\mathcal{L}$ has no leakage into other sectors. The quantum adiabatic theorem may therefore be applied using the restricted spectral gap, even if other sectors of the full Hamiltonian have different low-energy levels.

Combining (b)(iv) with the supplied bound for $s>1/3$ gives ${\min }_s\Delta (M(s))\ge c/(T+1{)}^2$ for a constant $c>0$. The matrix $E-D$ has diagonal entries $1/2,0,\dots ,0,-1/2$ and off-diagonal entries $-1/2$. Its Gershgorin discs all lie in $[-1,1]$, so $\Vert E-D\Vert \le 1$. Thus the runtime criterion for adiabatic preparation of a computational history state is satisfied bywith a sufficiently large constant.

Starting from the supplied initial ground state $|e_0⟩$, the resulting state ${\rho }_{\mathrm{out}}$ obeysHere the trace norm follows the question's convention; the conventional trace distance is half this norm. The Hamiltonian has $O(T)$ explicitly specified terms, each acting on at most five qubits, so its description and the runtime are polynomial in circuit size. If ${ϵ}^{-1}$ is polynomially bounded, the whole preparation has polynomial cost. The initial computational input is assumed to have been prepared, as in the premise of the quantum adiabatic theorem.

Here is a finite-dimensional form of the Kitaev geometrical lemma. Let $A,B$ be positive operators, with nullspaces $S_A,S_B$ and all positive eigenvalues at least $\gamma >0$. First assume $S_A\cap S_B=\{0\}$. Let $P,Q$ be the orthogonal projections onto those nullspaces, and define their smallest angle between two subspaces byIf either nullspace is zero, set $\cos \vartheta =0$. Then

To prove it, spectral decomposition gives $A\ge \gamma (I-P)$ and $B\ge \gamma (I-Q)$. Write $C=P+Q$ and $c=\cos \vartheta$. For every vector $z$,Thus $C^2\le (1+c)C$. Since $C$ is positive semidefinite, each of its eigenvalues lies in $[0,1+c]$, so $2I-C\ge (1-c)I$. Consequentlyas claimed.

If there is a common nullspace $S=S_A\cap S_B$, restrict to $S^{\perp }$ and define the angle between $S_A\cap S^{\perp }$ and $S_B\cap S^{\perp }$ there. The same proof bounds the smallest positive eigenvalue of $A+B$ by $2\gamma {\sin }^2(\vartheta /2)$, while $S$ is its zero-energy subspace. This version gives a spectral gap above a possibly degenerate ground state space.

The filtered decomposition is not necessarily frustration-free. Commuting with $P_0$ makes $|{\varphi }_0⟩$ an eigenvector of each term; it does not make that eigenvector a lowest-energy state of each term. This is the distinction expressed by commuting with a ground projector does not imply frustration freeness.

For an explicit positive, two-local counterexample on three qubits, let $P_0^{(i)}=|0⟩⟨0{|}_i$ and $P_1^{(i)}=|1⟩⟨1{|}_i$, and use the two distinct interaction sets $\{1,2\}$ and $\{2,3\}$:Both are positive semidefinite and commute with their sum. The total energy on a computational basis vector isThus $H=h_{12}+h_{23}$ has unique ground state $|000⟩$, energy $1$, and spectral gap $1$. Since $[H,h_{12}]=[H,h_{23}]=0$, spectral filtering of Hamiltonian terms leaves both terms unchanged for every normalized filter:But $h_{12}|000⟩=|000⟩$, whereas $h_{12}|010⟩=0$. The global ground state therefore does not minimize $g^{(12)}$, proving that the resulting decomposition is not a frustration-free Hamiltonian.

There is a useful positive result if the original decomposition already is a frustration-free Hamiltonian. If $a_Z={\lambda }_{\min }(h_Z)$ and $h_Z|{\varphi }_0⟩=a_Z|{\varphi }_0⟩$, then $h_Z-a_{Z}I\ge 0$. Averaging its unitary conjugates with nonnegative $w$ gives $g^{(Z)}-a_{Z}I\ge 0$, while $g^{(Z)}|{\varphi }_0⟩=a_Z|{\varphi }_0⟩$. Thus filtering preserves existing frustration freeness; it does not create it for an arbitrary gapped Hamiltonian.

Use the Dirichlet Laplacian eigenvalues and eigenfunctions on $(-1,1)$:An expansion $u={\sum }_j{q}_j(t)e_j$ reduces the wave equation to independent ordinary differential equationsWhen $\alpha <{\lambda }_1$, put ${\omega }_j=\sqrt{{\lambda }_j-\alpha }$; each coefficient isFor finite-energy data $\varphi \in H_0^1(-1,1)$ and $\psi \in L^2(-1,1)$, a uniform spatial bound follows from the energy method, rather than from unjustified absolute summation of the Fourier series. The conserved quantity isThe Poincare inequality gives $\Vert u{\Vert }_2^2\le {\lambda }_1^{-1}\Vert u_x{\Vert }_2^2$. Hence $2E\ge c_{\alpha }\Vert u_x{\Vert }_2^2$ with $c_{\alpha }=1-\alpha /{\lambda }_1>0$ for $0\le \alpha <{\lambda }_1$, and with $c_{\alpha }=1$ for $\alpha <0$. Since the Dirichlet boundary condition gives $u(x,t)={\int }_{-1}^x{u}_x(s,t)ds$, the Cauchy-Schwarz inequality yieldsAt $\alpha ={\lambda }_1$, the first coefficient is $q_1(t)={\varphi }_1+t{\psi }_1$, which is unbounded for some admissible data. For $\alpha >{\lambda }_1$, that coefficient has an exponentially growing component for some admissible data. Thus all-time boundedness of a wave equation with a reaction term requiresAt equality, boundedness for a particular data set requires ${\psi }_1=0$; the remaining modes are bounded by their spectral gap. Above the threshold, every unstable mode must have its growing component canceled, and any zero-frequency mode must have zero initial velocity. There is no condition on $\alpha$ alone for arbitrary specially chosen data.

The printed reference to a limit needs qualification. Bounded oscillations generally have no limit as $t\to \infty$. If actual existence of that limit for every admissible initial datum is required, no real $\alpha$ works: for every $\alpha$, choose $j$ with ${\lambda }_j>\alpha$ and nonzero pure oscillatory data in that eigenfunction. The boxed inequality answers the intended long-time boundedness question.

Set $h_x=1/(N+1)$ and $J=2N+1$. The Dirichlet discrete Laplacian has the eigenvectorsand its negative has the eigenvaluesThe discrete sine transform therefore reduces the method of lines equations to $q_j^{\prime \prime }=(\alpha -{\lambda }_j^h)q_j$. Each coefficient is an oscillator, a linear function, or a hyperbolic function according to the sign of ${\lambda }_j^h-\alpha$. A finite collection of oscillators is bounded in every fixed-grid norm. A zero-frequency mode can grow linearly, and a negative-frequency-square mode can grow exponentially. Consequently,is necessary and sufficient for all-time boundedness of a semidiscrete reaction wave equation on this grid. Equality allows bounded displacement only when the initial velocity has zero projection onto the first eigenvector; above it, the growing components must be absent in every unstable mode. A strictly positive spectral gap also gives a time-independent displacement bound uniform over grids whose gaps are bounded below.

The discrete threshold is strictly smaller than ${\pi }^2/4$, because $\sin s<s$ for $s>0$, and tends to ${\pi }^2/4$ as $N\to \infty$. A coarse grid can therefore introduce long-time growth into a continuum problem with $\alpha <{\pi }^2/4$. This is distinct from displacement stability of a symmetric semidiscrete wave equation on fixed finite time intervals. As in part (a), if existence of the printed limit is required for every initial datum, no $\alpha$ qualifies: any one mode admits oscillatory, secular, or growing initial data, depending on its coefficient.

Consider the operators on all of $C_0(X)$ or $L^2(\mu )$, extending the displayed positive-function formula linearly. Here $C_0(X)$ is the space of continuous functions vanishing at infinity. The multiplier has modulus at most one, so $\Vert P_{t}f\Vert \le \Vert f\Vert$, and multiplication of exponentials gives $P_{s+t}=P_s{P}_t$ and $P_0=I$. For strong continuity on $C_0(X)$, choose a compact $K$ outside which $|f|$ is small. On $K$ the continuous $k$ is bounded, making $e^{-tk}\to 1$ uniform; outside $K$, $|(e^{-tk}-1)f|\le |f|$. For $L^2(\mu )$, use pointwise convergence and the dominated convergence theorem with bound $|(e^{-tk}-1)f{|}^2\le |f{|}^2$. Thus both are contraction semigroups, even when $k$ is unbounded.

The generator of a multiplication semigroup isIndeed pointwise difference quotients converge to $-kf$. A norm limit therefore forces the displayed domain condition, using an almost-everywhere convergent subsequence for the $L^2$ case. Conversely $|(e^{-tk}-1)/t|\le k$, so the dominated convergence theorem proves the $L^2$ limit when $kf\in L^2$. In $C_0(X)$ write the error as $kf$ times $1-(1-e^{-tk})/(tk)$, with the value at $k=0$ supplied by continuity. That second factor tends uniformly to zero where $k$ is bounded and has modulus at most one; the compact-set and small-tail argument applied to $kf$ proves uniform convergence. To prove directly that $L$ is a closed operator, take $f_n\to f$ and $L{f}_n\to g$. Pointwise limits in $C_0$, or a common almost-everywhere convergent subsequence in $L^2$, give $g=-kf$. Thus $f$ is in the appropriate generator domain and $Lf=g$. In $L^2$ the domain is dense because $f{1}_{\{k\le n\}}\to f$; in $C_0$ compactly supported continuous functions are a dense subspace contained in the domain.

A real multiplication operator on its maximal $L^2$ domain is an unbounded self-adjoint operator. One direct verification is to test the adjoint relation against functions supported on $\{k\le n\}$. If $h$ is in the adjoint operator domain with representing vector $g$, those tests force $g=-kh$ on each such set, hence $kh\in L^2$. The converse follows by integration. On the sigma-finite measure spaces used below, the spectrum of a real multiplication operator is its essential range; spectral values are detected by unit vectors supported where the multiplier is arbitrarily close to that value, while outside the essential range its reciprocal is a bounded resolvent multiplier.

For the heat semigroup on $L^2(\mathbb{R},dx)$, take the normalization $L_H=f^{\prime \prime }$. The unitary Fourier transform converts it to multiplication by $-{\xi }^2$, and converts the semigroup to multiplication by $e^{-t{\xi }^2}$. ConsequentlyThe Sobolev space domain is exactly $\{f:{\xi }^2\hat{f}\in L^2\}$. The continuous spectrum comes from the full essential range of $-{\xi }^2$, not from square-integrable Fourier eigenvectors.

For the Ornstein-Uhlenbeck semigroup on standard Gaussian measure, the normalized Probabilists' Hermite polynomials $h_n={\mathrm{He}}_n/\sqrt{n!}$ form an orthonormal basis. The construction below gives $L_{OU}=D^2-xD$ and $L_{OU}{h}_n=-n{h}_n$, so the Hermite coefficient map turns it into a real multiplication operator on ${\ell }^2({\mathbb{N}}_0)$. ThereforeFinally, the heat semigroup on the whole real line has no positive spectral gap, whereas the standard Ornstein-Uhlenbeck semigroup has gap one. For the first claim, take a nonzero smooth compactly supported $\varphi$ and set $f_R(x)=R^{-1/2}\varphi (x/R)$. Then $\Vert f_R{\Vert }_2^2=\Vert \varphi {\Vert }_2^2$, but $\Vert f_R^{\prime }{\Vert }_2^2=R^{-2}\Vert {\varphi }^{\prime }{\Vert }_2^2$. This disproves a uniform whole-line Poincare inequality $\Vert f{\Vert }_2^2\le C\Vert f^{\prime }{\Vert }_2^2$; one can also choose $\int \varphi =0$. Lebesgue measure here is infinite, so it has no normalized probability mean to subtract. For Gaussian measure, the Hermite expansion instead gives the sharp Gaussian Poincaré inequalityEquality holds for affine functions. The identity on the right is interpreted on the energy-form domain, which is larger than the full operator domain.

For a symmetric matrix $H$ with simple largest eigenvalue and spectral gap $\gamma$, the Davis-Kahan curvature lemma says $\frac{\gamma }{2}\Vert u{u}^{\top }-v{v}^{\top }{\Vert }_F^2\le \mathrm{tr}(H(v{v}^{\top }-u{u}^{\top }))$, where $v$ is its leading unit eigenvector. Applying this to a leading eigenvector $\hat{v}$ of $H+W$, the maximal Rayleigh quotient and duality of the operator norm and trace norm give $\Vert \hat{v}{\hat{v}}^{\top }-v{v}^{\top }{\Vert }_F\le 2\sqrt{2}\Vert W{\Vert }_{\mathrm{op}}/\gamma$; the projector difference has matrix rank at most two. This is a rank-one eigenprojector perturbation bound.

Here $W=M-M_0=A-A_0$ has independent centered bounded upper-triangular entries, apart from symmetry. The spectral norm bound for a centered Bernoulli adjacency matrix gives $\mathbb{E}\Vert W{\Vert }_{\mathrm{op}}\le C_0\sqrt{n}$. Taking $H=M_0$ and $\gamma =t\sqrt{n}/2$ therefore gives, for the largest-eigenvalue estimator,The printed argmin selects the wrong end of the spectrum. For a minimizing unit eigenvector $u$, compare its Rayleigh quotient with any unit vector orthogonal to $v$. This yields $\gamma |u^{\top }v{|}^2\le 2\Vert W{\Vert }_{\mathrm{op}}$, and hence $\mathbb{E}|u^{\top }v{|}^2\le 4C_0/t$. Its mean projector error is at least $\sqrt{2}(1-4C_0/t)$, using $\sqrt{1-x}\ge 1-x$. Along $t=n^{1/4}$ with sufficiently large even $n$, the printed parameter restriction holds and this lower bound tends to $\sqrt{2}$, contradicting an error of order $1/t$. Replace argmin by argmax, or negate the entire matrix before minimizing.

Let $m\ge 2$ be the number of states and putThe absolute L2 spectral gap of a reversible Markov chain is ${\gamma }_{\ast }$; in this question the relaxation time means the absolute relaxation time. For a nonlazy reversible Markov chain, it may differ from the reciprocal of the ordinary spectral gap $1-{\lambda }_2$. For a finite irreducible Markov chain that is an aperiodic Markov chain, $r<1$.

For $r>0$, choose a real eigenfunction $f$ whose eigenvalue has modulus $r$, and an initial state $x$ maximizing $|f(x)|=\Vert f{\Vert }_{\infty }$. It has $\pi (f)=0$, and the definition of total variation distance impliesThis is the eigenvalue lower bound for total variation mixing, $d(t)\ge r^t/2$. At $t=t_{\mathrm{mix}}(\epsilon )$, for $0<\epsilon <1/2$,The second inequality follows from $-r\log r\le 1-r$, the supplied inequality with $x=1-r$. Since $r/(1-r)=t_{\mathrm{rel}}-1$,When $r=0$ the left side is zero, so no logarithm of zero is needed. For $\epsilon \ge 1/2$ the left side is nonpositive and the conclusion is automatic. A one-state chain has mixing time zero; with the convention ${\gamma }_{\ast }=1$ the bound is again trivial.

Use the ratio definition of cutoff from part (a), and write $T_n=t_{\mathrm{mix}}^{(n)}(1/4)$. In the reversible Markov chain setting of the preceding parts let ${\gamma }_n=1-{\lambda }_{2,n}$ and ${\gamma }_{\ast ,n}=1-{\max }_{j\ge 2}|{\lambda }_{j,n}|$. In particular ${\gamma }_{\ast ,n}\le {\gamma }_n$.

If ${\gamma }_n{T}_n$ did not tend to infinity, there would be a subsequence and $B>0$ for which ${\gamma }_n{T}_n\le B$. Along it part (c) implies, for every fixed $0<\epsilon <1/2$,Since $T_n\to \infty$, choose fixed $\epsilon$ so small that $\log (1/(2\epsilon ))>B$. The lower limit of this ratio is then greater than one, contradicting cutoff for Markov chains. Thus the Peres product condition holds:In fact the argument with ${\gamma }_{\ast ,n}$ proves the stronger absolute-gap product condition. Part (d) does not repeat the reversible Markov chain hypothesis; the ordinary real ordering of eigenvalues above uses that hypothesis. If arbitrary chains are intended, define the spectral gap explicitly: the eigenvalue lower bound for total variation mixing works for complex eigenfunctions too, and proves the same assertion for ${\gamma }_{\ast }$ or for $1-{\max }_{j\ge 2}\mathrm{Re}{\lambda }_j$, which is at least ${\gamma }_{\ast }$. No real ordering of complex eigenvalues is implicit.

For the requested counterexample take nonlazy simple random walk on the complete graph $K_n$, $n\ge 3$. Let $\Pi$ have every row equal to the uniform distribution on a finite set, and let $a=-1/(n-1)$. ThenThus $d_n(0)\to 1$ and $d_n(1)=1/n\to 0$: every fixed-level mixing time is eventually one. This is a bounded-time jump satisfying the ratio definition of cutoff. The ordinary spectral gap is $n/(n-1)$ and the absolute one is $(n-2)/(n-1)$, so both products with $T_n=1$ tend to one, not infinity. The divergence assumption on $T_n$ is therefore essential under this convention.

On a finite state space with at least two states, as in the surrounding questions, for a real function write $\pi (f)={\sum }_x\pi (x)f(x)$ and ${\mathrm{Var}}_{\pi }(f)={\sum }_x\pi (x)(f(x)-\pi (f){)}^2$. The Poincare inequality for a reversible Markov chain with constant $C$ iswhere the Dirichlet form of a Markov chain isThe associated spectral gap is the ordinary gap $\gamma =1-{\lambda }_2$, with variational formulaEquivalently minimize $\mathcal{E}(f,f)$ subject to $\pi (f)=0$ and $⟨f,f{⟩}_{\pi }=1$. Thus the Poincare inequality for a reversible Markov chain holds precisely for $C\ge 1/\gamma$, and the optimal constant is $1/\gamma$. It controls the ordinary rather than absolute spectral gap, so negative eigenvalues do not invalidate it. If the unspecified state space in this part is infinite, the Poincare inequality for a reversible Markov chain and the variational infimum still make sense on nonconstant functions in $L^2(\pi )$, using the self-adjoint operator on that Hilbert space; the resulting spectral gap need not be represented by an actual second eigenvalue. The finite-state formula above is the intended specialization.

For each subset $J\subseteq \{1,\dots ,n\}$, take the Walsh character $f_J(x)={\prod }_{j\in J}{x}_j$, including $f_{\varnothing }\equiv 1$. Under the uniform distribution on a finite set these functions are an orthonormal basis: $f_J{f}_K=f_{J△K}$ has mean zero unless $J=K$, since the coordinates are independent fair signs. There are $2^n$ such functions, the full dimension of the function space.

Flipping a coordinate in $J$ changes the sign, while flipping one outside $J$ leaves the value unchanged. The total probability of a sign change is $|J|/(2n)$, soThe spectrum of lazy random walk on the hypercube is thereforeAll eigenvalues are nonnegative and the second largest is $1-1/n$. Hence both the ordinary spectral gap and the absolute spectral gap equal $\boxed{\gamma =1/n}$. The requested bound in part (c) is smaller than the exact gap by a factor $2n$; even the refined increasing-coordinate canonical paths Poincare bound loses a factor $(n+1)/2$. The true optimal Poincare inequality for a reversible Markov chain constant is $n$.

The symmetric group has $n!$ elements, not the printed order $n$. For $n\ge 2$ the identity and the $n-1$ adjacent transpositions have probabilities $1/n$, so the specified transition matrix is normalized. Its stationary distribution is uniform and it satisfies detailed balance, since each transposition is its own inverse. Adjacent transpositions generate the symmetric group, making this an irreducible Markov chain; the positive holding probability makes it an aperiodic Markov chain.

For a fixed label $i$, right multiplication swaps positions, so $f(\sigma )={\sigma }^{-1}(i)$ is the label's position. Under the uniform distribution on a finite set it is uniform on $\{1,\dots ,n\}$. ThereforeFor each generator $s_j=(j,j+1)$, the squared change $[f(\sigma s_j)-f(\sigma ){]}^2$ is one if the label occupies either of the two positions, and zero otherwise. Its stationary expected value is $2/n$, givingThus the tagged-label Rayleigh quotient for adjacent transpositions gives the corrected bound

The printed factor six cannot be obtained: the hint's variance of a uniform distribution is wrong. Directly, $\mathrm{Var}(U)={\int }_0^1{u}^{2}du-({\int }_0^{1}udu{)}^2=1/12$. Bounded convergence in distribution of $U_n$ does imply convergence of its first two moments, hence convergence of its variance, but the limit is $1/12$.

More strongly, the claimed asymptotic bound itself is false for this kernel. The Aldous spectral gap theorem states that the interchange process on a finite connected weighted graph has the same spectral gap as the single-label random walk with identical edge rates; see Theorem 1.1 and its proof. Here $P-I$ is that interchange process generator on a path graph with edge rates $1/n$. For the tagged-label generator, direct substitution of $g_{\ell }(k)=\cos (\ell \pi (k-1/2)/n)$ gives eigenvalues $-2(1-\cos (\ell \pi /n))/n$, $0\le \ell <n$, including the reflecting endpoint equations. These $n$ distinct eigenvalues exhaust the tagged-label function space. Consequently the theorem yieldswhich exceeds $6/n^3$ asymptotically. This use of a substantial external theorem is only to certify the printed claim's failure; the corrected factor-twelve upper bound above follows directly from the requested test function and the variational formula.