5
$\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$
1
  • $\begingroup$ I'm not convinced there is a completely rigorous proof of such a thing... $\endgroup$
    – Mithrandir24601
    Dec 22, 2019 at 14:00

1 Answer 1

5
$\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”.

$\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.