Your second question is easy to answer: yes, you could say that. However, it is highly unlikely that you will find any experimental method to approximate the ground state energy of one of those QMA-hard models within a polynomial gap. If you did, you would find an efficient method to solve problems in QMA and therefore, problems in NP. We believe these problems cannot be solved efficiently within any realistic model of computation, classical or quantum.
Your first question is trickier. I would reformulate it as follows (let me know if you do not like my formulation): does the complexity class BQP naturally capture the computational power of analog quantum simulators? (Notice that the definition of BQP is unique and you cannot change it; the relevant question to me is whether it is the natural class associated to the quantum model of computation that we consider.)
So, I am going to try to answer my reformulation of your question. In short, I believe BQP might not be the relevant complexity class to talk about analog quantum simulators. I will focus on the class BQP because the question is already complicated for this class.
I believe it is presently unclear what type of computational problems analog quantum simulators can solve. In my view, this is hard to answer because of a combination of the following reasons: (1) there seems various different types of quantum simulator, so it is not clear to me whether one can define a computational model for all of them; (2) many authors seem not to be interested in doing quantum error correction with their quantum simulators.
First of all, I would say that the honest answer is that we still do not know whether the complexity class BQP faithfully represents the computational power of analog quantum simulators. On the other hand, it is widely accepted that this class naturally captures the power of universal quantum computers, and this matters a lot.
The case for error correction is crucial. If we can do error correction we know that we can do polynomially long quantum computations in the presence of noise due to the celebrated threshold theorem. However, if a quantum computation is not fault tolerant errors will accumulate and turn your (polynomially long) computation into garbage. Therefore, I think it is unnatural to assume that you can perform polynomially long quantum computations in a non fault tolerant way.
Yet, presently, many people often conceive analog quantum simulators as one-purpose quantum computers that do not do error correction. (Or, at least, in many talks, people seem not to be looking at that.) This definition is rather vague and it does not immediately define a computational modeL: to be rigorous we would need to specify what type of Hamiltonians we allow and what are our models of noise, dissipation, etc. Regardless of these details, we should still regard any model of this kind as a non-fault tolerant model of quantum computation. Therefore, it seems hard to argue that BQP is the natural complexity class associated to this model. Yet, it seems natural to expect that these machines could perform at least constant-depth quantum computations, since they error propagation is mitigated so badly in low-depth computations. However, the computational complexity of constant-depth quantum circuits is not very well understood. There is some evidence suggesting that such circuits might have super-classical features.
Last, I should say clarify that many people are not trying to build analog quantum simulators just to have ``crappier quantum computers''. I think the motivation usually is to have testbed systems to study physical properties of complex many-body quantum systems. In many situations, people would just like to have a machine to some intuition on whether one had got the right Hamiltonian that describes a system, measure properties of phases and things like that. So, my point is, I do not think people are not proposing to use them as replacements of quantum computers. And, if that is not your goal, it is not that important whether they can solve all problems in BQP.
This post imported from StackExchange Physics at 2014-06-11 15:01 (UCT), posted by SE-user Juan Bermejo Vega
Q&A (4871)
