In the paper of HHL algorithm (Quantum algorithm for linear systems of equations), the time complexity of simulating $e^{i A t}$ for a hermitian matrix A is $\tilde{O}\left(\log (N) s^{2} t_0\right)$. Let $T$ be the time required for the phase estimation subroutine. Then, the total-time of simulation should be $T \cdot \tilde{O}\left(\log (N) s^{2} t_0\right)$.

Why, then, is the time complexity $\tilde{O}\left(\log (N) s^{2} \kappa^{2} / \epsilon\right)$?

In the subsection of error and run-time, they said that the run-time is $\tilde{O}\left(\kappa \left(T_B + t_0 s^2 \log (N) \right) \right)$; why is it not $T \cdot \log (N) s^{2} t_0$ in the run-time, just $\log (N) s^{2} t_0$? Does that mean they just simulate $e^{i A t}$ one time?

Why does this paper needs T times simulation?

  • $\begingroup$ Does the subsection on run-time and error analysis in the paper clarify your question? $\endgroup$ Jul 5, 2020 at 4:05
  • $\begingroup$ No, it does not. I read the paper Quantum support vector machine for big feature and big data classification which have T simulation. So it confuses me, and thank you for help. $\endgroup$
    – zhenyu
    Jul 5, 2020 at 7:41

1 Answer 1


It is incorrect to say that the time of simulation is $T O(\log N s^2t)$ (it's also better written as $O(T\log N s^2t)$). Conceptually, the simulation time ends at $O(\log N s^2t)$. If you want to consider the phase estimation, that's another (more complex) unitary, which includes hamiltonian simulation. If you were to think this in terms of function composition, let $U=g(H,t,initial\_state,)$ be the function that performs hamiltonian simulation, and $f(U, args*)$ be the phase estimation subroutine, which takes as input a unitary (and the input to create the unitary, which in this case are the input of $g$, an hypotetical function (which you can imagine written in a quantum programming language) that builds the unitary for hamiltonian simulation U.

The reason there is no time dependence in the runtime is because they implicitely set $t=1$ and perform a time-indepentent Hamiltonian simulation. The other paper performs a time dependent simulation.

  • $\begingroup$ Thanks for you help. I also have some quesions. Is the matrix $A$ simulated $T$ times in phase estimation? If it is, should the complexity of phase extimation is $ \tilde{O}\left(T \cdot\log (N) s^{2} t_0\right)$? And how can i see the Hamiltonian simulation is time independence or not? $\endgroup$
    – zhenyu
    Jul 7, 2020 at 1:06
  • $\begingroup$ yes is simulated T times, where T=1/epsilon, and epsilon is the precision in the eigenvalues you want. Is often implicit in the context of usage if the hamiltonian simulation is time dependent or not. If t=1 is time independent. $\endgroup$ Jul 7, 2020 at 9:39
  • $\begingroup$ Thanks for your comment. If $T$ is $1/ \epsilon$, the total run-time is $\tilde{O}\left(\kappa \left(T_B +1/ \epsilon * t_0 s^2 \log (N) \right) \right)$? $\endgroup$
    – zhenyu
    Jul 7, 2020 at 10:13
  • $\begingroup$ perhaps. you need to perform an error analysis in order to choose the precision in the phase estimation. it should be written in the paper. $\endgroup$ Jul 7, 2020 at 11:24

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.