3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Does the subsection on run-time and error analysis in the paper clarify your question? $\endgroup$
    – keisuke.akira
    Commented 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
    Commented Jul 5, 2020 at 7:41

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented 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$
    – Nicholas Sathripa
    Commented 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
    Commented 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$
    – Nicholas Sathripa
    Commented Jul 7, 2020 at 11:24
0
$\begingroup$

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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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