6
$\begingroup$

In Quantum simulation of chemistry with sublinear scaling in basis size Ryan Babbush and other authors from Google Quantum team argue, when talking about performing Quantum Phase Estimation in 1st quantization, that

The reason for our greatly increased efficiency is that the complexity scales like the maximum possible energy representable in the basis.

But they do not really give a reason why this is the case or point to a reference to understand it better. Does anyone know why this is indeed true?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I think the answer has to do with the Trotter approximation to handle non-commuting terms in the Hamiltonian decomposition. The larger the "weight" of each term, the worse the approximation, so to keep error in check you need to break the Hamiltonian down into more, smaller time slices, increasing time complexity. I will re-read the referenced paper some time today and post a proper answer tomorrow, unless someone beats me to it. ;) $\endgroup$
    – jecado
    Dec 7, 2021 at 14:04
  • 1
    $\begingroup$ Thanks a lot @jecado. I am confused though because they do not use Trotterization but qubitization. However, it's a good idea to try to track this sort of things. Thanks again! $\endgroup$
    – Pablo
    Dec 8, 2021 at 16:22
  • $\begingroup$ Aye, not Trotterization, good catch. Their method has much better error scaling. But, the principle remains; they still need to break the problem into time slices to keep error constant. See my answer below. $\endgroup$
    – jecado
    Dec 8, 2021 at 19:45

1 Answer 1

Reset to default
3
$\begingroup$

The answer is in Eqn. 8 of the referenced paper, and its surrounding paragraph:

The overall complexity [of simulating $e^{-i(A+B)t}$ using the interaction picture formalism and the Linear Combination of Unitaries (LCU) method] depends on the value of $\lambda$, which is the sum of the weights of the unitaries when expressing $B$ as a sum of unitaries. To simulate within error $\epsilon$ the number of segments used is $\mathcal{O}(\lambda t)$, and [a cutoff energy introduces additional poly-logarithmic factors]. The complexity in terms of LCU applications of $B$ and evolutions $e^{-iA\tau}$ is therefore ... $\mathcal{\widetilde O}(\lambda t) $.

After Eqn. 13 they further argue that $\lambda$ in the interaction picture is fairly bounded by $\mathcal{O}(\eta^{5/3} N^{1/3})$, with $\eta$ the number of electrons and $N$ the number of basis orbitals. Around Eqn. 18 they argue the effective complexity of implementing each step is $\mathcal{\widetilde O}(\eta)$. This puts their overall complexity at $\mathcal{\widetilde O}(N^{1/3}\eta^{8/3}t)$, as claimed in the abstract.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yeah, I get this. My question is a bit more in line of how "why the maximum possible energy is representable in the basis", but I now realize they are just referring to the one-norm here? Thanks! $\endgroup$
    – Pablo
    Dec 8, 2021 at 21:05
  • 1
    $\begingroup$ Yes, that's how I read it. I also interpreted the thesis of their work being that the interaction picture lets them use a much smaller-normed Hamiltonian. But, it's true that the paragraph you cite emphasizes the qubit mapping rather than properties of the Hamiltonian. I guess the proper answer to your question needs to establish that the one-norm changes significantly under different representations of the same Hamiltonian? $\endgroup$
    – jecado
    Dec 8, 2021 at 22:12

Your Answer

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

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