# Confusion regarding time complexity in the HHL algorithm

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?

• Does the subsection on run-time and error analysis in the paper clarify your question? Jul 5, 2020 at 4:05
• 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. Jul 5, 2020 at 7:41

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.

• 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? Jul 7, 2020 at 1:06
• 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. Jul 7, 2020 at 9:39
• 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)$? Jul 7, 2020 at 10:13
• 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. Jul 7, 2020 at 11:24

I think it's because they use $$e^{iAt/T}$$ as U in the subroutine of QPE, here, $$T = 2^t$$, where t is the number of qubits in the clock register. So even if QPE needs an exponential number of execution of this, it doesn't result in an exponential runtime.

(The trick is, I guess, in their part of non-exact QPE and relabeling. Not very sure about that tho, but their analysis about the time complexity does hold)