13 ms·

Landmark computer science proof cascades through physics and math

636 points by digital55 7y ago

peterburkimsher 7y ago
Some practical questions: 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. [1] https://news.ycombinator.com/item?id=21332768 https://news.ycombinator.com/item?id=21332768
- baq 7y ago
  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.
- evanb 7y ago
  Entangled particles can be produced in a tabletop experiment, no need for an LHC.
jhoechtl 7y ago
In layman terms please?
ageitgey 7y ago
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.
event 7y ago
081499
zaroth 7y ago
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.
- chasd00 7y ago
  I remember my professors saying proof by contradiction was very powerful. i guess they were right after all.
- rytill 7y ago
  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.
AstralStorm 7y ago
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?
umvi 7y ago
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?
- adt2bt 7y ago
  Ever stare at a loading screen unsure if Windows is actually updating before?
  - umvi 7y ago
    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.
- artemisyna 7y ago
  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.)
  - umvi 7y ago
    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.
- Zalastax 7y ago
  A pretty simple program that fools your brain is one testing the Collatz conjecture: https://cs.stackexchange.com/a/44875 https://cs.stackexchange.com/a/44875 Or did you mean something else?
lacker 7y ago
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.
- gowld 7y ago
  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.
  - dingoegret 7y ago
    I feel the same way. Just scrolling down the history lesson to find the tldr
  - tomxor 7y ago
    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.
  - quakeguy 7y ago
    Try not to be so harsh on them, they offer a great amount of content, from authors all over the spectrum of interest. Accessible for most.
  - dfdz 7y ago
    > nugget of actual math 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 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.
eyegor 7y ago
For those interested, the arxiv link: https://arxiv.org/abs/2001.04383 https://arxiv.org/abs/2001.04383 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.
- darkcha0s 7y ago
  Some nice and easy afternoon reading
- deleted 7y ago
  [deleted]
- tzamora 7y ago
  Easiest to read and impressive article.
dkneeland 7y ago
So is this a proof for P=NP or something else entirely? I found article much too dense to understand fully
- wtallis 7y ago
  When there's a credible proof of P=NP, that'll be mentioned in the headline.
- klyrs 7y ago
  It's seen as a stepping stone towards P vs NP.
  - tgflynn 7y ago
    In what way ?
predictmktegirl 7y ago
So now when you get stuck on a hard problem, someone can actually prove that it's because you suck? Thanks science!
ivalm 7y ago
From Scott Aaronson: https://www.scottaaronson.com/blog/?p=4512 https://www.scottaaronson.com/blog/?p=4512
- TimSchumann 7y ago
  Exactly what I came to the comments looking for, thanks for posting this.
- quakeguy 7y ago
  Thx!
- n4r9 7y ago
  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.
  - potiuper 7y ago
    "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.
    - n4r9 7y ago
      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.
gautamcgoel 7y ago
One of the authors of this paper (Thomas Vidick) is a prof in my department. Brilliant guy!
tus88 7y ago
> 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.
abductee_hg 7y ago
wait, does that mean that Rice's theorem is wrong and machines can now solve nontrivial semantic problems?
- darzu 7y ago
  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.
  - j-pb 7y ago
    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.
  - bawolff 7y ago
    I think you are mistaken. RE is the class that includes the halting problem.
    - bawolff 7y ago
      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.
Alex_P13 7y ago
Top 7 payment gateway for your eCommerce business. Here we discuss the most usable Top 7 payment gateway for your eCommerce business, we hope this article will help you much. Take time and read this full article it will give you a proper net and clean experience. When you read this (Top payment gateway for eCommerce business) full article then you know how they work and what is the pricing, and which company will provide you the best solution for your business! https://www.electronthemes.com/top-7-payment-gateway-for-your-ecommerce-business/ https://www.electronthemes.com/top-7-payment-gateway-for-you...
domzhao 7y ago
incrediable
battery_cowboy 7y ago
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.
- dhimes 7y ago
  Guess I better cancel that order from Jameco then. Rats.
- thehappypm 7y ago
  Maxwell thought his E&M research was useless.
- 91aintprime 7y ago
  Hilbert's curve: Is infinite math useful? by 3blue1brown https://www.youtube.com/watch?v=3s7h2MHQtxc https://www.youtube.com/watch?v=3s7h2MHQtxc or skip directly to the conclusion; https://youtu.be/3s7h2MHQtxc?t=978 https://youtu.be/3s7h2MHQtxc?t=978
