What is the "physical" Hilbert space for non-local Hamiltonians?

Question

In their 2011 paper, D. Poulin and coauthors show that the size of "physically" accessible states in Hilbert space for local Hamiltonians is exponentially smaller than the total Hilbert space. Thus, there is an enormous space of states which take an exponentially long time to prepare, and are physically inaccessible by a quantum computer or any real-life quantum-mechanical system.

However, the result by Poulin, et al only holds or local Hamiltonians, so I am interested in what happens when you relax that assumption.

Locality here means that each qubit is only coupled to at most $k$ other qubits, where $k$ is fixed and does not scale with $N$. However, essentially all Hamiltonians in real-life are non-local because of the non-locality of electromagnetism. The Coulomb interaction between electrons is non-local and goes as $V(r)\sim \frac{\rho_1 \rho_2}{r}$, giving $N-1$ couplings per qubit. Similarly for dipole-dipole interactions, etc. which have the form $V(r) \sim r^{-\alpha}$ for different exponents $\alpha$. In all of these cases, each qubit is coupled to all $N$ other qubits.

So my question is has a non-local extension to Poulin et al's proof been made? Or, equivalently, how does the size of physically accessible states in Hilbert space grow with the non-locality of interactions $\alpha$.

I would expect that if we could have a completely non-local Hamiltonian with all-to-all coupling ($\alpha=0$), then all states in Hilbert space are physically accessible. But, as we localize couplings ($\alpha \rightarrow \infty)$), this space should decrease. The mostly physically relevant non-local coupling would be the Coulomb interaction.

Edit: Since there is some confusion, the Coulomb interaction I am referring to takes the following form $$\mathcal{H}_C = \frac{1}{2}\sum_{i,j} \frac{\hat{\rho}_i \hat{\rho}_j}{\vert r_i - r_j\vert}$$ where $\hat{\rho}_i$ would be an operator acting on the the $i$-th qubit and $r_i$ is its spatial position. This interaction is non-local both physically and computationally because it couples qubits which are far away in space, and couples all qubits to all other qubits (i.e., an all-to-all interaction). Rigorously speaking, one cannot argue that this falls under $k$-locality. Moreover, one can choose a smaller decay of $r^{-\alpha}, \alpha<1$ if $\alpha=1$ is not "slow" enough to break out of the Poulin et al argument.

Answer 1

Your assertion that interactions such as the Coulomb interaction are non-local (in the quantum information sense of "k-local") is incorrect. The Coulomb interaction couples two particles, pair by pair. It has thus a bounded locality (or bodi-ness). In the standard formulation of fermionic modes, it is 4-local.

Answer 2

I don't think there's likely to be any efficient way to explore all corners of the Hilbert space on $n$ qubits to prepare any quantum state, regardless of the amount of locality or non-locality.

For example, we could define $|\psi\rangle$ to be a witness for a QMA-complete problem, such as the ground state of some $k$-local Hamiltonian. If we can prepare such a state $|\psi\rangle$ efficiently, even with a quantum computer, then we would have the unlikely conclusion that QMA$\subseteq$BQP. It is (approximately) a tenet of the extended Church-Turing thesis that BQP$\subsetneq$QMA, and if we can prepare such a ground state efficiently then we violate this tenet.

Actually I think the meaning of locality as used in Poulin et al. is not necessarily geometric locality, and is unrelated or only slightly related to any parameter such as $r$ or $\alpha$ indicative of a Coulomb interaction distance. In Poulin et al., a $k$-local Hamiltonian acting on $n$ qubits means that the Hamiltonian can be written as a sum of local Hamiltonians, each acting on $k\le n$ qubits; Trotterization works to deal with the non-commutative properties of the Hamiltonian.

Indeed, although we can simulate some nonlocal Hamiltonians (such as sparse Hamiltonians) efficiently, if we relax the $k$-local condition by asking for the ground state of some other arbitrary nonlocal Hamiltonian, the problem may be even more difficult, and it may be even harder to find the ground state of such a Hamiltonian.

In short, the Hilbert space is likely just too big to be fully explored efficiently, and locality is not necessarily geometric locality.