Jan 18, 2020
Simulating the Monty Hall Problem on a Quantum Computer
Quantum computing is thought to bring advantages in many fields like chemistry, cryptography, optimization and more. But one of the most important traits of QC available today is true randomness. This makes it an ideal way to study problems related to probability and statistics.
Let’s use quantum computation to tackle one of the most debated probability problems: the Monty Hall problem.
The Monty Hall Problem
This problem gets it name from the host of the popular game-show “Let’s Make a Deal”. In the show the contestant is presented with three doors: door no. 1, door no. 2 and door no. 3. Behind one of them there is a new car. Behind each of the other two there is a goat. The contestant must choose a door. If he chooses the door with the car he wins the car. If not he gets nothing. So the contestant chooses a door where he thinks he will find the car. But then Monty, the host of the show, opens one of the loosing doors (this cannot be the chosen door) to reveal a goat. So now there are only two closed doors remaining and Monty gives the contestant a chance to change his choice. The question is: Should the contestant stick to his original choice, should he switch his choice or maybe it doesn’t matter?
The counter-intuitive answer, as popularized by Marilyn vos Savant in her column “Ask Marilyn”, is that switching the choice will double the contestant’s chances to win. In other words if he sticks to his original choice he has 1/3 chances of winning and if he switches he has 2/3 chances.
Let me say that again: You should always switch the door when Monty gives you the chance. This will double your chances of winning.
Now this is a concept that is hard to grasp for most people (hence the debate). There is a mathematical explanation in terms of probabilities, but I’m not going to expose it here. People have done simulations of this problem in many forms. You can watch some being done on YouTube.
Let’s try to use a quantum computer (or a quantum simulator) to test out this theory.
Simulation setup
We will use three qubits to represent the doors. We initialize the qubits in an entangled superposition in which only one of them is state |1⟩ and the others are |0⟩: 1/√3(|100⟩ + |010⟩ + |001⟩). The qubit in state |1⟩ represents the wining door. In this way we have a superposition of all possibilities of setting the winning door. For example the state 1/√3|001⟩ means that the car is behind door number three. The probability of that happening is the square of the amplitude which is 1/3. This is what we expect. The set of gates uses to achieve this superposition is shown in the image, along with the probabilities of measuring each state.
In the same way we represent the contestant’s initial choice. We have a superposition of three qubits were one is in state |1⟩ and the other two in state |0⟩. 1/√3(|100⟩ + |010⟩ + |001⟩). The qubit in state |1⟩ represents the door chosen initially by the contestant. For example the term 1/√3|010⟩ means the contestant chose door number two. The probability of each choice is also 1/3.
With this setup we can run our first experiment. We have 6 qubits — 3 for the doors and 3 for the choice. We set the winning door at random and the choice at random. We perform a set of measurements and collect the results. After that we have a post processing step, done classically, in which we compare the bits representing the choice to the ones representing the winning door. If they match we count the measurement as a win, if not we count it as a loose. See below the results.
In the random case the probability of winning is 1/3.
The “Monty qubit”
We use an additional qubit to represent Monty. Or more exactly Monty’s decision of what door to open. We must take into account the following rules
1. After the contestant’s initial choice, Monty will always open a door.
2. The opened door is never the winning door.
3. The opened door is never the chosen door.
Here’s how we encode Monty’s decision in the state of this qubit.
- If the state of the qubit is |1⟩ then Monty opens the door immediately to the right of the chosen door. I.e. If the contestant chose door 1 then Monty opens door 2; if they chose door 2 he opens door 3; if they chose door 3 he opens door 1
- If the state of the qubit is |0⟩ then Monty opens the door immediately to the left of the chosen door. I.e. If the contestant chose door 1 then Monty opens door 3; if they chose door 2 he opens door 1; if they chose door 3 he opens door 2.
In setting the state of the “Monty qubit”, we need to take into consideration the chosen door and the winning door. If the chosen door matches the winning door then Monty can decide to open any of the other two doors. This means we set the Monty qubit to an equal superposition of |0⟩ and |1⟩ by applying a Hadamard gate.If the winning door and the chosen door don’t match then Monty does not have a choice and can only open the remaining door, the one that is neither chosen nor the winner.If the winning door is to the right of the chosen one, then Monty must open the door to the left of it. This means we leave the qubit on the |0⟩ state (we do nothing). If the winning door is to the left of the one chosen by the contestant, then Monty must open the one to the right if it. In this case we set the qubit in the |1⟩ state by applying an X gate.
One thing to note here is that Qiskit doesn’t have a Hadamard gate controlled by two qubits so I made one using two Ry gates and a Toffoli gate.
Running this circuit will yield the same result as the random choice experiment because we haven’t change the doors or the contestant’s choice.
Switching the contestant’s choice
Okay. So now we are close to the finish. We have simulated the doors, the contestant’s initial choice and Monty opening one loosing door. We only have to simulate the last decision of the contestant. What happens if he switches to the other closed door.
To do that we use a small sequence of gates that permutates the choice to the right. Meaning |100⟩ becomes |010⟩, |010⟩ becomes |001⟩ and |001⟩ becomes |100⟩. Notice that to shift the choice to the left all we need to do is apply this sequence twice. If we do that |100⟩ becomes |001⟩ and so on.
Switching the choice depends on the Monty qubit. If the host of the show opened the door to the left of the initial choice (i.e. the Monty qubit is |0⟩) we need to permute our initial choice to the right by applying our gate sequence once. If the Monty qubit is |1⟩ then the show host has opened the door to the right of the initial choice, so we need to permute to the left and we do this by applying our gate sequence twice.
Now we have implemented everything in our circuit and are ready for the final simulation.
You can immediately see from the measurements that the qubit strings in which the choice (after change) matches the wining door were measured more times than the others.
This is great! We have proved Marilyn vos Savant was right. Switching your choice will double your chance to win. But we’ve done a lot more than that. We’ve shown how powerful quantum computation can be. We’ve done all this with just 7 qubits. And we only used a few quantum gates. This shows how intuitive we can make statistical problems using quantum computation and how close this reasoning can be to our intuition about how statistical problems should be implemented.
We can think of this implementation in two ways. For one we can think that we used something that is inherently probabilistic — a set of qubits — and that we encoded our probability problem in them. At the end we just “rolled” the probability dice a few times to get the result — the real final probability.
On the other hand we can think of the quantum computer as performing operations on all possible states at the same time. Indeed we have only 7 qubits but we represent with them more than 7 states. We set the qubits in a superposition that is made of multiple states — all possibilities — at the same time and we perform operations on it. It’s only at the time of measurement that the superposition “collapses” to a single definite state.
You can find the entire code here.
[1] https://www.statisticshowto.datasciencecentral.com/probability-and-statistics/monty-hall-problem/