dang 7y ago
A related thread from a few weeks ago: https://news.ycombinator.com/item?id=22083935 https://news.ycombinator.com/item?id=22083935 Also these little ones: https://news.ycombinator.com/item?id=22079048 https://news.ycombinator.com/item?id=22079048 https://news.ycombinator.com/item?id=22077591 https://news.ycombinator.com/item?id=22077591 I seem to recall others but can't find them. Anyone?
jansan 7y ago
Isn't that animation at the top of the page just awesome?
- Insanity 7y ago
  I'm happy someone here mentioned it, I was entertained by it for some time!
z3t4 7y ago
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...
- drewmol 7y ago
  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). [0]https://en.m.wikipedia.org/wiki/Monty_Hall_problem https://en.m.wikipedia.org/wiki/Monty_Hall_problem [1]https://en.m.wikipedia.org/wiki/Three_Prisoners_problem https://en.m.wikipedia.org/wiki/Three_Prisoners_problem
- fastball 7y ago
  You used Monte Carlo method to solve the Monty Hall problem.
- kortilla 7y ago
  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.
- sunstone 7y ago
  This problem is tricky with three doors but if you imagine playing the same game but with 100 doors instead of three, then the result is very clear.
lwneal 7y ago
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. [1] https://arxiv.org/abs/2001.04383 https://arxiv.org/abs/2001.04383 [2] https://www.scottaaronson.com/blog/?p=4512 https://www.scottaaronson.com/blog/?p=4512 [3] https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-time-quantum-provable/ https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-ti...
- iamvik 7y ago
  very meta
- xenonite 7y ago
  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.“
- raverbashing 7y ago
  So, from reading a bit, it seems MIP* was proven harder than it was thought to be, correct?
- peterburkimsher 7y ago
  I hadn't heard of Aaronson or Regan before, but perhaps they communicate, and therefore their blog posts might be correlated. 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.
  - titanomachy 7y ago
    They do communicate, but only nonclassically.
adhdbrain 7y ago
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.
- deleted 7y ago
  [deleted]
- zeroonetwothree 7y ago
  It's an upper bound, I'm not sure if anyone has constructed an optimal algorithm matching it though.
- xondono 7y ago
  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.
- sporkland 7y ago
  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? I'm sure there is a basic piece I'm missing here.
- Gibbon1 7y ago
  I'm suspicious of 3X3 = 9 and 1 - 1/9 = 0.88888

636 points by digital55 7y ago

Some practical questions: 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. [1] https://news.ycombinator.com/item?id=21332768 https://news.ycombinator.com/item?id=21332768

baq 7y ago
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.
evanb 7y ago
Entangled particles can be produced in a tabletop experiment, no need for an LHC.

jhoechtl 7y ago

In layman terms please?

ageitgey 7y ago

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.

event 7y ago

081499

zaroth 7y ago

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.

chasd00 7y ago
I remember my professors saying proof by contradiction was very powerful. i guess they were right after all.
rytill 7y ago
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.

AstralStorm 7y ago

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?

umvi 7y ago

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?

adt2bt 7y ago
Ever stare at a loading screen unsure if Windows is actually updating before?
- umvi 7y ago
  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.
artemisyna 7y ago
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.)
- umvi 7y ago
  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.
Zalastax 7y ago
A pretty simple program that fools your brain is one testing the Collatz conjecture: https://cs.stackexchange.com/a/44875 https://cs.stackexchange.com/a/44875 Or did you mean something else?

lacker 7y ago

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.

gowld 7y ago
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.
- dingoegret 7y ago
  I feel the same way. Just scrolling down the history lesson to find the tldr
- tomxor 7y ago
  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.
- quakeguy 7y ago
  Try not to be so harsh on them, they offer a great amount of content, from authors all over the spectrum of interest. Accessible for most.
- dfdz 7y ago
  > nugget of actual math 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 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.

eyegor 7y ago

For those interested, the arxiv link: https://arxiv.org/abs/2001.04383 https://arxiv.org/abs/2001.04383 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.

darkcha0s 7y ago
Some nice and easy afternoon reading
deleted 7y ago
[deleted]
tzamora 7y ago
Easiest to read and impressive article.

dkneeland 7y ago

So is this a proof for P=NP or something else entirely? I found article much too dense to understand fully

wtallis 7y ago
When there's a credible proof of P=NP, that'll be mentioned in the headline.
klyrs 7y ago
It's seen as a stepping stone towards P vs NP.
- tgflynn 7y ago
  In what way ?

