Disagreeing again with the "Ansible is unrealistic" view: I agree it's unrealistic in a global sense, I just think all of its unrealism comes from the use of FTL in the backend. FTL + relativity produces timetravel, yes. I just think it's implausible to expect a physical universe to first provision the mechanics for FTL, then provision a system that gives you timetravel when exposed to FTL, and then very carefully separate those two systems so that they computationally never touch, even though in theory they could! and so in a sense, this physical theory implies that this universe has to be prepared, in principle, to allow time travel and account for it, and having gained this capability has elected to specifically not use it. It just stinks of a massive Occam violation - the potential for time travel is an "entity without necessity", and the theory is bloated by it twice over; once by its inclusion in the physical logic and once again by the additional exclusion mechanism that makes it unusable in every reachable state. And so the ansible universe pays slightly less cost just by leaving out the global censor.
Am I saying "no correct theory can look like this"? No! I am saying it enters the race with a huge handicap.
My understanding is that that is a yes - with a quantum computer, quantum simulations [are expected to] run in linear time instead of the current exponential time.
Then you give me two numbers a and b (with some technical constraints) and ask me whether the ground state energy of H is between a and b.
This problem is QMA-complete as long as k >= 2, and known to be QMA-hard even for some pretty nice looking Hamiltonians. Here QMA stands for Quantum Merlin-Arthur which is the complexity class equivalent to MA (Merlin-Arthur) for classical computers. You can think of MA as being related to BPP in the same way that NP is related to P, and this is the same way that QMA is related to BQP.
Basically QMA problems are not expected to be solved efficiently by a quantum computer.
The current consensus (at least among people I speak to) is that a quantum computer will probably be able to solve some problems which are in NP (and not in P), but will probably not be able to solve an NP-hard problem.
Your intuitive view is appealing, but I don't think one should get too hung up on intuition. Our intuition was honed for millions of years to avoid large wild animals and avoid falling out of trees in prehistoric Africa. It generally sucks pretty badly at making guesses about the fundamental nature of the universe (or at least mine does).
Edit: by the way a faster than light communication "ansible" is functionally equivalent to a machine that sends messages back in time. I disagree with your view that such a machine is more plausible than the view that some ftl stuff happens on the "backend" but is hidden from the "frontend". Having said that my view is that there is no ftl stuff on the back or front end, this is consistent with something like the many worlds interpretation of quantum mechanics, which is entirely local and causal (no ftl stuff).