[pastelsky]

If I understand correctly, the limited amount of "expressiveness" a quantum computer has restricts its ability to solve useful problems.

Couldn't you simply express useful problems as a function of problems that the quantum computer can already solve? Doing so might be extremely in-efficient, but give that there's so much performance leeway, it still might end up being similar to super computers of today?