predictmktegirl 7y ago

So now when you get stuck on a hard problem, someone can actually prove that it's because you suck? Thanks science!

ivalm 7y ago

From Scott Aaronson: https://www.scottaaronson.com/blog/?p=4512 https://www.scottaaronson.com/blog/?p=4512

TimSchumann 7y ago
Exactly what I came to the comments looking for, thanks for posting this.
quakeguy 7y ago
Thx!
n4r9 7y ago
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.
- potiuper 7y ago
  "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.
  - n4r9 7y ago
    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.

gautamcgoel 7y ago

One of the authors of this paper (Thomas Vidick) is a prof in my department. Brilliant guy!

tus88 7y ago

> 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.

abductee_hg 7y ago

wait, does that mean that Rice's theorem is wrong and machines can now solve nontrivial semantic problems?

darzu 7y ago
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.
- j-pb 7y ago
  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.
- bawolff 7y ago
  I think you are mistaken. RE is the class that includes the halting problem.
  - bawolff 7y ago
    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.

Alex_P13 7y ago

Top 7 payment gateway for your eCommerce business. Here we discuss the most usable Top 7 payment gateway for your eCommerce business, we hope this article will help you much. Take time and read this full article it will give you a proper net and clean experience. When you read this (Top payment gateway for eCommerce business) full article then you know how they work and what is the pricing, and which company will provide you the best solution for your business! https://www.electronthemes.com/top-7-payment-gateway-for-your-ecommerce-business/ https://www.electronthemes.com/top-7-payment-gateway-for-you...

domzhao 7y ago

incrediable

battery_cowboy 7y ago

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.

dhimes 7y ago
Guess I better cancel that order from Jameco then. Rats.
thehappypm 7y ago
Maxwell thought his E&M research was useless.
91aintprime 7y ago
Hilbert's curve: Is infinite math useful? by 3blue1brown https://www.youtube.com/watch?v=3s7h2MHQtxc https://www.youtube.com/watch?v=3s7h2MHQtxc or skip directly to the conclusion; https://youtu.be/3s7h2MHQtxc?t=978 https://youtu.be/3s7h2MHQtxc?t=978

dang 7y ago

A related thread from a few weeks ago: https://news.ycombinator.com/item?id=22083935 https://news.ycombinator.com/item?id=22083935 Also these little ones: https://news.ycombinator.com/item?id=22079048 https://news.ycombinator.com/item?id=22079048 https://news.ycombinator.com/item?id=22077591 https://news.ycombinator.com/item?id=22077591 I seem to recall others but can't find them. Anyone?

jansan 7y ago

Isn't that animation at the top of the page just awesome?

Insanity 7y ago
I'm happy someone here mentioned it, I was entertained by it for some time!

z3t4 7y ago

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...

drewmol 7y ago
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). [0]https://en.m.wikipedia.org/wiki/Monty_Hall_problem https://en.m.wikipedia.org/wiki/Monty_Hall_problem [1]https://en.m.wikipedia.org/wiki/Three_Prisoners_problem https://en.m.wikipedia.org/wiki/Three_Prisoners_problem
fastball 7y ago
You used Monte Carlo method to solve the Monty Hall problem.
kortilla 7y ago
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.
sunstone 7y ago
This problem is tricky with three doors but if you imagine playing the same game but with 100 doors instead of three, then the result is very clear.

lwneal 7y ago

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. [1] https://arxiv.org/abs/2001.04383 https://arxiv.org/abs/2001.04383 [2] https://www.scottaaronson.com/blog/?p=4512 https://www.scottaaronson.com/blog/?p=4512 [3] https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-time-quantum-provable/ https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-ti...

iamvik 7y ago
very meta
xenonite 7y ago
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.“
raverbashing 7y ago
So, from reading a bit, it seems MIP* was proven harder than it was thought to be, correct?
peterburkimsher 7y ago
I hadn't heard of Aaronson or Regan before, but perhaps they communicate, and therefore their blog posts might be correlated. 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.
- titanomachy 7y ago
  They do communicate, but only nonclassically.

adhdbrain 7y ago

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.

deleted 7y ago
[deleted]
zeroonetwothree 7y ago
It's an upper bound, I'm not sure if anyone has constructed an optimal algorithm matching it though.
xondono 7y ago
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.
sporkland 7y ago
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? I'm sure there is a basic piece I'm missing here.
Gibbon1 7y ago
I'm suspicious of 3X3 = 9 and 1 - 1/9 = 0.88888