Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 324 / 4

The spectral norm is the induced Euclidean operator norm:It is the largest singular value. From the definition, multiplying on either side by a unitary operator leaves the norm unchanged: right multiplication permutes the unit sphere of possible inputs, and left multiplication preserves output lengths. In particular every unitary operator has norm one.

For unitary product telescoping, replace the factors one at a time. With empty products interpreted as the identity,All cross terms cancel. By the triangle inequality and unitary invariance of the spectral norm,This bound is independent of the dimension and does not assume that any of the factors commute.

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.