Survey of which 'physically interesting' many-body states can be efficiently prepared on a quantum computer?

Question

For digital quantum simulation of many-body problems, efficiently preparing an initial state of 'physical interest' (e.g. ground states, thermal states, topologically ordered states etc.) is very relevant.

There is quite an extensive amount of literature on this problem, e.g. proposing efficient quantum algorithms for certain states or classes of states or proving that the preparation for some states is hard. Many reviews of digital Hamiltonian simulation do not discuss initial state preparation in much depth however, and often focus more on the problem of simulating the dynamics (by e.g. discussing Trotterisation, Quantum Signal Processing, etc.) or only discuss very fundamental techniques, like ground state preparation with quantum phase estimation (which is not 'efficient' in the sense of exponential time complexity, as required by ground state preparation being QMA-complete). Moreover many papers estimating the required resources for some quantum simulation task under some assumption of future hardware focus more on variational methods without proven bounds.

Is there a review paper, workshop tutorial or some other resource systematically surveying which states or classes of states are efficiently preparable or not? I am particularly interested in non-heuristic, proven results and was hoping for a perspective from many-body physics, in the sense of 'for these situations of physical interest the initial state preparation problem is solved by this and that, for these situations it is proven impossible and for these it is an open problem'.

Answer 1

I think it is really tough to provide a complete and comprehensive list of conditions describing which states can be efficiently prepared, at least because we don't know how to split BQP from QMA yet, and ground states for some Hamiltonians may be easily/efficiently prepared, e.g. in BQP, while other generalized Hamiltonians may be QMA-hard. Even further many classical techniques related to matrix product states (MPS) and the density matrix renormalization group (DMRG) appear pretty efficient, e.g. may even be in P in some situations.

Nonetheless we can also ask about which states can be prepared adiabatically - as addressed in Aharanov and Ta-Shma and as related to the Statistical Zero Knowledge complexity class. We also have the old result of Grover and Rudolph on efficiently integrable probability distributions.

In many-body simulation I think there's this lovely interplay between:

• Efficient classical simulation with DMRG-like methods;
• Efficient quantum state preparation and the BQP-completeness of some Hamiltonian simulation;
• Inefficient quantum state preparation and the QMA-completeness of other Hamiltonian simulation; and
• (Violations of) the so-called "area law" which describes conjectured properties of entanglement entropy and the relation to each of the above.

Answer 2

This is only a partial answer, as it is not a survey paper/etc. and does not claim to be exhaustive, but the PhD thesis "Hamiltonian Complexity in Many-Body Quantum Physics" by James David Watson has a background chapter that lists some results on e.g. ground states.

Answer 3

I am not sure whether this site existed at the time I asked the question, but since then I became aware of https://hamiltonianjungle.xyz which aims to collect results on Hamiltonian complexity and seems to be helpful (and growingly so) in particular for ground state preparation complexity of various Hamiltonians.