It's funny you bring this up, because I am in this course with Scott right now.

Note that the issue is whether quantum states are physically real, in which case the fact that you exploit canceling amplitude of quantum states in Shor's algorithm would be evidence of many worlds in the sense of many neatly factorizing amplitude blobs. None of this cares whatsoever whether quantum computing is more powerful than classical computing, only about how it is doing the computation. Also, bounded error quantum algorithms pose another issue, since the outcome can be viewed statistically (which the linked paper casts into doubt).

We just had a sequence of classes on quantum computation and posted several interesting debates to our course blog. In particular, the paper I linked above was posted in the comments thread for our discussion about whether quantum computing can or cannot offer insight in the debate over interpretations.

Look here for the blog post about Many Worlds and look here for the new posts about quantum computing and closed timelike curves.

My username in those discussions is 'bobthebayesian' and I would welcome criticism of my ideas if it is constructive and helps me update to better understanding. However, I think Scott wants us to keep the blog mostly for students in the class and with few or no posts from outsiders.

For what it's worth, Scott presents great challenges for Many Worlds that do not suffer from the usual shock level paranoia that most people have when the hear about it. He has no problem believing the trippy / weird consequences of Many Worlds. He said it well as follows on that class blog:

As I see it, the question then is whether we should be satisfied with MWI’s clear advantages in simplicity and elegance, or whether we should continue to search for a less “trippy” explanation. (After all, there are many simple, elegant theories whose “only” flaw is their failure to account for various aspects of our experience!)

I think the paper linked in the OP gives more reason to be satisfied with the simplicity of Many Worlds, beyond Bell's theorem.

Also, if we want an argument from authority, Hawking, Feynman, Deutsch, and Weinberg all side with Many-Worlds. Yes, they have some nuanced beliefs.. Weinberg said it interestingly when he said Many Worlds is "like democracy... terrible except for the alternatives." I don't think that this (nor Aaronson's agnosticism towards MWI) "proves" anything other than that it is a difficult problem. I, for one, do not share Deutsch's view that MWI is straightforwardly obvious, especially not when you consider all the issues in trying to understand why we see the Born probabilities instead of something else (see here).

I do think that it is straightforward that we should not postulate "measurement" as an ontologically basic thing, though. And this is why MWI is the best theory we have so far. (Bohmian mechanics would be worth consideration if it weren't for predictions that don't agree with experiment and the inherent underdetermination problem that it suffers.)