References for quantum state praparation: what states are easy to prepare and which ones aren’t?

Question

I’m looking for references on quantum state preparation. I know there’s a plethora of papers on this topic but I don’t know how to narrow it down or figure out which ones to prioritize. In general, I’m interested in the question of: “which class of states are difficult to prepare?”.

Answer 1

That's a pretty broad question. But we can use complexity theory to get some guidance. Below I explore the implications of the standard assumptions that BPP$\subsetneq$BQP$\subsetneq$QCMA$\subsetneq$QMA.

Intiially, there are many states that we can efficiently prepare with a quantum algorithm, because there's a BQP-algorithm for their preparation. We could use one or more of adiabatic state preparation, amplitude amplification, post-selection, Grover-Rudolph state preparation, etc. If we have a good guiding-state description of a state "close to" a ground state of a Hamiltonian of interest, we can prepare the guiding state and measure the energy to hope to get to the corresponding ground state.

Presumably below BQP is BPP; since Tang's breakthrough a couple of years ago we know how to access entries of a quantum state in a classical manner for many such states.

But most states are presumably not so easily prepared. For example for an arbitrary local Hamiltonian, assuming BQP$\subsetneq$QMA, we can not so easily prepare the ground state thereof. This is the QMA-completeness of $k$-local Hamiltonian. So, ground states of arbitrary $k$-local Hamiltonians are not so easily prepared.

Between BQP and QMA is QCMA - these are states that would be easily prepared if we had a classical description of a quantum algorithm so as to prepare them, but we don't know how to easily describe the quantum algorithm to prepare them. So, any problem that's QCMA-complete naturally lends itself to a state that's also not so easily prepared.

A paper that touches on many of these, at least in its introduction, is Gharabian and Le Gall's. They get close to putting necessary and sufficient conditions on the accuracy ground-state calculations to try to learn more about the split between BPP and BQP (and QMA).