LW - A computational complexity argument for many worlds by jessicata

Link to original article

Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: A computational complexity argument for many worlds, published by jessicata on August 15, 2024 on LessWrong.
The following is an argument for a weak form of the many-worlds hypothesis. The weak form I mean is that there are many observers in different branches of the wave function. The other branches "actually exist" for anthropic purposes; some observers are observing them.
I've written before about difficulties with deriving discrete branches and observers from the Schrödinger equation; I'm ignoring this difficulty for now, instead assuming the existence of a many-worlds theory that specifies discrete branches and observers somehow.
To be clear, I'm not confident in the conclusion; it rests on some assumptions. In general, physics theories throughout history have not been completely correct. It would not surprise me if a superintelligence would consider many-worlds to be a false theory. Rather, I am drawing implications from currently largely accepted physics and computational complexity theory, and plausible anthropic assumptions.
First assumption: P != BQP. That is, there are some decision problems that cannot be decided in polynomial time by a classical computer but can be decided in polynomial time by an idealized quantum computer. This is generally accepted (RSA security depends on it) but not proven. This leaves open the possibility that the classically hardest BQP problems are only slightly harder than polynomial time.
Currently, it is known that factorizing a b-bit integer can be done in roughly O(exp(cb1/3)) time where c is a constant greater than 1, while it can be done in polynomial time on an idealized quantum computer. I want to make an assumption that there are decision problems in BQP whose running time is "fast-growing", and I would consider O(exp(cb1/3)) "fast-growing" in this context despite not being truly exponential time.
For example, a billion-bit number would require at least exp(1000) time to factorize with known classical methods, which is a sufficiently huge number for the purposes of this post.
Second assumption: The universe supports BQP computation in polynomial physical resources and clock time. That is, it's actually possible to build a quantum computer and solve BQP problems in polynomial clock time with polynomial physical resources (space, matter, energy, etc). This is implied by currently accepted quantum theories (up to a reasonably high limit of how big a quantum computer can be).
Third assumption: A "computational density anthropic prior", combining SIA with a speed prior, is a good prior over observations for anthropic purposes. As background, SIA stands for "self-indicating assumption" and SSA stands for "self-sampling assumption"; I'll assume familiarity with these theories, specified by Bostrom. According to SIA, all else being equal, universes that have more observers are more likely.
Both SSA and SIA accept that universes with no observers are never observed, but only SIA accepts that universes with more observers are in general more likely. Note that SSA and SIA tend to converge in large universes (that is, in a big universe or multiverse with many observers, you're more likely to observe parts of the universe/multiverse with more observers, because of sampling).
The speed prior implies that, all else being equal, universes that are more efficient to simulate (on some reference machine) are more likely. A rough argument for this is that in a big universe, many computations are run, and cheap computations are run more often, generating more observers.
The computational density anthropic prior combines SIA with a speed prior, and says that we are proportionally more likely to observe universes that have a high ratio of observer-moments to required computation time.
We could imagine aliens simulating many universes in paral...