Well, there still is an unspecific and vague line between 'quantum' and 'classical' objects, entanglement is hard to understand and there isn't even a metric for more than simplest cases, and quantum systems appear to evolve in ways which classical computers cannot (it is believed) even approximate quickly enough. So it's likely that there's some fundamental complexity there...