Welcome on Physics SE :) Please also provide details on any attempt at solution of the question that you have done so far.

Please show the work you have done. I have voted to close this question as off-topic, as homework, because it is really just a problem you are asking us to do (and is somewhat homework like). Please show your work, like Sanya said.

@Sanya: Thank you! My attempts so far were focused on disproving the above conjecture, i.e. find a counterexample. In particular, I tried with some well-known states (e.g. graph, Dicke, AKLT states) but I had no luck (I can provide all the details, however I don't think they can be really useful since they concern very particular states). So I'm hoping to receive some insights/ideas from the Physics SE community.

Can you clarify what you mean by invariance-satisfying unitaries? What invariance condition are they satisfying? @heather out of curiosity, what course might you expect to find this question in as homework?

@JoelKlassen, it doesn't have to be homework exactly; it is about asking the physics.SE community to do a problem for them, especially with little to no work shown, and with the question not asking about a specific physics concept. In this case, I personally think it is the former that is true here.

@JoelKlassen: I edited the OP. I hope that now is clear.

(Likely unhelpful: if the neighborhoods aren't connected, the answer is no. So I'll assume they are.) Also, it seems helpful to think in terms of universal gates, if you aren't already: then you can see that if you drop the "invariance-satisfying" requirement, the answer is yes. Maybe you can modify the proof of that. I suppose the frustration-free part is necessary to guarantee the existence of any invariance-satisfying unitaries supported on single neighborhoods.

@DanielRanard: Thank you for the comment! Could you please expand the part about dropping the "invariance-satisfying" requirement? Specifically, how does the proof work? (And yes, the neighbourhoods are connected)

Note that by parameter counting, you can see that you need to apply an exponential number of layers of unitaries: A general unitary which preserved one vector has $(d^n-1)^2$ real parameters (with $n$ the system size and $d$ the local Hilbert space dimension), whereas the number of local regions is linear in $n$. Not sure if that's what you have in mind. --- But giving more background is likely going to be helpful.

@NorbertSchuch: Interesting observation. However, my question doesn’t concern complexity issues. Indeed, I'm interested on the existence of a local (no matter how complex) invariance-preserving decomposition of a global invariance-preserving unitary.

Did you check for counterexamples on small systems -- e.g., 3 sites, where the reduced density matrices on sites 12 and 23 have almost maximal rank (e.g., space dimension minus 1)? This might pose an obstacle to having such a decomposition.

This may be a really silly question, but does your $|\psi\rangle$ decompose into neighborhood components, something like $ |\psi\rangle = \sum_k{a_k |\psi^{(k)}\rangle}$ with $\langle \psi^{(j)} | \psi^{(k)} \rangle = \delta_{jk}$? If so, and since the system is finite dimensional, does the Hilbert space decompose into a sum of 'neighborhood spaces'?

@Jacquard, Re: dropping requirement that the unitaries in the product leave state invariant. Consider chain of qubits. Then any unitary is a finite product of unitaries on pairs qubits, e.g. see www-bcf.usc.edu/~tbrun/Course/lecture12.pdf. If you restrict to only using unitaries on pairs of neighbors, you get the same result, because you can generate any permutation of qubits by a sequence of swapping neighbors, and from there you can generate any unitary on non-neighboring pairs.

@NorbertSchuch: I haven't tried to check examples of this form. This can be a good idea, thanks!