Simulating the Many Worlds of Quantum Mechanics
Computers have become an essential part of the scientific process. They allow us to visualize and explore natural processes that would be costly or impossible in a physical laboratory. One fascinating topic of theoretical physics that is impossible to explore in a laboratory is the Many Worlds Interpretation (MWI) of Quantum Mechanics (QM). Why is it impossible to explore in the laboratory? Because the laboratory is only a subsystem of the Universe’s wave function, therefore, there is more to the quantum multiverse than can be directly measured! So, just as we try and put one physical world into a computer obeying the laws of classical physics we want to try and put many worlds into a computer and obey the laws of quantum physics.
Our goal is to better understand the MWI of QM using simulation, not an observable prediction of QM. For example, we would like to explore how worlds branch in the MWI not the spectra of the hydrogen atom. To put it more plainly, we simulate the details of an interpretation of QM instead of just calculating the predicted outcomes of QM using computers. In this post I will show you a way to simulate how worlds are created and evolve with qubits and quantum computing circuits using a new mathematical structure called a Quantum Multiverse Network (QuMvN) based on Information Theory. Along the way, we will explore details of the MWI interpretation that our simulations have uncovered and propose a couple solutions to long standing problems of the MWI such as the preferred basis problem and counting the number of worlds of a simple system.
An interesting note is that QuMvNs were developed to simulate Shor’s Algorithm, which they successfully did for 70 qubits on a modest cloud computer. The fact that the MWI popped out of the simulations was a pleasant surprise to us.
Brief overview of MWI
The MWI of Quantum Mechanics was first proposed by Everett in 1957. It has recently been popularized by Sean Caroll in Something Deeply Hidden and science fiction works such as Man In The High Castle. In QM, our mathematical description of nature can give multiple answers to a question. Each answer can be observed by an observer with a certain probability. The strange thing is that once we observe an answer, the multiplicity goes away (the so called “collapse” of the wave function). Various explanations exist trying to make sense of this peculiar problem of multiplicity in QM. The MWI explains this multiplicity by taking the multiplicity literally and equating them to different worlds in our description of reality. There is not one observer and many possible outcomes, there are many observers who’s only difference is the outcome they observe.
The most famous thought experiment that tries to emphasize this multiplicity is Schrodinger’s Cat. Suppose there is a closed box. In this box there is a quantum device that releases poison. Since it is a quantum device, the question “was the poison released?” has a multiplicity of answers. The poison is released with some probability and not released with another probability. In the MWI, the source world branches into two different worlds. In one world the poison was released, and the cat is dead. In the other world the poison was not released, and the cat is alive. When the observer opens the box, he knows what world he is in by looking at the state of the cat. If he continues to look at the cat, it is always in the same state because he is observing the cat in his world, the multiplicity is gone with respect to a single observer. Notice that there are two observers, two worlds and two cats in different states. This is the heart of the MWI. For a more complete description I highly recommend Caroll and Wallace.
Multiplicity with Quantum Multiverse Networks
Schrodinger’s Cat is a historic thought experiment, but there is no reason to think in terms of cats. Instead of cats and a quantum poison device, we will explore and simulate the MWI using bits in a quantum computing device. Classical bits in classical devices can represent a 0 or 1 in one world (the classical world we all know). Quantum bits in quantum computers (qubits) represent the multiplicity of QM by allowing the bit to be 0 in one world and 1 in another world. When the programmer asks: “what is the value of the bi?”, the answer depends on which world the bit is in! This is precisely what we want to simulate, we want to explore how qubits interact and visualize qubits in different worlds and we do this by a classical simulation of qubits.
We can use classical computers to simulate QM, qubits and quantum computers it just doesn’t scale. That is why we need the largest supercomputers ever built to study small quantum circuits. Traditionally, qubits have been simulated by using a vector (array) and quantum circuits by matrices. A quantum computation is simulated by multiplying the vector by the matrices and recording the outcome. The problem is this: if you have n qubits then you need an array of size 2^n and matrices the size of 2^n x 2^n. You can see that this gets out of hand with even small n (say 20). However, if we can rethink the way we do our simulations we can increase the ability of classical computers to simulate quantum computers and explore the MWI in more detail. That is precisely what we have done with Quantum Multiverse Networks (QuMvNs). Think of QuMvNs as a different data structure to represent quantum states (not a simple array) with different algorithms to accomplish quantum computation that are not matrix multiplications.
The first thing we must think about when designing a new method for quantum simulation is how to handle multiplicity. In the MWI multiplicity leads to different worlds, but that should only be for quantum multiplicity. We also have classical multiplicity. For example, if we flip a coin there are two possible outcomes: heads (0) and tails (1). We even assign a probability of 50% to getting a 0 and 50% to getting a 1. The biggest mistake I see people make when trying to reason about the MWI without large scale computer simulations is assuming we need a world for each possible outcome of the system. For example, if a system is described with 50 qubits then there are up to 2⁵⁰ possible bit strings we can observe. If this is a quantum system, then they naïvely say we need 2⁵⁰ worlds to represent the quantum system. We argue this is not completely accurate because what happens during a quantum circuit when there is no observer between the initial state of the circuit and the final measurement? If we have a classical system consisting of 50 bits why don’t we need 2⁵⁰ worlds?
The measurement problem and collapse of the wave function is not enough to answer this question. We can write superpositions of classical systems just as easily. Shannon does this in his famous paper A Mathematical Theory of Communication (section 5, top of page 10) where he considers a superposition of information sources, “mixed sources”, where we first choose an information source with some probability and then generate a message from the information source with another probability. If you stay on the same information source and don’t re-choose then the message is the same. Nobody says that the information source collapses or that we need multiple worlds do describe this process. Also, the MWI creates new worlds during measurement because the measuring device (and observer) become entangled with the system. However, in our simulations we want to see what is happening before the measurement as well. If we wanted to simulate the cat in the box, how many worlds do we need before we measure? We need to know the difference between classical multiplicity and quantum multiplicity if we want to simulate it.
So how do we distinguish between classical multiplicity and quantum multiplicity? Using QuMvNs we found a simple answer: if you only need A SINGLE world to represent your qubits then it is classical otherwise it is quantum. Wait a minute! You may exclaim. How do we know we need more than one world? The answer we got from simulating with QuMvNs is ENTANGLEMENT. When there is any entanglement between any two qubits in any world, they cannot be represented with A SINGLE WORLD. Therefore, the multiplicity is a quantum multiplicity. If there is NO ENTANGLEMENT between any qubits, then the multiplicity can be represented with one world and we have a classical multiplicity. Entanglement creates worlds, even if no measurement is happening at the time.
From our simulations, we find that the quantum state becomes a sum of multiple worlds, but each world can have classical multiplicity. If the multiplicity of the system only requires one world, then QuMvNs can efficiently simulate the system on a classical computer. Two worlds cannot be combined if entanglement exists between any two qubits. Since entanglement is basis independent, our method may be a solution to the preferred basis problem. The fact that you only need multiple worlds when entanglement is present is also very encouraging, since what creates the uniquely quantum effect of many worlds is the uniquely quantum effect of entanglement and we can show that from first principles using QuMvNs and information theory.
Let’s see how this single world multiplicity works with QuMvNs which is a new data structure to represent qubits and a set of algorithms to simulate quantum circuits. The underlying mathematical structure of a QuMvN is a Multiplex Network. Multiplex Networks are a set of graphs (aka networks) which have the same set of nodes but can have different edges connecting those nodes. Each individual network is said to be in a separate “Layer”. In the QuMvN data structure a layer is used to represent a world in the MWI, and the set of all layers is all the possible worlds of the QuMvN. By performing a random walk on the network, we obtain a possible measurement outcome. By performing multiple random walks on the network, we obtain a probability distribution that matches the probability distribution expected from the wave function. If there are multiple worlds, the first step of the walk is to choose a world according to the world credence (which is explained below).
Let’s do a simplified example making all possibilities have equal probability, let |X> be the bit string 00, and |Y> be the bit string 10. Then we have |Q> = .707|00> + .707|10>. There is a 50% chance of getting |00> and a 50% chance of getting |10>. There are two possible outcomes when you measure, but do you need two worlds? The answer is no! Only one world is required. How do I know? I know because I can represent this |Q> with a single layer in a QuMvN data structure and simulate it efficiently on a classical computer (Figure 1). There are many more examples of single world QuMvNs and how edge weights correspond to probability amplitudes in our paper.
A single layer of a QuMvN for qubit systems can be represented by a directed acyclic graph Q = {V, E} where V, E are the set of vertices and edges respectively. The vertices V represent the degrees of freedom of the system and are labeled by an alphabet A. Therefore, for qubits we have two vertices labeled from the alphabet A = {0, 1} per qubit. The edges have a weight ∈ C and represent the probability amplitude of the destination vertex given the source vertex. Now Imagine you are walking this graph, you start from the root and go either left or right, then you keep walking until there is nowhere to go. At each step you look at the edge weight to your left and square it, that is the probability of going left (0). So, just generate a random number between [0.0, 1.0], if that random number <= probability of going left, go left, otherwise go right (1). This will produce various bit string with certain probabilities.
The reason we only need one world for the above state is because we can “factor” the state and write it as a product. For example, .707(|00> + |10>) = [.707|0> + .707|1>] X |0>. Just perform that “multiplication”. To be precise, if a state |Q> can be written as a single tensor product then you only need a single world and can classically simulate it with a single layer QuMvN. Most states |Q> cannot be written nicely as a product. There is a definition for states that cannot be written as a product: entangled states. Entanglement is exotic and uniquely quantum mechanical, but at the heart of it, it is really a simple property. If a state cannot be factored and represented in a single layer network QuMvN then it is entangled. That’s it. If entanglement is present in a state |Q>, then you must represent it with multiple network layers in a QuMvN, therefore, different worlds in the MWI. Each world has states that can be factored, and then you sum the possibilities in each world to get all possibilities.
One of the main results of QuMvNs is that the quantum state becomes a sum of multiple worlds, but each world can have classical multiplicity. Each world is a subsystem that can be written in a factored form, and adding these worlds together gives us a sum of subsystems that can be factored. Since factorization is the mathematical definition of entanglement, we say that we write the quantum state as a sum of unentangled subsystems. One crucial aspect that our simulations show is that in order to get the correct results, these subsystems cannot share any states. For example, if we have 3 worlds and the state |00110> is a possibility in world 1, then it cannot be a possibility in the other two worlds. What we are describing is a “tensor decomposition” in multilinear algebra. Therefore, we do not need a world for every possibility allowed by the quantum state, we only need a world for each term in the term in the tensor decomposition.
The rank of the tensor decomposition is the number of worlds required to simulate the circuit.
Let’s look at an example that has two worlds because of entanglement. The quantum circuit below:
will generate the state |Q> = 0.5(|0000> + |0111> + |1000> + |1111>) which cannot be represent with one world because of entanglement between qubits 3 and 4. The state |Q> requires two layers (Figure 3) in a QuMvN and therefore two worlds. We can see this in the factorization of |Q> =0.5 (|0> + |1>) X |000> + 0.5(|0> +|1>) X |111>. What created the extra layer in our quantum circuit? It was the CNOT gates which makes a lot of sense. Think about the CNOT gate for a second, it takes two qubits as arguments: the control qubit and target qubit. It says: if the control qubit is 1 then apply X to the target qubit. However, the “if” clause is not a classical if! What happens in the MWI interpretation when you do an if? In one world the control qubit is |0> and in another world the control qubit is |1>. Therefore, if after applying the X gate to the target qubit the two qubits become entangled, then we branch into two separate worlds. Otherwise, they remain as one world represented by classical multiplicity.
We developed entanglement detection algorithms for this purpose that we will save for another post.
It is at the CNOT step where probabilities of worlds (credence) are established. Noticed in the circuit above that we had an uncertainty the control qubit (qubit 2) and no uncertainty in the worlds. In the beginning there is only one world with probability 1. After the CNOT gate is applied, the single world branches into two worlds. The probability of world 1 is the probability that qubit 2 = |0> and the probability of world 2 is the probability of qubit 2 = |1>. However, if we happen to know what world we are in, then we know the value of qubit 2 with certainty. The CNOT gate, and the branching process removes uncertainty from the qubit and puts that uncertainty in the worlds. This is how the probability of worlds is established in the MWI using QuMvNs.
Multiplicity and the preferred basis problem
One of the largest problems for the MWI is the preferred basis problem. Notice, this whole time we have been using |0> and |1> as our “bit strings”. Therefore, we are in the|0>/|1> basis. Similarly to how classical computing can have Hexadecimal and Octal strings instead of bit strings, quantum computing can have a different basis. The most well-known is the Hadamard Basis (HB). In the HB, instead of |0> / |1> we have |+> / |->. There are relationships between the basis (much like there are formulas from going to Hexadecimal from base 2 bits). For the HB,
|+> = .707|0> + .707|1> and |-> = .707|0> — .707|1>.
Notice that |0> = .707|+> + .707|-> and |+> = .707|0> + .707|1> which means we can be in a superposition in one basis, but not in a superposition in another basis. If we naively say that each possible outcome requires a new world, how do we account for a different number of worlds required depending on our basis?! This makes our theory basis dependent. Since a basis is a human construct that can change, having a basis dependent theory is problematic because by changing the basis we can make worlds appear or disappear! For me (and probably many other physicists) this was a clear no-go for the MWI. However, by trying to simulate the branching process we pretty much found a solution to this problem: entanglement.
In the QuMvN formalism, we need a separate world only when there is entanglement, not just any superposition. So, for the wave function
|q> = .707(|0> + |1>)
we only need one world not two. In the HB |q> = |+> which again only requires one world. The state
|Q> = 0.5(|0000> + |0111> + |1000> + |1111>)
requires two worlds. In the HB,
|Q> = 0.5(|++++> + |++- ->+ |+-+-> + |+- -+>)
again only two worlds. Another classic example is the bell state
|Bell> = .707|00> + .707|11>
|Bell> requires two worlds due to entanglement. When switching to the HB |Bell> = .707|++> + .707|- ->, again requiring two worlds due to entanglement.
The examples go on and on, but the point is that using the QuMvN formalism the number of worlds is basis independent. QuMvNs are basis independent because we only need separate worlds to handle entanglement and entanglement is basis independent! Thus, we seem to be able to solve the preferred basis problem by leveraging the properties of entanglement. More work remains to be done to explore this solution and verify it, but we believe we have put the analysis on a firm mathematical footing using QuMvNs and we do not have to invoke philosophical arguments such as “worlds are an emergent subjective property”.
Counting Worlds
Another related thorny issue in the MWI is how many worlds are there? This question usually becomes too open ended and the people arguing usually start talking about the total number of worlds in the universe. But I’m a practitioner, I don’t care how many worlds there are in the universe. What I care about is this: Given a simple system (not the entire universe) how many worlds are required by the MWI? We should be able to answer this simple question for a simple system. For example, a two-qubit system is a simple system. Suppose I give you the wave function
|q1> = 0.5(|00> + |01> + |10> + |11>)
how many worlds are needed for this wave function?
The naive answer is four, one world for every possibility. However, the QuMvN answer is one world! That is correct, just one world because the |q1> can be written as one tensor product:
|q1> = .707(|0>+|1>) X .707(|0>+|1>)
There is no sum of tensor product therefore only one world is required (We say that the rank of the tensor decomposition is 1). If we naively assumed one world for every possibility, then the preferred basis problem would have been quite extreme. In the HB the wave function |q1> = |++> with no multiplicity!! If |q1> required 4 worlds in the |0>/|1> basis, where do those worlds go when we switch to the HB basis? QuMvNs give us a clear answer, because there is no entanglement, only one world is required for any basis and any multiplicity is a classical multiplicity not quantum.
The number of worlds is the rank of polyadic tensor decomposition.
One issue you may have with the QuMvN approach is: how do you know which states to put in which worlds? We do not have a clear answer for this yet, but what we do have is a postulate that guides our research:
“The time evolution of a quantum system minimizes the number of worlds”
Therefore, we arrange states in layers in a way that minimizes the number of worlds. This is a postulate, and the next round of research in QuMvNs will be calculating all the consequences of this postulate. The current state of our research is using methods of layer aggregation in multiplex networks to get a minimum number of worlds given a wave function. Once we have that published, we will go on to study the time evolution of the number of layers in a dynamical system and see what equation we come up with. We think QuMvNs give us an exciting new framework to study quantum mechanics, quantum computing and details of the MWI of quantum theory.
Exciting times!
Epilogue: Origin of QuMvNs
When I first started exploring quantum computation, I didn’t expect to run into the Many Worlds Interpretation (MWI) of quantum foundations. I just wanted to simulate quantum circuits on a classical computer using a different algorithm that could potentially scale much better than matrix mechanics. I developed a network theoretic approach that was first applied to unentangled systems with a single network. The MWI was the last thing on my mind. However, with a single network I was not able to simulate control gates (CNOT) in a coherent way. My original solution was decohering, much like the actual hardware problems.
The big push forward was realizing that to simulate coherent control gates we had NO CHOICE BUT TO BRANCH INTO SEPARATE NETWORKS. This branching mechanism also gave a clear answer to what the probability of each separate network (or world) should be. When I literally saw this branching process in the simulations and visualizations my eyes widened, and I was struck with awe. I didn’t assume the MWI, quite the contrary, I was just taking a graph theoretic, computer science approach to simulating quantum circuits. From the first principles computational approach I saw the MWI “pop out” of the simulations. Not only did I see the world starting to branch, but it made reasoning about quantum circuits simpler. The MWI helped me refactor code, drastically reducing the size of my code and increasing code quality. A purely theoretical interpretation in the foundations of quantum physics had a direct impact on my very practical software. This amazes me every time I think about it and I just wanted to share this experience. Hopefully, this shows the importance of teaching quantum foundations to students. Don’t just shut up and calculate, sometimes we must try and understand what we are calculating.
