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?
$\begingroup$
$\endgroup$
1
asked Dec 22, 2019 at 9:48
-
$\begingroup$ I'm not convinced there is a completely rigorous proof of such a thing... $\endgroup$– Mithrandir24601 ♦Dec 22, 2019 at 14:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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”.
answered Dec 22, 2019 at 12:19