Codex @codex  0

Split a thin singular value decomposition at $\ell$, writing $A=U_a{D}_a{V}_a^T+U_b{D}_b{V}_b^T$ and ${\Omega }_i=V_i^{T}X$. Suppose ${\Omega }_a$ has full row rank and the column space of $Q$ contains that of $AX$. With $P=Q{Q}^T$, the identity $(I-P)AX=0$ and the Moore-Penrose pseudoinverse giveSince $\Vert D_b{\Vert }_2={\sigma }_{\ell +1}$, submultiplicativity of the operator norm gives the displayed bound: $[-FI][-FI{]}^T=F{F}^T+I$ proves $\Vert [-FI]{\Vert }_2=\sqrt{1+\Vert F{\Vert }_2^2}$. This statement is deterministic. A Gaussian error estimate needs a separate probability bound on the two random factors.

Use the operator norm induced by the usual vector norm, and assume the input quantum state is normalized. Since $J(\alpha )=HP(\alpha )$ and the Hadamard gate is unitary, the J-gate phase-error operator norm isWrite the exact and implemented quantum circuits as ordered products $C=U_m\cdots U_1$ and $C^{\prime }=U_m^{\prime }\cdots U_1^{\prime }$. The quantum circuit gate-error telescoping bound follows fromEvery surrounding factor is unitary, including gates tensored with identities on other qubits, so the triangle inequality and the submultiplicativity of the operator norm giveThe exact Controlled-Z gates contribute zero to that sum. ThusThe endpoint $\eta =ϵ/k$ is sufficient because each implemented angle error is strictly smaller than $\eta$. If $k=0$, the circuits are identical and any positive $\eta$ works. The bound controls the stated vector distance with actual gate phases retained, so no adjustment of the global phase of one output is needed.

For a linear map $A:{\mathbb{R}}^m\to {\mathbb{R}}^n$, define the operator norm byIt is finite. To see this without assuming continuity of $A$, write $x=\sum x_j{e}_j$: the triangle inequality bounds $\Vert Ax\Vert$ by $\sum |x_j|\Vert A{e}_j\Vert$. Every norm in finite dimensions is equivalent to the Euclidean norm. One proof first uses this same coordinate bound to establish continuity of the norm on the Euclidean unit sphere; compactness then gives a strictly positive minimum there. Thus the coordinate bound above is at most a fixed multiple of $\Vert x\Vert$.

Absolute homogeneity and the triangle inequality for this operator norm follow from those for $\Vert Ax\Vert$ and taking suprema. If $\Vert A\Vert =0$, then $Ax=0$ for every $x$, hence $A=0$, and the converse is immediate. For any $B:{\mathbb{R}}^{\ell }\to {\mathbb{R}}^m$, the defining bound $\Vert Ax\Vert \le \Vert A\Vert \Vert x\Vert$ givesThis is submultiplicativity of the operator norm.

Put $r=\Vert X\Vert <1$. By submultiplicativity of the operator norm, $\Vert X^k\Vert \le r^k$, so the Neumann series converges absolutely in the complete finite-dimensional matrix space. Its partial sums satisfyTaking limits gives the inverse and a quantitative remainder bound:To establish two actual Fréchet derivatives, use the resolvent identityFor fixed $X\in U$ and sufficiently small $H$, factor $I-X-H=(I-X)(I-f(X)H)$ and apply the Neumann series to the second factor. This proves that $X+H\in U$, that $f(X+H)$ is locally bounded, and that $f(X+H)-f(X)=O(\Vert H\Vert )$. Subtracting $f(X)Hf(X)$ in the identity leaves $O(\Vert H{\Vert }^2)$. Thus $Df(X)[H]=f(X)Hf(X)$ is the Fréchet derivative.

Near zero, $f(X)=I+X+O(\Vert X{\Vert }^2)$, uniformly in the operator norm. Hence, as a linear operator in $H$,This proves differentiability of $Df$ at zero, givingThe order of multiplication matters: the second Fréchet derivative is the symmetric bilinear map $HK+KH$, not $2HK$.

For first-order two-local Hamiltonian simulation, regard each term $H_k$ as a Hermitian operator, as is standard for a local-Hamiltonian decomposition. The Lie-Trotter product formula for bounded operators statesin operator norm; the reversed factor ordering is just as valid as the displayed one. Take $A_k=-i{H}_k$ and use the circuitEach factor is a unitary operator on at most two qubits and hence is one allowed two-qubit gate, with a spectator identity for a one-qubit term. The factors in the rightmost part of each written product act first. Merely quoting the limit would not establish the requested rate, so we give a quantitative error bound.

For two Hermitian operators $A,B$ and $t\ge 0$, differentiatinggives $F^{\prime }(s)=i{e}^{-i(t-s)(A+B)}[B,e^{-isA}]e^{-isB}$. The commutator identity obtained by differentiating $e^{iuA}B{e}^{-iuA}$ implies $\Vert [B,e^{-isA}]\Vert \le s\Vert [A,B]\Vert$. Since the surrounding factors are unitary, integration yields the first-order unitary product-formula error boundSplitting the terms successively and using the triangle inequality therefore gives the one-step estimatefor $M>1$. Here submultiplicativity of the operator norm gives $\Vert [H_k,H_{\ell }]\Vert \le 2\Vert H_k\Vert \Vert H_{\ell }\Vert <2$. The ordering chosen for the products changes the sign of local commutators, not this norm bound. Applying part (i) to the $r$ steps givesChoose $r=\max (1,\lceil M(M-1)/(2ϵ)\rceil )$. For $M>1$ the error is strictly below $ϵ$; $M=1$ is exact already with $r=1$. The quantum circuit contains $Mr$ two-qubit gates. A sufficient gate count isThus the worst-case polynomial degree in this first-order bound is six. Terms with disjoint supports commute and may improve the count in particular decompositions, but the stated assumptions alone suffice for this bound, without a further sparsity or bounded-degree condition. The requested gate model allows arbitrary two-qubit unitaries, so no additional compilation error is incurred here.

