# Quantum Darwinism & application to Algorithmic Complexity

WARNING: This is a joke…

## What is Quantum Darwinism?

It may already be a thing but I haven’t been bothered to google it - so if it is, I’m redefining it.

### Everett’s Many Worlds

In order to understand Quantum Darwinism, or at least my definition, you must first understand the many worlds interpretation of quantum mechanics. This was an idea proposed by Hugh Everett and the idea is somewhat simple. Each time there is a probabilistic decision to be made on a quantum level, the universe forks (yes, in the git sense) and all possible ways in which the quantum event could have taken place run in separate worlds. This is a great way of explaining the seemingly random quirks of quantum theory but it doesn’t seem to have much application to the real world… or does it?

### Quantum Darwinism

Charles Darwin formulated a theory of evolution, where traits that helped an organism reproduce would result in more of those traits in the whole population down the line. The best would reproduce more, the weak would die out. What if we applied this to possible worlds? The best would be able to fork into more worlds, the bad ones would die out. Maybe, there is a possible world without Trump? Maybe there is a possible world where politicians worked together across borders to solve global warming? If these events were decided on a quantum level, then according to Everett’s theory, there would be a possible world far better than our own. So surely we should just destroy this one, seeing as there are better ones that we are already living in? But what about all the death and destruction? Yes, that is a problem if you think about it that way, but if you consider how many quantum decisions there have been in your lifetime; then you realise that there are far far far more of you surviving, the only noticeable change is that this awful world is not left to fork into more awful worlds. But we can’t be sure that these political decisions were predicated on quantum decisions, and even if they were, they could have been so long ago that we would lose the recent traits of this world that we actually like and would want to fork. Is there another application?

## Quantum Darwinism & Algorithmic Complexity

### Algorithmic Complexity

There is a small chance that you are here because of the Quantum Physics in the title, the philosophy, the joke or simply because I asked you to proofread this page for me. In which case, you may have very little or no experience with programming or algorithmic complexity. So let me quickly fill you in.

Consider the following code.

int main() {
int n = N;
for(int i = 0; i < n; i++)
printf("Hello World");
return 0;
}


main is our main function; we set n to N, we then write onto the screen (printf) Hello world n times. N could be any number we want (that is an integer). In computer science, we would say that this code is $O(n)$ with respect to time, where, confusingly, $n$ is N (the size of our input). This means that if we were to times N by some number $p$, the amount of time the program would take to run would also be multiplied by $p$. Now, we change the second line to int n = N*N; making the program $O(n^2)$ because when we times N by $p$, the program would take $p^2$ times longer to run. This is known as time complexity, and in computer science, much time and effort is put into coming up with code with better algorithmic complexity than the last way. This is because if, say I have two algorithms, $A_1$ is $O(n)$ and $A_2$ is $O(2^n)$, each time I increase $n$ by 1, $A_2$ will take twice as long! Consider the case where when we have an input size of $20$, both algorithms take 1 min to complete. Maybe this algorithm takes the names of children in a year group at school and sorts them into classes based on certain preferences? What if I increase the input size to 70? Maybe I don’t need to organise my year group at school into classes, but all year groups into forms that cross year groups? $A_1$ will take 3.5 minutes… not bad… $A_2$, on the other hand, will take about 1125899906842624 mins… or in other words, around 18765000000000 hours, or 1781875000000 days, or 2140660000 years…

### The application of Quantum Darwinism

Sadly, there are some problems which no one has worked out how to simplify (with respect to time) on conventional computers, and others can’t even be simplified on unconventional computers! These unconventional computers don’t even exist yet and as a result we use data centers and data centers of classical computers all working together to solve things. This isn’t good for the environment and isn’t always possible! But the other day I read an article that showed that people have worked out how to use quantum affects to create a truly random number generator. People were going on about its applications to security etc and it just seemed all a bit boring for such a cool quantum device. Then it struck me! The quantum number generator exploits the fact that a quantum decision is made in order to get the random number, and thus splits the universe into many worlds each time it generates a random number. So consider this code:

int main() {
int rand = getQuantumNumber();
Form *forms = selectFormPermutation(rand);
if (incorrect(forms))
sys_destroyUniverse();
return forms;
}


This is an application that solves the form problem from earlier. It selects a random configuration of forms and if it’s a bad configuration, the universe is destroyed. If it is a correct configuration, it gives the answer back. Only universes with the correct solution survive to fork more universes, giving the illusion of guessing correctly each time. Assuming that it is very simple to create a random configuration and check it, it should run very fast, possibly in constant time (meaning the time it takes to run is independent of the size of the input). If the answer is wrong… well… you probably have other things on your mind than to care.

## Conclusion

What we have designed is an infinitely parallel search algorithm. We generate at least one universe for each possible answer to the problem and a single computer in each universe performs a check to see if its randomly allocated solution is correct. If it is, it outputs the answer, if not, the universe is destroyed! Anyone alive will just see the answer outputted on their screen as if nothing unusual has happened.

So, if you enjoyed and understood this, I will give you some more thoughts to ponder over:

1. What would an inter-universal race condition look like? Is one possible? Is the universe thread safe?
2. Could all universes be destroyed? (Would you make the same bug in all universes?)
3. If the universe was wiped out so quickly that no one felt it, is the plan ethical?
4. Come up with some quantumly darwinistic algorithms yourself!

James