In the same way people believe P != NP, most quantum computing people believe BQP != NP, and NP-complete problems will still take exponential time on quantum computers. But if we had access to arbitrary parallel universes then presumably that shouldn't be an issue.

The success on the random (quantum) circuit problem is really a valdiation of Feynman's idea, not Deutsch: classical computers need 2^n bits to simulate n qubits, so we will need quantum computers to efficiently simulate quantum phenomena.