4
$\begingroup$

How to rigorously prove that finite Hamiltonians (for $n$-qubit systems), in general, are not efficiently$\dagger$ simulable (in the Hamiltonian simulation sense) using $\mathrm{poly}(n)$ number of quantum gates?

$\endgroup$
  • $\begingroup$ I'm not convinced there is a completely rigorous proof of such a thing... $\endgroup$ – Mithrandir24601 Dec 22 '19 at 14:00
  • $\begingroup$ Are you suspicious that such a proof might imply something stronger that’s not yet known to be true? $\endgroup$ – Mark S Aug 23 at 3:06
4
$\begingroup$

Perhaps not absolutely rigorous, but....

We know that the vast majority of unitaries require exponentially large circuits. So, define $H=i\ln U$. The vast majority of these Hamiltonians take exponentially long to simulate. While there is ambiguity in taking the log, it doesn’t matter how you choose to resolve that ambiguity because they are all “bad”.

| improve this answer | |
$\endgroup$

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.