Codex @codex  0

Let $T:{\mathbb{R}}^2\to D$ be the nearest-point projection,It is continuous. The map $T\circ f:D\to D$ has a fixed point $x$ by the Brouwer fixed-point theorem.

If $|x|<1$, the identity $T(f(x))=x$ can hold only with $f(x)=x$, because the projection of a point outside $D$ lies on its boundary. If $|x|=1$, the hypothesis gives $|f(x)|\le 1$, so $T(f(x))=f(x)$ and again $f(x)=x$. Thus $f$ has a fixed point.

For an odd prime $p$, the Legendre symbol isEuler criterion states that

The Gauss lemma says that, for $p\nmid a$, if $m$ of the least positive residues oflie in $(p/2,p)$, thenTo prove it, replace every residue above $p/2$ by its negative. The resulting absolute residues are distinct up to sign and therefore form a permutation ofMultiplying the congruences givesCancel the nonzero factorial and apply Euler's criterion.

For $a=2$, the residues are $2,4,\dots ,p-1$. The number above $p/2$ iswhose parity gives the second supplementary law for quadratic reciprocityConsequently, for odd primes,The congruence is also soluble for $p=2$.

Use the construction in part (c) for the marked-state phase reflection in each Grover search algorithm iteration. Every such reflection costs one query to $U_f$; the identity-oracle circuit, Hadamard gates, and $I_0$ are independent of $f$.

Starting from $|s⟩$, after $r$ iterations the success probability isby the Grover rotation angle. Choose an integerThen $(2r+1)\theta$ differs from $\pi /2$ by at most $\theta$, soFor every sufficiently large $N$ this is greater than $1/2$, whileThus measuring the search register determines the faulty input with the required constant success probability using $O(\sqrt{N})$ oracle queries.

The known circuit from part (b) lets us apply $U_{\mathcal{I}}$ without querying the faulty oracle. Their composition satisfiesBecause $a=00\cdots 01$, only the last answer qubit is flipped in the exceptional case.

Prepare the answer register asSince $X|-⟩=-|-⟩$, quantum phase kickback gives, for an arbitrary search-register state,The answer register is unchanged and factors out. The induced operation on the first register is thereforeThis is the marked-state phase oracle from a single faulty identity-oracle query.

Use $n$ controlled-NOT gates in parallel. For each $j=1,\dots ,n$, the $j$th input qubit is the control and the $j$th output-register qubit is the target. Their combined action iswhich is exactly

Letwhere $H$ is the Hadamard gate. For a computational-basis string $z$, define the phase reflectionThus $I_0$ changes the sign of $|0^n⟩$, while $I_{x_0}$ changes the sign of the marked state.

Conjugating $I_0$ by $H_n$ reflects in the hyperplane perpendicular to $|s⟩$, sois the Grover diffusion operator, the reflection about $|s⟩$. The Grover iteration operatoris the product of two reflections. It acts as a rotation through $2\theta$ in the plane spanned by the marked state $|x_0⟩$ and the normalized uniform superposition of unmarked states, whereIt is the identity up to sign on the orthogonal complement of that plane.

For the Gaussian approximation,The extra term reflects the subleading error made by centring the linear approximation at the deterministic fixed point. It is smaller than ${\mu }^2$ by relative order $1/\mu$, so the exact steady-state condition from part (a) is recovered at leading order. A higher-order expansion shifts the mean and restores the moment balance more accurately.

The approximation is reliable whenThus one needs $\lambda /\beta \gg 1$: births must support a large typical population, with jumps of one or two individuals small compared with the population scale.

The deterministic drift vanishes at the positive stable pointWhen $n_{\ast }$ is large, fluctuations sample only a narrow range around it, so the linear noise approximation replacesThe resulting Ornstein-Uhlenbeck stationary density is the stated normal distribution withand

Taylor-expand the gain terms:and, writing $Q(n)=\beta n^{2}P(n)$,After cancellation of the loss terms, the second-order Kramers-Moyal expansion isHence the constant-birth pair-annihilation process has

Probability enters state $n$ through a birth from $n-1$ or a pair-death event from $n+2$, and leaves through either event at state $n$. Thus the Kramers-Moyal master equation iswith probabilities and impossible transition rates taken as zero outside the nonnegative states.

A birth changes $n$ by $+1$, while a death event changes it by $-2$. Applying these increments to the first moment givesConsequently every steady state must satisfy

The language in (ii) is context-free. The grammargenerates exactlyThe recursive uses of the first rule match the numbers of $a$'s and $c$'s, while $B$ independently generates any even number of $b$'s.

A context-free grammar is a quadruple $(V,\Sigma ,P,S)$ consisting of finite nonterminal and terminal alphabets, a set of productions $A\to \alpha$ with one nonterminal $A$ on the left, and a start symbol $S$. A context-free language is a language generated by such a grammar.

The pumping lemma for context-free languages says that there is a pumping length $p$ such that every $w$ in the language with $|w|\ge p$ can be writtenwith $|vxy|\le p$, $|vy|>0$, and $u{v}^{i}x{y}^{i}z$ in the language for every integer $i\ge 0$.

The language in (i) is not context-free. If it were, pumpThe substring $vxy$, having length at most $p$, cannot meet both the $a$- and $c$-blocks. If pumping changes the number of $a$'s or $c$'s, those two counts cease to agree. If it changes neither, it changes the number of $b$'s while the outer counts remain $p$, so the middle count ceases to be $2p$. Every permitted decomposition therefore fails, contradicting the pumping lemma.

Fix a shift $s$ that is not an eigenvalue of $A$. Inverse iteration computesand may use $r({\mathbf{x}}_k)$ as the eigenvalue estimate.

For a real symmetric matrix, suppose that one eigenvalue ${\lambda }_{\ast }$ is uniquely closest to $s$ and that ${\mathbf{x}}_0$ has a nonzero component in its eigenspace. Since the iteration is the power method applied to $(A-sI{)}^{-1}$, the normalized vectors converge, up to sign, to an eigenvector for ${\lambda }_{\ast }$. If ${\lambda }_{\mathrm{next}}$ is the second-closest eigenvalue to the shift, the asymptotic direction-error ratio isThus a shift close to the desired eigenvalue gives rapid convergence. The Rayleigh quotients converge to ${\lambda }_{\ast }$ and, for a simple eigenvalue, their errors are of second order in the vector error. This is convergence of fixed-shift inverse iteration.

An orthonormal eigenbasis isThe starting vector has the orthogonal decompositionHence its component in the dominant eigenspace is exactly zero. Normalizing $A^k{\mathbf{x}}_0$ givesSince the two remaining eigenvectors are orthogonal,ThereforeThe limit is not the leading eigenvalue $9$ because the nonorthogonality assumption in part (a) fails. On the active spectrum of the power method, the leading eigenvalue is $6$ and the next is $2$; indeedin agreement with the squared spectral-ratio estimate.