Landmark computer science proof cascades through physics and math
quantamagazine.org
quantamagazine.org
But then I found a series of questions and answers written by this quantum guy Scott Aaronson[2] and by this other quantum guy Kenneth Regan[3], who both know a bunch of quantum stuff. Each one of their blog posts makes me more certain about MIP* = RE, to the point that now I'm 99.9% sure it's true, even though I could never verify it myself.
[1] https://arxiv.org/abs/2001.04383
[2] https://www.scottaaronson.com/blog/?p=4512
[3] https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-ti...
From the new proof though, I'm certain that I can't put an upper or lower bound on the probability of whether they're right.
Be warned, this is 160 pages of dense math. To anyone complaining that the quanta article is "unclear" or not descriptive enough, there's no way around that when summarizing a dissertation.
There are a number of results about how measurements of an individual infinite-dimensional quantum system can be approximated to arbitrary degree by an arbitrarily large finite-dimensional system.
This new result seems to suggest that for joint entangled systems there's a "buffer" between measurement results obtained by having arbitrarily many dimensions, and by having infinite dimensions.
I was wondering how practical it could be to actually do an experiment and verify that the buffer line is crossed.
Infinitely small things (even infinitely small nothingness) is to me the relevant question as we may have it within our reach.
Infinitely large things are more of a perpetual argument that I don't know whether one can argue about physically (although mathematically one could try).
To me the difference between QM and relativity is exactly continuity. This is the key question.
So basically, we would still need a way to build an unboundedly-powerful pair of Q-computers that were entangled (whoops, forgot that part!) in order to get any direct application for this, then we'd have to actually write the software to run this series of communications the 3 computers exchange from the paper.
So, this is only useful for some unknown, future proof of something else, not to engineer a real-life system with.
https://www.youtube.com/watch?v=3s7h2MHQtxc
or skip directly to the conclusion;
Also these little ones:
https://news.ycombinator.com/item?id=22079048
https://news.ycombinator.com/item?id=22077591
I seem to recall others but can't find them. Anyone?
But then as you continue, you go deeper and deeper through the rabbit hole. Expertly guided through a series of analogies and examples through a complex subject until you arrive at an incredible payoff in perfectly understandable terms.
I won’t spoil the surprise. But it’ll just say I love how this proof works so, so much.
In the end it rests on the logic that if A then B but we know !B therefore !A. It proves that for something to be true, then something else which we know to be false would then have to be true. Therefore that something must not be true. I love it.
Edit: or maybe “the featured article”, either way derived from “RTFA”, “the fucking article”, which I assume derived from RTFM, of which many more I’m sure are familiar.
>> let’s imagine two players, Alice and Bob, and a 3-by-3 grid. A referee assigns Alice a row and tells her to enter a 0 or a 1 in each box so that the digits sum to an odd number. Bob gets a column and has to fill it out so that it sums to an even number. They win if they put the same number in the one place her row and his column overlap. They’re not allowed to communicate. Under normal circumstances, the best they can do is win 89% of the time.
Alice will set the combination 100 if she was assigned either the first or the second rows, and the 010 if she is assigned the last.
Now Bob knows how to win if he gets first column since 110 will always win, and knows how to win if he gets the last column, because 000 always wins.
When assigned the middle column though, he needs to choose between 101 and 011. He will win if Alice got last row no matter what, but the other two are a toss up.
He’ll get it right half of the time, so he will win for sure if row and column meet at 7/9 squares, and the other two he’ll win half of the time, thus 8/9.
I'm sure there is a basic piece I'm missing here.
a. What does this mean about Google's claim of quantum supremacy? [1] Does the new paper prove that quantum computers with entangled provers are more versatile than classical computers, because they can work in a larger problem space? Would that also mean that there is definitely such a thing as quantum supremacy, regardless of whether we've achieved it yet?
b. How does this affect CERN? That research institute is a melting pot of physicists, computer scientists, and mathematicians. This proof did not come from CERN, but I feel like CERN has the best resources to apply the proof. Need some entangled particles? Sure, let me just go downstairs to the LHC and pick up a few. Want to play a nonlocal game? Second door on your left. Need the Grid supercomputing network to verify your proof? You've got it. I hope that someone will be able to use this to reassure politicians that CERN is worth funding.
c. Does anyone know whether Tsirelson saw the proof (13 Jan) before he died (21 Jan), and what his reaction was?
I'm also really impressed at how Vidick & Ito, and Natarajan & Wright were working independently, and then joined forces to become a genius team. My gut feeling is that MIP* = RE is the E = MC^2 of quantum computing.
It does seem from the article that they use an argument that the halting problem is unsolvable to somehow give an upper bound on complexity, but I wonder if the paper really does that.
"the fact that the halting problem is unsolvable" This is less of a fact and more of a conjecture. As always in mathematics we use implicit context and sometimes that context gets lost to a damaging degree. The whole, and true, sentence would be "the fact that the halting problem is unsolvable by a turing machine and, given that the Church Turing thesis is true, unsolvable in general".
It would be a pitty if the paper simply assumes the Church Turing thesis as true, because if we ever find a hypercomputation counterexample to the CTT, it'll probably come from a place like quantum computing and physics, where there might be more reals than the computable reals, where the axiom of choice could work, and where infinity might be a reified thing instead of a process.
Is it even a theorem, such hand-wavy thing is a theorem boggles my mind.
In fact, computability theory sometimes strikes me as one of the most rigorous fields, and aren't all of the hand-wavy sounding words in Wikipedia's first paragraphs of Rice's Theorem for example, in reality very rigorously defined as well?
Are people okay with the word "non-trivial" ? Is it even quantifiable?
E.g. "returns 4 for some input" is a non-trivial property: the function 'f(x) = 4' satisfies it, while the function 'f(x) = 7' does not.
"MIP* = RE shows that, with quantum entanglement, there can be a chasm of computability between verifying solutions and finding them."
(Which is to say... humans aren’t more powerful — it’s that we’re so limited, we will never reach the domain for which the halting problem is relevant.)
Or did you mean something else?
if fermats_last_theorem_holds(x,y,z):
halt()
else:
infinite_loop()
It may be able to "trick my brain" but only because I don't have a PhD in mathematics. Obviously no general algorithm can solve this, or else said general algorithm would easily be able to solve all unanswered questions in mathematics, physics, etc. Yet, human mathematicians are able to determine whether my program above halts, even if a general algorithm can't.
But that's the point! The halting problem hides inside of it all of the complexity of math, including the dark tricky self-referential corners. Saying that you can solve the halting problem is tantamount to saying you've solved Godel incompleteness.
If you applied the halting proof diagonalization step to yourself (modeled as a machine built of out physics) you would find that it spit out something very complicated that ultimately amounted to a program equivalent of a statement of the form "The physics machine that I am cannot prove this statement". If you proved the statement then that would disprove it, which is the core of the problem.
In general, human answers to halting problems have no guarantees of soundness or completeness, and can't be guaranteed to be correct unless presented as some kind of proof in some kind of logic.
Then, if a human can use some logic system to guarantee that a particular program halts, then a turing machine could also trivially solve this problem, by simply enumerating and verifying the possible proofs of program in the logic system. This proof strategy has further benefits beyond ad-hoc human reasoning, in that it is guaranteed to eventually find the proof if it exists.
Here is my program:
def fool(input):
while input:
pass
That's the gist of the proof that the halting problem is unsolvable. Whatever the algorithm or method is used to answer the problem, you can take that method and "embed" it into the program to be verified, and invert the answer.
The halting program doesn't say you can't answer for many or even most programs and inputs, it just says there'll be at least one counter-example.
The real proof is a bit of a head scratcher. Imagine we created such a function, doesHalt, that can read any program's source code and always figure out if the program will halt. This program can solve the halting problem -- it always produces a solution, either a True or a False. Feed it your fool program, it can always solve it, for any arbitrary input.
So what happens if we run create this little head scratcher function, that takes no input:
def headScratcher():
if doesHalt(headScratcher):
while 1: pass
Assumptions in CS complexity theory:
1. Turing showed that you can't tell ahead of time if a program will run forever or eventually stop. This is the halting problem. It proves that some problems are impossible to solve with computers even with infinite memory and CPU.
2. But you can often verify if an answer to a problem is correct more easily than solving the problem itself.
3. But some problems are so difficult that even verifying if an answer is correct is seemingly impossible - like verifying some properties of an infinite graph of nodes. This is because the graph could be infinitely large, so you could never have enough memory in your computer to even number the nodes, let alone inspect them.
4. Sometimes if you can't verify the solution with your own computer, you can use your computer to interrogate a more power computer to indirectly verify it. You ask inter-related questions that are easy to verify to the more power computer (called the "prover") about it's solution. If you get consistent answers back more frequently then chance, you can assume the entire solution is correct.
5. Going even further, you could have two 'prover' computers and ask inter-related questions to both about the same solution. Since you can now cross-check their answers against each other, you are able to indirectly verify even more complex solutions. This is like a detective checking the stories if different witnesses against each other.
tl;dr - Some problems are unsolvable, but it may or may not be possible to verify a single solution. Computer scientists want to quantify the complexity of verifying these solutions.
Assumptions in Quantum Physics:
1. Particles can be "entangled". This means that if you observe one particle, some other particle somewhere else will exhibit the exact same state change, as though they are connected by a mysterious communication channel.
2. This is super weird. Einstein thought it was so weird that he thought they must be missing something in their understanding.
3. Physicists created two separate mathematical models to describe how entanglement works: (A) the Tensor Product model, using finite dimension matrices and (B) the Commuting Operator mode, using infinite dimension matrices
tl;dr - Quantum Physics is so weird that they came up with two mathematical models for entanglement
Assumptions in Mathematics:
1. Because physicists said that the same physical property (entanglement) could be described either with infinite matrices or finite matrices, maybe you can approximate an infinite matrix using a finite matrix. This idea is the 'Connes embedding conjecture'.
2. If finite and infinite matrices are actually interrelated by the Connes embedding conjecture, maybe it means that solving one means you solved the other.
tl;dr - The two quantum physics models inspired mathematicians to conjecture about the relationship between finite and infinite matrices
Back to Physics:
1. To prove that quantum entanglement exists in real life and isn't just a math mistake, they came up with the idea of a "nonlocal game". You set up a seemingly-random test where two 'players' make guesses and the goal is to have them hit on the same guess more often than chance. If they win higher than chance, you can assume they are entangled.
2. Using those tests, they showed that quantum entanglement is real.
Back to Computer Science:
1. Computational complexity is not just a theory. "The resources that computers need to solve and verify problems — time and memory — are fundamentally physical." If you change the rules physics, you can change the rules of computer science. Our understanding of quantum entanglement as a real thing thus changes the rules of what a computer can do.
2. If two entangled particles can behave in a correlated manner, you can (in theory) use that coordination to verify the solution to harder problems by using them as two "provers". For example, you could have each particle randomly pick a node in your infinite graph and inspect a different edge. But since they are entangled, the two particles always pick the same node. That means you can use them to indirectly inspect an infinite graph and verify a previously unverifiable solution.
New CS discovery in the paper:
1. Entangled provers allow you to verify solutions to the unsolvable halting problem. That implies that you can also verify the solution to any problem easier than the halting problem using quantum particles.
2. This neat and re-writes the rules of CS complexity, but at a glance appears not very interesting to other fields.
New Implication for Physics:
1. Wait a sec! Since the problem you are verifying itself is unsolvable, this implies the two mathematical models of quantum entanglement are NOT equivalent (more details in article).
New Implication for Math:
1. This means the Connes embedding conjecture (which said we can estimate an infinite-dimension matrix from from a finite dimension matrix) is also definitely FALSE.
So in the process of computer scientists trying to clarify the bounds of computational complexity theory, they accidentally re-wrote the rules of quantum physics and invalidated a major mathematical assumption. But the CS researchers aren't physicists or classical mathematicians, so they don't even claim to fully understand the cross-discipline implications of what they discovered.
Not necessarily. Or rather, we don't know that's actually the case for the most important example - machines which work in time polynomial in the length of their input (P vs. NP).
If you are seriously looking for a nugget I would suggest trying to understand the nonlocal game example (which was hidden in the write up)
"But first, to see how the games work, let’s imagine two players, Alice and Bob, and a 3-by-3 grid. A referee assigns Alice a row and tells her to enter a 0 or a 1 in each box so that the digits sum to an odd number. Bob gets a column and has to fill it out so that it sums to an even number. They win if they put the same number in the one place her row and his column overlap. They’re not allowed to communicate.
Under normal circumstances, the best they can do is win 89% of the time. But under quantum circumstances, they can do better.
Imagine Alice and Bob split a pair of entangled particles. They perform measurements on their respective particles and use the results to dictate whether to write 1 or 0 in each box. Because the particles are entangled, the results of their measurements are going to be correlated, which means their answers will correlate as well — meaning they can win the game 100% of the time."
These notes might help to understand the basic idea: https://www.scottaaronson.com/qclec/14.pdf In particular, after understanding why the best they can is win 89% on normal circumstances, the easier examples at the beginning of the notes provide intuition of how a quantum strategy might help for the 3-by-3 grid game. Edit: also see the write up by ahelwer below.
It's a bit more complicated to follow but absolutely worth the work.
Why not just imagine Alice tells Bob how she's going to choose what to write in the boxes? That works 100% of the time too.
I don't see a distinction between "Alice and Bob communicate" and "a pair of entangled particles gives Alice and Bob a piece of shared information that, by prior arrangement, they both interpret in the same way."
Alice and Bob can pre-share arbitrary amounts of classical information and still not win more than 89% of the time.
What would your strategy be for sharing information before the game starts?
The crux is that Alice and Bob don't know which row/column the other is filling, and they are given symbol-selection rules which would contradict each other if used to fill the whole square, preventing a pre-ordained strategy (e.g. a pre-seeded RNG) with 100% success rate. So a 100% strategy would intuitively need some way of communicating _after_ they are given their row and column, and the math shows that the quasi-communication granted by entanglement is sufficient.
I'm sure my explanation is also insufficient, but there should be enough information at the link to convince you if you're curious.
[1] https://en.wikipedia.org/wiki/Quantum_pseudo-telepathy#The_M...
> They're apparently the same phenomenon
You're the one deciding that they're the same phenomenon, by choosing to only imagine using the entangled particle pair to seed a PRNG on each side using the same method.
The key thing to realize is that Alice and Bob have quantum mutual information, not classical, and that "quantum" here is not just technobabble but actually has meaningful consequences.
If Alice and Bob choose to destroy the quantum information and extract the same bit(s) of classical information from their respective halves of the entangled pair(s) before the game starts, then the quantum case has been reduced to the classical case and you can think of them as the same phenomenon. But if instead they keep the quantum information around past the start of the game and decide what to do with it based on the hand they're dealt, they can get a win rate that's impossible with only pre-shared classical information.
So entangled particles give you fundamentally different properties to a seed to an RNG (or any other arbitrary local hidden-variable setup you can come up with).
The problem can be rephrased as "does there exist an ideal PRNG that is not discernible from a true quantum RNG". Discerning between real RNG and PRNG is akin to solving the halting problem and one of the lynchpins if the proof.
If communication really needs to be forbidden, just let them agree on an RNG beforehand and share a seed. This seems to eliminate any quantum magic involved, which suggests I don't really understand the problem, which suggests that they haven't really explained it.
Can you explain how this will allow them to always win the game?
It may help to point out that (someone correct me if I'm wrong here...) this only works if both Alice and Bob are able to use their hidden information to choose the bases they're using to measure the qubit; if they were stuck with measuring at pre-determined angles, this trick doesn't work.
Disclaimer: zero quantum research background, only cs and a hint of math
Alice doesn't know which column is Bob's column, and Bob doesn't know which row is Alice's row.
The description of the game in the article is incredibly simplified. The original Bell game is that you take two particles and separate them spacially so that any local (slower-than-light) communicaton cannot interfere with the experiment. You then measure their spins in two orientations (the absolute orientation isn't important, only the angle between the two measurements is important) and repeat a large number of times. Then, sum how many times the two measurements had the same spin (+1) or opposite spins (-1) and divide it by the number of measurements to get the "correlation" (scare quotes because this is not the same as what statisticians mean when they say "correlation"). Repeat for a large number of different relative angles and plot "correlation" vs angle.
Quantum mechanics predicts (and experimental data produces) an inverse cosine "correlation" curve. However, it is simply not possible to produce that "correlation" curve using a local, hidden variable theory of quantum mechanics. Why? With some slight hand-waving, it's because the two particles don't know along which (relative) angle the other particle will be measured ahead of time -- if you permit non-locality (faster-than-light communication or "spooky" action at a distance) then this problem goes away. Now, the proof that this is the case is far more involved than this (and to be honest I'm not sure I understand it well enough to explain it). But hopefully that gives you some idea why the "just use an RNG" method is not sufficient.
Since the two particles are created from the same source, why couldn't it be that the two particles are affected by the initial state of their source so as that to appear correlated?
But that's effectively just a description of the problem. It doesn't really help you come up with a local hidden-variable theory of QM could produce the same "correlation" vs angle curve.
The problem (in computer science terms) is that you need to come up with an algorithm (which for a given particle (A or B) takes some state (called lA or lB), and an angle parameter (oA and oB)) that gives you an output which has the statistical distribution which agrees with QM if you randomly sample lA and lB values. In other words, write an algorithm such that the "correlation" of Measure(oA, lA) and Measure(oB, lB) is always equal to precisely -cos(|oA - oB|) without using global variables. It turns out this is (provably) impossible.
NOTE: In the real experiment you're actually measuring in 3D, so the angles should actually be unit vectors and the angle difference is actually (a function of) the dot product.
If the source is responsible for the correlation, what other explanation do we need? why we need to explain it with a local hidden-variable theory of QM?
Why isn't it enough that the source is responsible for the correlation?
And since it's impossible to write that algorithm, why not simply suppose the values of iA and iB are such that the correlation is possible?
Wouldn't global variables actually be non-local communication, instead of local? they are global variables, just like entanglement is 'global' for the universe.
Ah, okay -- that's a very good question (I skipped over a bunch of context on what problem we are discussing in my first responsd).
The problem is that all quantum mechanical measurements appear to be random. We might know (through our understanding of quantum mechanics) that measuring a particle in a particular state will give us spin-up 75% of the time, and spin-down 25% of the time -- but we cannot predict what any single measurement will give us. As far as we can tell, each measurement is as close to a real-life RNG as we can find.
This apparent randomness (and thus inability to predict individual experiments -- only being able to predict the statistical distribution of many experimental trials) has unnerved scientists for several decades, and thus many "deeper theories" have surfaced to try to explain where this randomness is coming from. Hidden-variable theories are one such class of theory, and are based around the idea that there is just some additional fundamental quantum numbers associated with quantum states which we don't know about -- these are the most natural-feeling theories because these kinds of extensions are a common theme in the history of physics. A local hidden-variable theory would be the most ideal because it would allow for the unification of relativity and quantum mechanics -- but alas, it is not to be.
> why not simply suppose the values of iA and iB are such that the correlation is possible
Punting the problem to the state doesn't help -- the state variables are decided ahead-of-time when the particle states are first created. Having your algorithm just use a value in the state still counts as an algorithm.
I really recommend trying to come up with a toy algorithm to solve this problem, to get an idea of where the hidden complexity arises.
The key problem (as you may discover yourself) is that you can't tell what angle the other particle will be measured with, and thus you don't know what statistical weight to apply to the state you have internally.
> Wouldn't global variables actually be non-local communication, instead of local?
Yes, "global variables" would be non-local. Hence why you can't use them (Bell's inequalities only prove the non-existence of local hidden-variable theories of QM).
In Bell's thought experiment, the angle between the axes of two particles is well known before any particle is fired. Why do you say the following?
> you can't tell what angle the other particle will be measured with
If the angle is 90 degrees, the correlation would be 50%, if the angle is 180 degrees, the correlation would be 100%, and when the angle is 0 degrees, the correlation would be 50%.
What are you saying (or rather, the theory says) is that since we have the above numbers, if there were local variables, then the correlation, for example, at 90 degrees should have been 25%, and the correllation at 270 degrees should have been 75%, but since in both cases the correlation isn't that, we can't have local variables?
Edit:
What about this algorithm?
struct ParticleState
{
double otherAngle;
};
double algorithm(ParticleState state, double angle)
{
return -cos(abs(angle - state.otherAngle));
}
This algorithm returns precisely -cos(|oA - oB|) as you suggested.
The relative angles I'm referring to are of the measurements (or rather, the relative angle between the two measurement vectors). Those angles can be thought of as being unknown when the particles are created (because you can imagine the experimenters for A and B randomly picking an angle after the particles have been separated).
We do "know" that the particles have a particular spin along a particular axis when they're created (more accurately, we know that the spin axes have a particular property -- that they have opposite spins along some axis), but we aren't necessarily measuring along that axis (and if you measure a quantum state along a different axis, you get random-looking results that follow a particular statistical distribution which is predicted by quantum mechanics).
To give an example of this property. Imagine a particle which we measure to have a +1/2 spin in the Z-axis. If you then measure it along the X-axis you'll get a result of +1/2 50% of the time (note though, that subsequent measurements of the same particle in the same state will give you the same result because measuring the particle collapsed its state to be along the axis you measured). Now, we aren't measuring along the Z-axis in this experiment (instead we're depending on a different property of the particles to calculate their correlation) but the idea is very similar.
> If the angle is 90 degrees, the correlation would be 50%, if the angle is 180 degrees, the correlation would be 100%, and when the angle is 0 degrees, the correlation would be 50%.
Sure, but if particle A is measured along -47 degrees from the Z-axis (angle chosen at random after the particles are separated), and particle B is measured along +133 degrees from the Z-axis (also a random angle chosen after the particles are separated), how would A (or B) individually know what statistical distribution to produce when you measure it? All the A particle knows is that you measured it at -47 degrees from the Z-axis and it doesn't know what angle B was measured against (heck, the scientist doing the measurement might not know what angle B is being measured against).
> 'other angle' is the angle of the other entangled particle.
The angle is not a property of the particle, it's a property of the measurement we take.
Like imagine the 3x3 grid suddenly changes after Alice and Bob write down their first message.
No, it does not. Let’s suppose Alice’s pre-negotiated (or predetermined by a seeded PRNG) choices for rows 1..3 are:
(A11 A12 A13)
(A21 A22 A23)
(A31 A32 A33)
And Bob’s choices for columns 1..3 are:
(B11) (B21) (B13)
(B21) (B22) (B23)
(B31) (B32) (B33)
If they are given row 1 and column 1, the intersect should match, i.e. A11 == B11. The same goes for any row and column selection: Aij == Bij. That is not, however, consistent with the requirement that the sum of all numbers for Alice must be an odd number (each row must add up to an odd number and there are 3 rows), and the sum of all numbers for Bob must be an even number (each column must add up to an even number and the sum of three even numbers is even). So, that’s the real catch for the classical setup. And yes, quantum correlation can beat it.
The point of the analogy is that in the quantum version there is a way to work around this unavoidable constraint in the classical problem.
The fact that they can't know which row/column they're going to be assigned makes it impossible to know with more than 8/9 certainty what the correct move would be. Even if they agree ahead of time what the values should be, the fact that they only know half of the information makes it impossible (classically) to win more often than 8/9 of the time. They have no control over and no way of knowing which row/column the other was given.
If I'm understanding correctly, the "quantum version" lets you increase that precision arbitrarily depending on how many measurements you make, up to 99.9999999...%
Really neat stuff
1. Every row has an even sum
2. Every column has an odd sum
I simply simulated the game on a computer one million times which revealed that changing the door after the host removed a empty one had a 66% probability of winning. (rather then 50%) but the teacher wouldn't believe me...
The solution is counter-intuitive, but the problem can be solved with some elementary probability theory.
I'm saying that since the OP appears to believe that a simulation proves it (which of course it doesn't), there's a decent chance other parts of the story also are incorrect.
Because yes, this puzzle is quite well known for confounding intuition. Presumably a math teacher knows that when they introduced the question.
Right, and this is the intuitive solution. Nobody argues that switching reduces your chance of success; the split is over whether it increases it to 2/3 or leaves it at 1/3.
(The problem statement ends with 'Is it to your advantage to switch your choice?' The right answer under the intended assumption about the host is 'yes', but the intuitive answer is 'no, it makes no difference'.)
The specific posing of the problem is that the game is you are presented with three doors, you choose one, and the host opens a door showing a goat, and you have to decide if you want to switch.
The problem is that people imagine a game where you choose a door and the host decides whether to open a second door to convince you to switch OR they open the door you chose to show the goat. So given that they CHOSE to open a goat-door, is it the right move to switch? That problem is a game theory problem and requires that you understand the strategy that the host is employing; the intuition is that the host WANTS you to lose, so will only open the goat-door if you chose right (or has a significantly higher probability of doing so) so switching is "falling for" the trick.
Re-imagining the problem as a different scenario, where you can ask to see which of two doors contains a goat, and then deciding which door to take avoids this trap. Then the solution is not obvious, but not counter-intuitive (maybe; depends on your intuition).
It can be understood that the contestant choosing to switch doors has a probability of winning equivalent to that them being allowed to choose two of the three doors in the first place. By not switching they are choosing one door (1/3) but by switching (since one of the empty doors is removed) they are effectively choosing both the other two doors (2/3).
What are the odds you guessed it right on your first pick? (1/3) That’s the only time switching answers will not reveal the prize. The rest of the time there is a losing door and a winning door and the host is forced to reveal the losing door so switching wins 2/3 of the time. It’s that simple.
LOL this was the original promise of Quantum Computers. I would think a proof would be a quantum computer that actually delivers on that promise.