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

However, the result by Poulin et al only holds true for 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$. As we know from solid-state physics, most Hamiltonians in real-life systems are non-local because electromagnetism is non-local. This is most obvious in the Coulomb interaction between electrons, which is non-local and goes as $V(r)\sim \frac{\rho_1 \rho_2}{r}$. Similar effects occur with dipole-dipole interactions, etc. which generally 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.

Intuitively, I would expect the result of Poulin et al to still hold to some extent depending on the exponent $\alpha$. 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, which I am interested most in.

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 both couples qubits which are infinitely far apart in space, and couples all qubits to all other qubits (i.e., an all-to-all interaction). Note that the $r^{-1}$ is a very slow drop off, so there are logarithmic corrections to wavefunctions even as $r\rightarrow \infty$, as described in Sakurai's Quantum Mechanics textbook. So rigorously speaking, one camnot 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.


1 Answer 1


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$
    – Mark S
    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$
    – Mark S
    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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.