The paper[1] claims that MIP* = RE. At first I wasn't sure whether that was true, because the paper is too long and complicated for me to verify.
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.
They „denote by MIP the class of languages that have multiprover interactive proof systems,“ and by „MIP∗, the ‚entangled-prover‘ analogue of the class MIP. Informally the class MIP∗, first introduced in [CHTW04], contains all languages that can be decided by a classical polynomial-time verifier interacting with multiple quantum provers sharing entanglement.“
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.
Thanks for the link. Does this mean we're closer to experimentally determining whether infinite-dimensional quantum systems actually exist (rather than being approximated by very large finite ones) ? I vaguely remember this being a topic of discussion when I was in research.
"Prior to the new work, mathematicians had wondered whether they could get away with approximating infinite-dimensional matrices by using large finite-dimensional ones instead. Now, because the Connes embedding conjecture is false, they know they can’t." Your question is like asking if limits actually exist. It might be answered by first proposing what continuity holds for the quantum system.
I'm not sure what you mean by "proposing what continuity holds for the quantum system".
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.
To me the question has always been: Does infinity exist in nature?
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.
From what I gathered so far, this is more of a theoretical win for mathematicians, computer scientists, and physicists because it basically proved that if you had two Q-computers with unbounded (read: greater than infinite, basically) power, they could convince a classical computer in poly time that they could run a Q-program to completion correctly, in infinite time.
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.
TFA starts off a little cheesy, where you might almost think to bounce because the writing is going to just pummel the subject matter beyond recognition.
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.
first I’ve heard the abbreviation TFA, which apparently means “this fine article.”
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.
Can someone please explain how the math works out to 89%?
>> 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 and Bob just need to agree before hand on the proper distribution of 1s:
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 read the whole wiki page. I don't fully follow how it doesn't count as "communication". Bob may not know exactly what row Alice has or pattern Alice is using, but doesn't he know that she has either a +/- in the first row or a +/- in the second row or a +/- on the third row depending on the measurement he gets back?
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.
what I gathered from it is that infinite quantum computers can't be approximated by any finite, no matter how unreasonably large, quantum computers. we're in no danger of possessing an infinite quantum computer, so probably not that many implications either google or CERN.
If I understand it right, the proof shows the difference between a finite matrix of recursively enumerable operators and infinite matrix of non-recursive operators, is that about correct?
No, from my reading, this uses the opposite, it uses the fact that the halting problem is unsolvable to show that MIP* cannot solve harder problems than RE, which are a class easier than nontrivial semantic questions and the halting problem.
The halting problem is RE complete, which means it's both RE Hard (every problem in RE can be reduced to the halting problem) and in RE.
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.
I know its really bad form to complain about downvotes - but can i ask if people are disagreeing with me or if there is something else objectionable in my comment? If its the former, i'm confused as its trivially easy to google the definition of recursively enumerable, if its the latter I am honestly curious.
I'm curious how you find it to be hand-wavy? I only vaguely recall the details of Rice's Theorem and its proof from University years ago, but does it not stand on some very rigorous formal foundation?
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?
We call a property non-trivial if there is a computable (partial) function that satisfies the property and another computable (partial) function that doesn't satisfy the property.
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.
Non-trivial here means something specific (see the other reply), people say "non-trivial" in this context as an abbreviation of what it means, it's not a vague term that readers are asked to give an interpretation to.
Even the introductory paragraph on Wikipedia that I mentioned immediately defines it for the context: “A property is non-trivial if it is neither true for every computable function, nor false for every computable function.” I think that’s as rigorous as can be. (You’d have to look up the actual definition of “property”, “computable”, and “function” of course. “True” and “false” are probably obvious, however.)
Slight tangent, but it seems to me that humans are not bounded by the halting problem like computers are. In other words, given a general algorithm to determine whether a program halts, I can always write a program that fools the algorithm. But I can't write a program that fools my brain. Ergo, human brains are not simply biological Turing machines like everyone seems to think?
The halting problem is that there is no algorithm possible that can answer, for all programs and all inputs, whether that program with that input will halt.
Here is my program:
def fool(input):
while input:
pass
The input given to the program is your answer as to whether it halts given that input.
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.
That's not really how it works, though. You could imagine writing an AI program that can read this program, figure out that it halts on the truthiness of the input, and handles this case flawlessly.
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
This program halts if doesHalt() says it doesn't halt, and does not halt if doesHalt says it does halt. These are both contradictions -- proving that such a doesHalt function cannot actually exist.
Have you ever written a program that incorrectly looped forever? or one that deadlocked? or had any such other liveness bugs? I can't speak for you, but I certainly have, and, if the questions on stackoverflow are to be considered representative of typical humans, then it seems most other programmers have also done this at some point
in their lives.
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.
I think that’s more of a matter that human lifespan is finite while the halting problem proof for Turing machines is across every single program.
(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.)
No, the problem is that I can design programs that fool any general algorithm A you produce. Even small programs. You can't fool my brain though for the same programs. Therefore my brain transcends general algorithms.
That seems kind of bogus because you've just disguised an unsolved math problem as a computer program. It's like me making a program like this:
if fermats_last_theorem_holds(x,y,z):
halt()
else:
infinite_loop()
Will this program halt for all possible input integers > 2?
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.
> you've just disguised an unsolved math problem as a computer program
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.
That's the not halting problem. The halting problem is whether or not you can make an algorithm that determines whether a program will halt given the source code and inputs.
I'm not a physicist or mathematician, but I tried to reduce this article to a basic level to see if I understood it. Maybe this will be helpful to someone else:
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.
> 2. But you can often verify if an answer to a problem is correct more easily than solving the problem itself.
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).
I am impressed by Quanta's dedication to trying to make cutting-edge theoretical mathematics comprehensible. I wouldn't say I succeeded in understanding this, but I feel like I got 10% of the way there.
I feel the opposite. They are so dedicated to making math sizzly that their articles are full of hype paragraphs of "mathiness" to get you excited without learning much. The clickbait headline, the intricate animation of the clickbait headline(!), the paragraphs of "human interest" goop. The worst part is that I know they bury a nugget of actual math in there, but I get exchausted trying to find it.
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.
> 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.
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."
Most of Bell's thought-experiments result in fairly unintuitive answers, so it's quite understandable that the distinction would be unclear to someone who hadn't seen this problem before.
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.
> it's because the two particles don't know along which (relative) angle the other particle will be measured ahead of time
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?
The nature of the source is the reason they are correlated in that particular way (that is effectively what entanglement is achieving, at least in this simple example). In particular, the source in the classic Bell inequalities produced particles that had opposite spins (guaranteed by conservation of angular momentum).
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.
> If the source is responsible for the correlation, what other explanation do we need? Why isn't it enough that the source is responsible for the correlation?
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?
> 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?
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.
This isn't right though. Let's say Alice tells Bob what she's going to write in the boxes, and Bob can fill out his however he wishes. Due to the constraints given in the problem (the way the rows and columns add up), Bob can only pick the "correct" value to put in 8 of his 9 squares. That is: the problem constraints were designed so that there's no 3x3 grid that wins in all 9 squares for Alice and Bob and that simultaneously satisfies the row constraints. This is why the best Alice and Bob can do is win 89% of the time -- the best grid layout (even when they preshare information) satisfying the problem constraints only wins in 8 of the 9 squares.
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.
This description greatly helped in making the problem "click" for me, thanks!
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...%
> 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.
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.
Yep, I quite literally came here to post this. It seems like exactly the kind of "not giving enough information to really understand a topic" that the OP was complaining about.
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.
I thought the point was that they can't perfectly share information. So, they could both zero knowledge proof their way through "we share common knowledge" but be unable to directly prove it due to a halting problem. I agree that this write up is missing some key details, but grokking the publication will take a few weeks/months.
Disclaimer: zero quantum research background, only cs and a hint of math
No, but as I said in my parallel comment, I don't understand how you can do any better than having an infinite amount of pre-shared information without actually communicating. If you can explain that, great (I really would be interested), but the important thing here is that without explaining it the article is kind of flawed.
I'll make an attempt, though I am by no means a domain expert. As I said in another comment, Alice doesn't know which column is Bob's column, and Bob doesn't know which row is Alice's row. Bell-like inequalities allow something interesting to happen: Alice and Bob can measure a qubit at different "basis angles" such that the phase difference in their basis angles is reflected in the correlation of what outputs they observe from the qubit. You can't do this classically; what Alice does with a pre-shared bit and her row and what Bob does with the pre-shared bit and his column, form independent random variables.
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.
OK, so if I'm understanding this right - when you give them a pair of entangled particles, they can each do some stuff to their particle to determine what the other party is going to do. How is this not communication?
I think (but IANAP) the answer is in two parts: (1) you can’t intentionally send a message—it’s like asking whether ancient civilisations are communicating with archaeologists, to which the answer is surely “only metaphorically”; and (2) even if it is communication in some sense, it’s still surely surprising, no?
Point 1) matches my lay understanding of quantum entanglement; information is transferred somehow between the entangled particles but not in a way that we can use. So if this new thing IS communication via entanglement (and I can't see how it's not, given the description) then that's huge, and opens the door to all sorts of interesting things.
Not quite, you can do some stuff that affects the correlation between one output and the other, but that can't be used for communication as each output in isolation looks random.
That’s a very valid question, and I agree the article fails to explain. The problem is that the answer is complicated (see the discussion at the bottom of the notes I posted). So my suggestion is
1) convince yourself sharing a classic seed is not enough to always win
2) read the blog post describing a simpler problem from ahelwer
3) take it on faith that this idea can be used for the magic square game
4) I know this is an unsatisfactory answer, but hopefully it is a start!
That’s the rule for MIP: Alice and Bob can’t communicate once the game starts, and their messages to the verifier depend on challenges from the verifier (which they can’t predict).
Like imagine the 3x3 grid suddenly changes after Alice and Bob write down their first message.
Well, that's sort of the point most of us seem to be making here. We don't understand, and more importantly, the excerpt doesn't explain, how sharing an entangled particle pair (from which you can generate two infinite streams of identical information on both sides) is interestingly different than sharing a seed to an RNG (from which you can generate two infinite streams of identical information on both sides). They're apparently the same phenomenon, so asking people to think about the game without explaining what the difference is means you haven't really explained what's going on.
The comments here led me to realize that I didn't really understand, either. Thank you. To save you some searching, I found the answer here [1].
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.
> [...] how sharing an entangled particle pair (...) is interestingly different than sharing a seed to an RNG
> 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.
To be clear, I wasn't saying they were the same phenomenon. I was saying they're apparently the same phenomenon, even though I know they can't really be. My opinion was that it was the responsibility of the article to explain why these apparently identical phenomena are in fact distinct.
The "interesting" thing is that entangled particles allow the player to win 100% of the time. There is _no way_ sharing only classical information before the game to guarantee 100% win rate.
The difference is that entangled particles cannot be modelled using a local hidden-variable theory of quantum mechanics (that's what the Bell inequalities and experimental evidence have shown). The reason why this is the case is a more involved question which I tried my best to explain in [1].
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).
There are two random choices. One of the value, the other by the verifier. There are infinitely many columns and rows to check, which would require an infinite amount of shared RNG. (or is otherwise finite, a PRNG)
Yet this can be done in MIP* because state in A and B is correlated for any state.
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.
I'm inclined to agree in this case, but it may also depend on the particular author... I've read some enjoyably deep yet accessible pieces on quanta before.
In high school our math teacher introduced a problem that could not be solved, which involved a TV-show game where the contender would choose one of 3 doors, and if there was something behind it, the contender would win it. But the show host would remove one of the doors without something behind it, and ask the contender if he/she would like to switch door.
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...
Yeah, the trick with this one is the game show host knows where the prize is. In the case where you picked correctly first (1:3) the switching to the other door will be a loss. But in the case where you picked wrong (2:3) the host will eliminate the non-prize door, so a win is guaranteed if you switch. So, 1/3 * 0 + 2/3 * 1 = 66% of winning for the always switch strategy. Shame on your teacher!
I think the reason that people can't shake off their intuition is that the intuition is based on the idea that the host (Monty Hall) has agency.
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).
To be fair, the problem is often badly posed. The host always reveals a goat, and this is crucial information, but people often fail to make it clear. If the host chose randomly and just happened to reveal a goat, the solution would be the 'intuitive' one.
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'.)
Sorry, I shouldn't have said 'increases it to 2/3 or leaves it at 1/3'. If he picks randomly and reveals a goat, the probability that your original choice of door is a winner is now 1/2, as is the probability that the remaining door is a winner.
The Monty hall problem (what you’ve described) doesn’t require simulations.
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.
It's known at the Montey Hall Problem[0] or another variation is The Three Prisoners Problem[1] (IMO [1] is an easier way to conceptualize the probability of different outcomes).
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).
It's very unclear from your description, but I suspect "could not be solved" means "could not be proved", in which case of course a simulation is not a proof.
This and similar math puzzles are trivial to prove compared to the math problems like the one discussed in the article. It is only that they are counter intuitive that makes it hard for people to believe them. If you change the three door to hundred door problem and have the host open 98 doors, it is rather obvious that you should switch to the one door he has not opened besides the door that you did choose at the start.
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.
> The new proof establishes that quantum computers that calculate with entangled quantum bits or qubits, rather than classical 1s and 0s, can theoretically be used to verify answers to an incredibly vast set of problems.
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.
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...