# Proof that most Hamiltonian evolutions are not efficiently approximable by quantum circuits

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?

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

## 1 Answer

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”.