5
$\begingroup$

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".

|improve this question
$\endgroup$
4
$\begingroup$
  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.
|improve this answer
$\endgroup$
  • $\begingroup$ Do you have any evidence for 2.? $\endgroup$ – Norbert Schuch Nov 4 '18 at 13:04
  • 1
    $\begingroup$ @NorbertSchuch Please, find page 2 of the paper arxiv.org/pdf/1501.01715.pdf where it is mentionned. $\endgroup$ – cnada Nov 4 '18 at 13:15
  • $\begingroup$ Thanks. But is this the same scaling as the one in the paper in the question? E.g. the link you give scales like O(N), not O(log(N)), so it seems different. In any case, if no explanation is given $\|\cdot\|$ is the operator norm -- or (sloppily) it could be a norm which scales just as it (since it wouldn't really matter), but this doesn't seem to be the case for the max norm. $\endgroup$ – Norbert Schuch Nov 4 '18 at 13:19
  • $\begingroup$ Ok I will add the mention it really depends on the Hamiltonian simulation technique used. $\endgroup$ – cnada Nov 4 '18 at 13:25
  • 1
    $\begingroup$ Oh ... different $N$, I see: $N=2^n$. Seems you are right that in this case the max-norm is meant. Then it is very sloppy to just write $\|\cdot\|$! (Unless sparsity somehow guarantees that the norms are related.) $\endgroup$ – Norbert Schuch Nov 4 '18 at 13:26
2
$\begingroup$

"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.

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks. That makes sense. By the way, do you know of any reference which discusses how long (time complexity) it takes to classically compute the entries of the matrix exponential $e^{-i\operatorname{H}t}$ for different types of $\operatorname{H}$? $\endgroup$ – Sanchayan Dutta Nov 4 '18 at 13:11
  • $\begingroup$ Now I should say that is what $||\cdot||$ usually means. It could of course be that the paper you link to is sloppy and cnada is in fact right (but then this would be bad notation). Note that the difference between the two can be exponential in the number of qubits! --- What do you mean compute the matrix exponential, and what types of $H$? Have you checked en.wikipedia.org/wiki/Matrix_exponential? Or are you just interested in single entries, rather than the full $e^{iHt}$? $\endgroup$ – Norbert Schuch Nov 4 '18 at 13:14
  • $\begingroup$ I mean computing all the entries of $e^{-i\operatorname{H}t}$, not just a few entries. By different types I meant, diagonal matrix, 1-sparse matrix, s-sparse matrix and so on. For instance, exponentiating a diagonal matrix would obviously take less time than an arbitrary 1-sparse matrix. And yeah, I did check that Wikipedia page but it doesn't discuss the time complexities explicitly. Maybe I'll have to dig into the references or ask on Math SE... $\endgroup$ – Sanchayan Dutta Nov 4 '18 at 13:22
  • $\begingroup$ @Blue ... or you program it in matlab/julia/numpy/... and measure the scaling ;) $\endgroup$ – Norbert Schuch Nov 4 '18 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.