Clarification needed: "Simulation" of $e^{-iHt}$ and its time complexity

Question

On page 3 here it is mentioned that:

However, building on prior works [32, 36, 38] recently it has been shown in [39] that to simulate $e^{−iHt}$ for an $s$-sparse Hamiltonian requires only $\mathcal{O}(s^2||Ht||\text{poly}(\log N, \log(1/\epsilon)))$, breaching the limitation of previous algorithms on the scaling in terms of $1/\epsilon$.

Questions:

1. What is meant by "simulate" in this context? Does it mean it takes $$\mathcal{O}(s^2||Ht||\text{poly}(\log N, \log(1/\epsilon)))$$ time to decompose $e^{-iHt}$ into elementary quantum gates given we know $H$. Or does it mean we can compute the matrix form of $e^{-iHt}$ in $$\mathcal{O}(s^2||Ht||\text{poly}(\log N,\log(1/\epsilon)))$$ time given we know the matrix form of $H$?

2. What does $||Ht||$ mean here? Determinant of $Ht$? Spectral norm of $Ht$? I checked the linked ppt and it seems to call $||H||$ the "norm" of $H$. Now I have no idea how they're defining "norm".

Answer 1

1. Yes. Computing this matrix is something we call Hamiltonian Simulation. We do not use the verb "simulate" alone though I think.
2. It is the norm. I think you assume in general they use either the max norm, which is the largest entry of the Hamiltonian, or the norm is referring to the largest eigenvalue in absolute value (which is called the spectral radius and would be less confusing to call it this way). I think it is a bit unclear here but as they mention quantum walks, the max norm is associated (here is a mention of this norm for a quantum walk approach) You can find a very good explanation about Hamiltonian Simulation from this talk from Robin Kothari.

Answer 2

"Hamiltonian Simulation" means applying the time evolution given by $H$ to some initial state $|\psi\rangle$, i.e. to implement the unitary $U=e^{iHt}$ on a quantum computer.

If not mentioned otherwise, for an operator $H$, $\|H\|$ generally denotes the operator norm, i.e., the largest eigenvalue (in absolute value) of $H$. Whether this is really the case the answer linked is unclear, see the answer by cnada.