6 ms·

Major quantum computational breakthrough is shaking up physics and maths

177 points by jonbaer 6y ago

brian_herman 6y ago
We need a Scott Arronson to comment on this.
- Cyphase 6y ago
  https://www.scottaaronson.com/blog/?p=4512 https://www.scottaaronson.com/blog/?p=4512
- DonHopkins 6y ago
  Hopefully the one in this parallel universe.
magneticnorth 6y ago
The discussion of this paper on Scott Aaronson's blog is a great way to get a bit deeper into what was proved and what the implications are: https://www.scottaaronson.com/blog/?p=4512 https://www.scottaaronson.com/blog/?p=4512
- AnotherGoodName 6y ago
  Thank goodness. I don't want to be mean but the originally linked article was badly written. Eg. A sentence about the halting problem being unsolvable with a follow on sentence to that opening up that everything could be solved by computers...
  - deleted 6y ago
    [deleted]
  - magneticnorth 6y ago
    Agreed - the original article is written well enough that I got very interested in the result, but not well enough that I came away with much of an understanding of what, really, was proved and what all the important implications are.
  - jessriedel 6y ago
    I noticed the same error you did, and I agree the OP article doesn't tell us much about why this result is important, but I actually thought the OP article did a better job of explaining complexity classes at an extremely elementary level (not relying on what a polynomial is) than other articles I've seen
- phkahler 6y ago
  >> There is a protocol by which two entangled provers can convince a polynomial-time verifier of the answer to any computable problem whatsoever (!!), or indeed that a given Turing machine halts. Sounds like an existence proof rather than an actual algorithm. Still interesting even if it take a computer the size of the earth. I'm also puzzled by the use of the word "convince" in there. Is it possible for such a quantum oracle to lie?
  - terrelln 6y ago
    Convince means the verifier can prove to itself what the provers are telling it in polynomial time, without trusting the provers.
    - jessriedel 6y ago
      It's still unclear whether the algorithm the verifier uses has actually been identified or has only been proven to exist.
  - steve_gh 6y ago
    >> Still interesting even if it take a computer the size of the earth. There are some white mice on Magrathea who hold the IP on this.
  - btilly 6y ago
    That sounds like a probabilistically verifiable proof. See http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf for more.
deleted 6y ago
[deleted]
edge17 6y ago
Can someone offer a layman summary? Very curious but everything at this link and links in the comments is relatively impenetrable to me.
- mlthoughts2018 6y ago
  RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Keep that pinned in your mind. IP: The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. There are some additional stipulations about the probability with which the verifier must accept or reject the prover’s claim. MIP* is like IP but (a) you can have multiple provers and (b) the provers can share arbitrarily many entangled qubits. MIP* = RE One way to look at this is to think of MIP* as a subset of RE and then RE as a subset of MIP. RE being contained within MIP* isn’t very surprising - if it’s already in RE, then just clone a bunch of entangled copies of the “regular” Turing machine that already verifies “yes” answers in finite time and you’ve got your no-op MIP* version of the same thing. The hard part here (and where all the details that make the proof such an impressive achievement come in) is how to ensure the verifier doesn’t have to just trust the provers, for any general problem in RE, while still only running in polynomial time to achieve a certain level of probability of correctness. MIP* \in RE is weird though. Any decision problem where a verifier can polynomially verify a “yes” answer given info from multiple entangled provers must also be a problem where there exists a “regular” Turing machine that can verify a “yes” answer in finite time. What’s surprising is that the “collusion” of multiple entangled provers never presents the verifier with something they can polynomially verify such that some other “regular” Turing machine couldn’t. You don’t “get more” or “get extra” out of their being multiple provers that can “work together” in a sense. It turns out to be no different than the class of problems where a “yes” answer was already easy (finite time) to verify. One careful point to note is that the only place in this where polynomial time comes into play is the process of the verifier validating a “yes” answer from the provers in MIP. The process of the provers themselves may not be polynomial (though, for “yes” answers it is clear it must be finite). RE problems are not necessarily efficiently verifiable. For example the Halting Problem itself is in RE. The finite verifier for a “yes” answer is to run for the finite amount of time it takes to halt for that example. The MIP interactive proof could be running several of those in parallel and just ignore any entanglement and ask each one “have you halted?” They will all wait around for the finite amount of time it takes to halt and then say “yes” and the verifier can just check they all said yes (O(n) where n is number of provers). But again the trick is how to modify that algorithm so the verifier doesn’t just have to believe the provers, and the authors of the proof give that explicitly for the Halting Problem on page 154 of the paper. Side note: it’s really hard writing prose with a term that needs an asterisk on HN - apologies for weird italics and “MIP” when it should be “MIP*”.
