alt Hacker NewsIn 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.
Does access to arbitrary parallel universes imply that they divide up the computation and the correct answer is distributed to all of the universes or in such a collection, there will be sucker universes which will always receive wrong answers ?