4
$\begingroup$

My task is to simulate quantum evolution. To do that I need to perform this operation

$$w = e^{-itH}v$$

where $H$ is a sparse matrix and $v$ is the initial column vector. I am wondering if there is a way to calculate vector $w$ without evaluating the MatrixExp? What I mean is: if $t$ is really small (time step) is there some kind of an algorithm (stable and accurate) which uses only matrix-vector multiplication?

For example:

$$w(t) = \left(e^{-i\frac{t}{n}H}\right)^{n}v\\ \frac{t}{n} = dt$$ Algorithm would go like this: $$w(0) = v \\ w(dt) = e^{-idtH}w(0)\\ w(2dt) = e^{-idtH}w(dt)\\ \ldots$$

and I don't know, replace $$e^{-idtH}\approx 1 -idtH$$

One thing should remain unchanged: norm of the vector $||w(t)||=1$

$\endgroup$
3
$\begingroup$

In addition to Godric Seer's suggestion, you can also use rational approximations to the exponential, e.g.

$e^z = \frac{1 + z/2}{1 - z/2} + \mathcal{O}(z^3)$,

to devise more accurate approximations to the matrix exponential:

$e^{-itH} \approx (I + itH)^{-1}(I - itH)$.

This approximation has the advantage of being a unitary operator, so that in exact arithmetic $\|w\|$ remains unchanged. Of course you have to watch out in floating point arithmetic if the condition number of $H$ is very large.

The paper 19 Dubious Ways to Compute the Exponential of a Matrix is worth a read, and if you want to dig deeper, Saad's book is both very readable and very comprehensive.

$\endgroup$
1
$\begingroup$

By definition

$e^{idtH} = \sum\limits_{k=0}^\infty \frac{1}{k!}\left( i dt H\right)^k$

which is easily approximated by truncating the sum after a number of terms. Ideally you would want to use only two terms so that

$e^{i dt H} \approx 1 + i dt H$

What that means is that $\frac{1}{2}(i dt H)^2$ must have a small effect on the solution. Assuming $H$ has eigenvalues $\lambda_i$, then you need $dt^2 \lambda_i^2 << 1$ for every eigenvalue. As long as you choose a small enough $dt$ that this is true, you can avoid the matrix exponential with only the first two terms of the sum.

$\endgroup$
  • $\begingroup$ This is actually very bad idea link Better way is to use SOD algorithm or Expansion of Exponential function in Chebyshev polynomials $\endgroup$ – WoofDoggy Mar 18 '15 at 18:11
  • $\begingroup$ I agree that this is likely the roughest and least efficient way to approximate the exponent, but since the question started heading this way, I wanted to give a criteria for it. $\endgroup$ – Godric Seer Mar 18 '15 at 18:18
1
$\begingroup$

Is H time-dependent? If not, can not you just diagonalize H, and then express your initial vector "v" as a linear combination of the eigenvectors of H, and then propagate those?

If H is time-dependent, another technique (in addition to those already mentioned) would be to use a split operator technique like the Trotter decomposition.

$\endgroup$
  • $\begingroup$ Yes, I think it would be the best way if my hamiltonian is the same during calculations - just diagonalize it once and store diagonal vector with transition matrix in a memory. However, imagine at every momemt of time You have a collection of different hamiltonians (simulating noise) to calculate mean vector - I am not sure if diagonalization is better than MatrixExp algorithm? $\endgroup$ – WoofDoggy Mar 24 '15 at 17:51

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.