Causality1 6y ago
My biggest question about quantum computers is will they ever be generalized or is that a fundamental impossibility? A hundred years from now are computers going to have a normal processor for 95% of their workload and a quantum modules for the other five percent?
- nabla9 6y ago
  Quantum computers are not useful as general purpose computers. <Φ| they would not provide any speedup for most everyday computations. <Φ| For many everyday computations where they provide speedup they provide only quadratic speedup (see Grover's algorithm) <Φ| They can't interact with the environment when they are doing calculations.
- klyrs 6y ago
  For the forseeable future, quantum computers need big honkin' hardware. I've read too much failed futurism to predict that it can/can't happen in 100 years, but I'm pretty confident that current approaches won't miniaturize quickly. They can help out with pretty neat stuff and could make for an awesome special purpose co-processor, but they'll be cloud-only for quite a while.
- bawolff 6y ago
  Right now, we only in theory know how to do some very specific things with quantum computers (mostly involving factoring prome numbers and doing physics simulations). These things mostly aren't useful to average computer user. It would probably be an add-on, kind of like a GPU (if we massively solve all the engineering problems), but only for people working on problems that need it. Sort of like how GPUs are a thing now, but most web servers dont have one because they are useless for your typical web server.
magneticnorth 6y ago
A more technical, but imo very good, blog post explaining this result can be found here: https://quantumfrontiers.com/2020/03/01/the-shape-of-mip-re/ https://quantumfrontiers.com/2020/03/01/the-shape-of-mip-re/
krackers 6y ago
See also: https://news.ycombinator.com/item?id=22083935 https://news.ycombinator.com/item?id=22083935
supergirl 6y ago
seeing something explained through an analogy, and such a complex analogy, makes me rage (interogations, cross examination, wtf)

177 points by jonbaer 6y ago

brian_herman 6y ago

We need a Scott Arronson to comment on this.

Cyphase 6y ago
https://www.scottaaronson.com/blog/?p=4512 https://www.scottaaronson.com/blog/?p=4512
DonHopkins 6y ago
Hopefully the one in this parallel universe.

magneticnorth 6y ago

The discussion of this paper on Scott Aaronson's blog is a great way to get a bit deeper into what was proved and what the implications are: https://www.scottaaronson.com/blog/?p=4512 https://www.scottaaronson.com/blog/?p=4512

AnotherGoodName 6y ago
Thank goodness. I don't want to be mean but the originally linked article was badly written. Eg. A sentence about the halting problem being unsolvable with a follow on sentence to that opening up that everything could be solved by computers...
- deleted 6y ago
  [deleted]
- magneticnorth 6y ago
  Agreed - the original article is written well enough that I got very interested in the result, but not well enough that I came away with much of an understanding of what, really, was proved and what all the important implications are.
- jessriedel 6y ago
  I noticed the same error you did, and I agree the OP article doesn't tell us much about why this result is important, but I actually thought the OP article did a better job of explaining complexity classes at an extremely elementary level (not relying on what a polynomial is) than other articles I've seen
phkahler 6y ago
>> There is a protocol by which two entangled provers can convince a polynomial-time verifier of the answer to any computable problem whatsoever (!!), or indeed that a given Turing machine halts. Sounds like an existence proof rather than an actual algorithm. Still interesting even if it take a computer the size of the earth. I'm also puzzled by the use of the word "convince" in there. Is it possible for such a quantum oracle to lie?
- terrelln 6y ago
  Convince means the verifier can prove to itself what the provers are telling it in polynomial time, without trusting the provers.
  - jessriedel 6y ago
    It's still unclear whether the algorithm the verifier uses has actually been identified or has only been proven to exist.
- steve_gh 6y ago
  >> Still interesting even if it take a computer the size of the earth. There are some white mice on Magrathea who hold the IP on this.
- btilly 6y ago
  That sounds like a probabilistically verifiable proof. See http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf http://people.csail.mit.edu/madhu/papers/2009/pcpcacm.pdf for more.

deleted 6y ago

[deleted]

edge17 6y ago

Can someone offer a layman summary? Very curious but everything at this link and links in the comments is relatively impenetrable to me.

mlthoughts2018 6y ago
RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Keep that pinned in your mind. IP: The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a probabilistic polynomial-time verifier sends messages back and forth with an all-powerful prover. There are some additional stipulations about the probability with which the verifier must accept or reject the prover’s claim. MIP* is like IP but (a) you can have multiple provers and (b) the provers can share arbitrarily many entangled qubits. MIP* = RE One way to look at this is to think of MIP* as a subset of RE and then RE as a subset of MIP. RE being contained within MIP* isn’t very surprising - if it’s already in RE, then just clone a bunch of entangled copies of the “regular” Turing machine that already verifies “yes” answers in finite time and you’ve got your no-op MIP* version of the same thing. The hard part here (and where all the details that make the proof such an impressive achievement come in) is how to ensure the verifier doesn’t have to just trust the provers, for any general problem in RE, while still only running in polynomial time to achieve a certain level of probability of correctness. MIP* \in RE is weird though. Any decision problem where a verifier can polynomially verify a “yes” answer given info from multiple entangled provers must also be a problem where there exists a “regular” Turing machine that can verify a “yes” answer in finite time. What’s surprising is that the “collusion” of multiple entangled provers never presents the verifier with something they can polynomially verify such that some other “regular” Turing machine couldn’t. You don’t “get more” or “get extra” out of their being multiple provers that can “work together” in a sense. It turns out to be no different than the class of problems where a “yes” answer was already easy (finite time) to verify. One careful point to note is that the only place in this where polynomial time comes into play is the process of the verifier validating a “yes” answer from the provers in MIP. The process of the provers themselves may not be polynomial (though, for “yes” answers it is clear it must be finite). RE problems are not necessarily efficiently verifiable. For example the Halting Problem itself is in RE. The finite verifier for a “yes” answer is to run for the finite amount of time it takes to halt for that example. The MIP interactive proof could be running several of those in parallel and just ignore any entanglement and ask each one “have you halted?” They will all wait around for the finite amount of time it takes to halt and then say “yes” and the verifier can just check they all said yes (O(n) where n is number of provers). But again the trick is how to modify that algorithm so the verifier doesn’t just have to believe the provers, and the authors of the proof give that explicitly for the Halting Problem on page 154 of the paper. Side note: it’s really hard writing prose with a term that needs an asterisk on HN - apologies for weird italics and “MIP” when it should be “MIP*”.

Causality1 6y ago

My biggest question about quantum computers is will they ever be generalized or is that a fundamental impossibility? A hundred years from now are computers going to have a normal processor for 95% of their workload and a quantum modules for the other five percent?

nabla9 6y ago
Quantum computers are not useful as general purpose computers. <Φ| they would not provide any speedup for most everyday computations. <Φ| For many everyday computations where they provide speedup they provide only quadratic speedup (see Grover's algorithm) <Φ| They can't interact with the environment when they are doing calculations.
klyrs 6y ago
For the forseeable future, quantum computers need big honkin' hardware. I've read too much failed futurism to predict that it can/can't happen in 100 years, but I'm pretty confident that current approaches won't miniaturize quickly. They can help out with pretty neat stuff and could make for an awesome special purpose co-processor, but they'll be cloud-only for quite a while.
bawolff 6y ago
Right now, we only in theory know how to do some very specific things with quantum computers (mostly involving factoring prome numbers and doing physics simulations). These things mostly aren't useful to average computer user. It would probably be an add-on, kind of like a GPU (if we massively solve all the engineering problems), but only for people working on problems that need it. Sort of like how GPUs are a thing now, but most web servers dont have one because they are useless for your typical web server.

magneticnorth 6y ago

A more technical, but imo very good, blog post explaining this result can be found here: https://quantumfrontiers.com/2020/03/01/the-shape-of-mip-re/ https://quantumfrontiers.com/2020/03/01/the-shape-of-mip-re/

krackers 6y ago

See also: https://news.ycombinator.com/item?id=22083935 https://news.ycombinator.com/item?id=22083935

supergirl 6y ago

seeing something explained through an analogy, and such a complex analogy, makes me rage (interogations, cross examination, wtf)