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.


2 Answers 2


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.

  • $\begingroup$ +1 After revisiting this question a year later, I see that you're right, the argument applies to all physical systems! Since you are an expert in the field, can I ask you a followup? Is there any paper which discusses the ramifications of this paper for many-body condensed matter? It seems to mean that most states cannot contribute to the entropy and is subtle how ergodicity works with "exponentially far" states $\endgroup$ Jul 8, 2023 at 5:57

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.

  • $\begingroup$ I feel my question is being missed here. I'm trying to understand how much locality vs non locality changes the size of "physically accessible" states. I think you're arguing that it will never be the case the case that all states in Hilbert space will be physical, but that's a separate point, I would say. Clearly the number of accessible states should increase going from local to non local, but how much? I should say that this is more than just a CS question, the answer to this question would place limits on all possible quantum states of matter in real life materials and systems. $\endgroup$ Aug 14, 2022 at 5:44
  • $\begingroup$ Well, sorry I’m not understanding! Maybe I’m confused about the use of “non-local”. If we only have nearest neighbor interactions, we can simulate all-to-all interactions with polynomial overhead, by using a chain of SWAP gates. The all-to-all interactions don’t buy you any efficiency. Also, presumably “real life materials” obey the extended Church-Turing theorem, and they won’t evolve into a quantum state that is inaccessible… Sorry I can’t help more! $\endgroup$ Aug 14, 2022 at 12:21
  • $\begingroup$ No worries, I probably did not write things clear enough, or just have a poor understanding of the paper. Anyways, if it's simply a matter of swap gates, doesn't that mean the assumption of a local Hamiltonian is unnecessary? As in, you're arguing that the theorem by Poulin can be trivially extended to non-local Hamiltonians? $\endgroup$ Aug 14, 2022 at 16:58
  • $\begingroup$ Well, a really subtle and often confusing point, that I still struggle with, is that geometric locality is distinct from computational l’ity. think you have been asking about the former, while the paper might mean the latter. A computationally $k$-local Hamiltonian on $n$ qubits can be written as a sum of a polynomial number of simpler Hamiltonians, each acting on at most $k\le n$ qubits (and acting as the identity on the other $n-k$ qubits). A computationally non-local Hamiltonian might have an exponential decomposition into simpler Hamiltonians… google the “local Hamiltonian problem”. $\endgroup$ Aug 14, 2022 at 17:33
  • $\begingroup$ But is it not the case that the Coulomb interaction is both an example of geometric and computational non-locality? It couples everything to everything after all, so you can't write it as a $k$-local Hamiltonian. $\endgroup$ Aug 14, 2022 at 19:21

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.