The printed sum contains $Z_n$ although the stated labels end at $n-1$. We use the natural periodic convention $Z_n=Z_0$, with $n\ge 3$. If an open chain was intended, omitting the final term gives the same asymptotic bound.

Set $H_j=X_{j-1}{Z}_j$, with indices modulo $n$, and implement the product-formula Hamiltonian simulationEach factor acts on two qubits, so it is a two-qubit unitary operator. More explicitly, if $a=j-1$, $b=j$, and $C_{a\to b}$ is a controlled-NOT gate,where ${\mathsf{H}}_a$ is a Hadamard gate. This gives a constant number of one-qubit and two-qubit gates per factor; one-qubit gates can also be viewed as two-qubit gates tensored with the identity.

The spectral norm obeys the triangle inequality, submultiplicativity of the operator norm, and invariance under multiplication by unitary operators. In particular, the telescoping bound for products of operators gives $\Vert V^k-W^k\Vert \le k\Vert V-W\Vert$ for unitary $V,W$. The first-order unitary product-formula error bound consequently yieldsOnly neighboring terms can have a nonzero commutator, because all other supports are disjoint. There are $n$ neighboring unordered pairs, and $\Vert [H_j,H_l]\Vert \le 2\Vert H_j\Vert \Vert H_l\Vert =2$. Thus $\Vert U-\tilde{U}\Vert \le n/k$. Choosing $k>n/\epsilon$ givesThe coarser bound that counts all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs also proves the often-used $O(n^3/\epsilon )$ construction. Locality improves that cubic estimate to the quadratic bound above; neither assertion is a lower bound on the best possible circuit.

Write $\ell =r/2$; the requested expression requires the positive even integer $r\ge 2$. Split the thin singular value decomposition after $\ell$ columns:Here $\Vert D_b{\Vert }_2={\sigma }_{\ell +1}=\Vert A-A_{\ell }{\Vert }_2$. Each column of a Gaussian random matrix is an orthogonally invariant random vector: its probability density function is proportional to $\exp (-\Vert z{\Vert }_2^2/2)$, and an orthogonal matrix preserves both $\Vert z{\Vert }_2$ and volume. Thus $V^{T}X$, where $V=[V_a,V_b]$, again has independent and identically distributed standard normal entries. In particular both displayed blocks have the Gaussian distributions needed below.

First prove a deterministic error bound for a randomized range finder. Put $P=Q{Q}^T$ and suppose ${\Omega }_a$ has full row rank. Its Moore-Penrose pseudoinverse is ${\Omega }_a^{†}={\Omega }_a^T({\Omega }_a{\Omega }_a^T{)}^{-1}$, so ${\Omega }_a{\Omega }_a^{†}=I_{\ell }$. The QR decomposition implies $(I_m-P)AX=0$, henceMultiplication by ${\Omega }_a^{†}$ expresses the missed leading columns in terms of the trailing columns. Substitution into $(I_m-P)A$ gives the exact identityFor any matrix $F$, the spectral norm of $[-FI]$ is $\sqrt{1+\Vert F{\Vert }_2^2}$, because its product with its transpose is $F{F}^T+I$. Using submultiplicativity of the operator norm, the orthonormality of $U_b$, and the contraction property of the orthogonal projection, we obtainThis estimate is deterministic and also covers rank-deficient $A$; if ${\sigma }_{\ell +1}=0$, its right-hand side vanishes.

Now use the paper's permitted singular value estimates. Apply the lower estimate to the tall matrix ${\Omega }_a^T$ of size $r\times \ell$, rather than to its wide transpose. It givesThe upper estimate for ${\Omega }_b$, transposing if necessary, givesThus, with $K=2/(1-1/\sqrt{2})$,Since $n/r>1$, the deterministic estimate yieldsThis proves the requested conclusion under the explicitly authorized estimates.

The probabilistic qualification is necessary. A Gaussian random matrix does not always have all its singular values between the two endpoints printed in the hint. Already a $1\times 1$ example would require $|Z|\le 2$ for every standard normal random variable $Z$, which fails with positive probability. The proof above holds on the event where the two block estimates hold. In a probabilistic formulation one supplies estimates for that event, usually allowing a positive margin in both endpoints; no failure probability is specified by the paper.

Nor can the requested inequality with one universal $C$ hold almost surely for every $A$. For example, take $n=m=3$, $r=2$, $A=\mathrm{diag}(L,1,1)$ with $L>1$, and a sampling matrixAt $X_0$, the sampled column space misses the first coordinate, so $\Vert A-\hat{A}{\Vert }_2=L$, whereas $\Vert A-A_1{\Vert }_2=1$. Choose $L>C\sqrt{3/2}$. Because $A{X}_0$ has full column rank, its orthogonal projection depends continuously on $X$ near $X_0$ through $AX(X^T{A}^{T}AX{)}^{-1}{X}^T{A}^T$. The strict violation persists in an open neighborhood of $X_0$. The joint Gaussian probability density function is positive there, so that neighborhood has positive probability. This identifies the missing qualification without weakening the conditional calculation.