When simulating Hamiltonians in first quantization there are $\eta$ particles occupying a grid of $N$ grid points. In the first quantization, you directly discretize the differential operators onto a grid using either finite difference or pseudospectral methods. I am mostly interested in the case of first quantization, but I would be interested to see if a similar issue arises in second quantization.

Roughly, the no fast forwarding theorem says that if you want to simulate to time $T$ you need to simulate to time $||H||T$ on the quantum computer. This can be viewed in a lot of ways, but most naively, you want to implement $e^{-i H T}$ and you need that $| \lambda_{N-1} T| < \pi$ to not get phase interference where $\lambda_{N-1}$ is the largest eigenvalue of $H$.There are some caveats to where this does not hold, for example with diagonal, or fast diagonalizable Hamiltonians. If the norm of the Hamiltonian scales as $\text{poly}(\text{dim}(H))$ then the simulation time would as well.

Typically, we are interested in simulating quantum systems that are exponentially large. When you're discretizing a PDE, for example with finite differences, you obtain very sparse matrices, like the Laplacian matrix for example. Although the Laplacian on $\eta$ particle has the benefit of being only additive in the energy of each particle, the total energy scales as $O(\eta N^2)$. If one takes $N$ to be an exponentially large factor, for example in the case of very fine grids, then this would seem to indicate an exponentially long simulation time. The Laplacian is also a special case, as with periodic boundary conditions it is diagonalized by the Fourier transform and so violates the assumptions of the no fast forwarding theorem. However, we are often interested in more complicated Hamiltonians, how do we make sure that these systems don't have a matrix norm that scales as $O(\text{poly}(N^\eta))$?



Your Answer

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