12 ms·

Major Quantum Computing Advance Made Obsolete by Teenager (2018)

113 points by g42gregory 5y ago

Strilanc 5y ago
This might be coming up again because the paper was finally published, like in a journal after peer-review, one month ago [1]. The pre-print has been available since 2018 [2]. [1]: https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.127.060503 https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.12... [2]: https://arxiv.org/abs/1811.00414 https://arxiv.org/abs/1811.00414
- knuthsat 5y ago
  What does this mean? After making the state preparation assumption, the classical algorithm can be of same complexity? Or the classical algorithm does not depend on state preparation?
  - Strilanc 5y ago
    The advantage of the quantum algorithm drops from exponential to polynomial, when the classical algorithm is able to query the data in the way it's being assumed the quantum algorithms can query the data.
  - mjburgess 5y ago
    It is helpful to have a really clear idea of what a computer is: an algorithm is a sequencing of operations which take some time; important operations to sequence are memory (ie., data) access. In the classical case we stipulate a model of data access (eg., a Random-Access-Model) which enables calculating a "time-complexity" (performance) of the algorithm. In the quantum case it appears that where such models exist they haven't been carefully compared to the classical ones. It seems here the claim is that when you do this comparison carefully, you find most of the speed up of the algorithm comes from a stipulated data access model -- rather than "a more powerful sequencing of actions". The proof appears to involve a means of stating equivalent classical assumptions about the data access model; and showing under these assumptions, many key quantum algorithms have "time-similar" classical versions (ie., the time-complexity difference isnt expotential, as previously claimed).
bombcar 5y ago
I suspect a number of quantum advancements will be this type of two steps forward, one step back as people discover that the quantum part wasn't really necessary.
- bredren 5y ago
  This is ~what the article suggests near the end. Are there other examples in math or physics where work on some advanced concept (like quantum) results in useful advancements in contemporary / classical systems? If the original authors had set out to prove no faster recommendation system existed, would they have found the same solution? Would this alone have been an interesting enough problem to work on? I suppose I am wondering if the cachet of quantum (or some other field’s killer next thing) alone is useful if it results in driving forward understanding of technology we have at hand.
  - bombcar 5y ago
    A decent number of problems come down to “does it have a solution or not” and once it’s known there is a solution it becomes easier to find it in a way. Humans are funny that way - the four minute mile is another example.
userbinator 5y ago
Any relationship between this and integer factoring?
- tromp 5y ago
  Not until someone finds the classical ploynomial time integer factoring algorithm :-) On a more serious note, the two problems seem to be of a different nature. With integer factoring, the underlying structure of natural numbers is fixed, while in the recommendation problem, the input describes the structure.
  - deleted 5y ago
    [deleted]
  - whatshisface 5y ago
    The underlying structure of matrices is fixed, but in the recommendation problem you're given a specific matrix. Likewise with integer factoring the underlying structure of integers is fixed, but you're given a specific integer.
- tsimionescu 5y ago
  No known one. Interestingly, my understanding from Scott Aaronson is that most computer scientists expect there to be a fast classical integer algorithm, it just hasn't been found yet.
  - cevi 5y ago
    While computer scientists might expect slightly faster factoring algorithms to exist than the ones we know of - perhaps exp((# bits)^0.25) is plausible - I think the majority of computer scientists, including Aaronson, would be completely shocked if it was possible to factor integers in polynomial time. Factoring isn't a problem like testing primality, or graph isomorphism, where we had algorithms that worked well in practice but not perfectly theoretically for many years before the major breakthroughs. While it wouldn't be quite as mind-boggling to find a fast factoring algorithm as it would be to efficiently solve SAT - factoring almost certainly isn't NP-complete - it definitely seems to fit somewhere into the "hard" side of things from the standpoint of classical complexity. One way to think of it is this: when problems can be solved efficiently, there is generally some sort of nice algebraic structure that makes them easy. Nice, exploitable algebraic structure is extremely rare: if you haven't found hints of it after putting in a fair amount of effort, it probably isn't there at all. Of course, we can't currently rule out the possibility that there are secret ghostly algebraic structures that will render everything easy lurking just beyond our current knowledge, but intuition from studying our best known algorithms and our complete lack of progress on truly hard problems indicates that this isn't the case.
delusional 5y ago
What a beautiful example of science building on itself. A new framework gave way to a new solution, and now that solution has been ported back to the old framework. It's a wonderful process.
jhgb 5y ago
"Millennials^H^H^H^H^H^H^H^H^H^H^H Zoomers killing another industry" > "I was hesitant because it seemed like a hard problem when I looked at it, but it was the easiest of the problems he gave me" For some reason I'm getting some major "Dantzig coming late into lecture" vibes here.
_0ffh 5y ago
Scott Aaronson's blog post about this: https://www.scottaaronson.com/blog/?p=3880 https://www.scottaaronson.com/blog/?p=3880 HN at the time: https://news.ycombinator.com/item?id=17519001 https://news.ycombinator.com/item?id=17519001
mjburgess 5y ago
My initial interpretation: Previously we thought quantum algorithms were radical improvements over classical algorithms. Rather, where this improvement exists at all, it is actually coming from assumptions about the /non-computational/ 'input' preparation. Here, analogously, we thought we had a better CPU, but we were actually just switched the HDD to an SSD. I'd like to be more radical here and say that, perhaps, everything significant about quantum computers has nothing to do with their computational properties (ie., their discrete/sequential properties). But rather, comes from exploiting continuous features of their underlying material states. I'd be grateful if any specialist were able to comment on that; as I think, were it true, we should probably say that "quantum computers" arent (mostly) computers at all -- they are more like "quantum hard-drives".
- Strilanc 5y ago
  This result is only about one kind of quantum algorithm. I don't agree with the characterization of quantum computers as being more like hard drives. If anything this result pushes in the opposite direction. Quantum algorithms work best when they use an extremely small amount of data; the complexity of querying data can give classical computers a foothold.
  - mjburgess 5y ago
    I wasnt clear in the sense of "HDD" I was using; it wasnt about data volume. I mean that a quantum computer isn't strictly a CPU whose computational properties are the ones we are using when we compute stuff (ie., discrete switching of states). It is more like a device which holds state in a non-discrete manner, eg., like freezing water; or the physical structure of a hard-disk. So that if/when we use a quantum computer to "do anything" useful, it is actually useful not because it is a better CPU, but more, because it /holds state/ more usefully. Ie., its computational properties aren't the interesting ones; it's (continuous?) state representation properties are. That's the claim i'm asking about at least, it would helpful if a specialist had a response.
    - feanaro 5y ago
birbs 5y ago
How is integer factoring not the best-known possible example of a quantum speed-up? What was special about this recommender system problem?
- mirekrusin 5y ago
  Maybe he was scared he may solve it and didn't want to live through apocalypse.
- sgt101 5y ago
  There don't seem to be many practical applications of integer factoring - basically it's good for cracking PKI. On the other hand these recommender algorithms looked really useful for the applications that folks use recommenders in now and for extending to deal with potentially other sparse matrix problems as well. Which is good because the paper here produced a good classical alternative. This is a problem for QC though because there really aren't many actual algorithms to run on these things that are going to be that useful afaik. At least with analytical complexity results (I think quantum neural nets don't have these yet?) - I would love to see counter examples! Note - a lot of QC algorithms provide only modest speedups like ^2 improvements - the ^n improvements are the ones we want and are v.rare.
sugarkjube 5y ago
This makes me wonder. It occurs once in a while that a student (although in this case a particular bright mind) solves a complicated problem where experienced researchers haven't. One well known example that comes to mind is the famous George Dantzig case (he mistook 2 open statistics problems for an assignment, and promptly solved them). Also in this case Tang apparently was hesitating to approach his his mentor Aaronson about this. And Aaronson also wanted additional scrutiny like presenting to limited audience before publication. Why is it ? Are people just smarter when they are young ? Or is it fear of failure ? Or prejudice - it's unsolvable ? I remember myself in college, cryptology class, where a fellow student invented a shortcut for some calculations. Back then, we didn't know whether it was a known formula or not, or even whether it was correct; we searched but couldn't find it mentioned anywhere. He never dared to tell the prof, but most of us actually used it successfully during our exams to assist and validate our calculations.
- thysultan 5y ago
  Young minds have less systematic tunnel vision.
  - Fjolsvith 5y ago
    Or perhaps, less indoctrinated minds...
- hackpert 5y ago
  *her mentor :) Source: https://ewintang.com/ https://ewintang.com/
  - antisocial 5y ago
    The original article seems to go extra distance to avoid she or her in the article. I was surprised to find that Ewin is female.
    - whatshisface 5y ago
      I can sort of understand why Aaronson would do that, any time you mention a pronoun, a moment later the entire discussion is dominated by nothing but pronoun stuff. It is literally happening right now in this comment thread that I am participating it. :-) (Original article for reference) https://www.scottaaronson.com/blog/?p=3880 https://www.scottaaronson.com/blog/?p=3880
Managor 5y ago
Does anyone know the best place that explains the algorithm to a less educated person? This article treats it as a black box.
echopurity 5y ago
>Kerenidis and Prakash proved that a quantum computer could solve the recommendation problem exponentially faster than any known algorithm That's not a proof. It's a few hopeful examples. The current proof only appears stunning to those who were formerly satisfied with weak evidence.
Atlas667 5y ago
Good on him, but this seems bittersweet to me. This coupled with social media or search engine information can help determine mental states, world outlooks, and can be used to manipulate outcomes. A custom reality for customized behaviour. Anyone knows if this is implemented anywhere?
FpUser 5y ago
What an amazing story and what a brilliant mind. I wish all the best to Tang and hope he would bring more wonders later on.
- deleted 5y ago
  [deleted]
john579 5y ago
It doesn't take a genius to point out that the emperor has no clothes. Eventually quantum electrodynamics will go the way of geocentrics and the pancake earth. Unfortunately, there will always be charlatans around using sophisticated language to trick the best and brightest into believing absurdity after absurdity. However, quantum computing wins the Darwin award hands down.

113 points by g42gregory 5y ago

This might be coming up again because the paper was finally published, like in a journal after peer-review, one month ago [1]. The pre-print has been available since 2018 [2]. [1]: https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.127.060503 https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.12... [2]: https://arxiv.org/abs/1811.00414 https://arxiv.org/abs/1811.00414

knuthsat 5y ago
What does this mean? After making the state preparation assumption, the classical algorithm can be of same complexity? Or the classical algorithm does not depend on state preparation?
- Strilanc 5y ago
  The advantage of the quantum algorithm drops from exponential to polynomial, when the classical algorithm is able to query the data in the way it's being assumed the quantum algorithms can query the data.
- mjburgess 5y ago
  It is helpful to have a really clear idea of what a computer is: an algorithm is a sequencing of operations which take some time; important operations to sequence are memory (ie., data) access. In the classical case we stipulate a model of data access (eg., a Random-Access-Model) which enables calculating a "time-complexity" (performance) of the algorithm. In the quantum case it appears that where such models exist they haven't been carefully compared to the classical ones. It seems here the claim is that when you do this comparison carefully, you find most of the speed up of the algorithm comes from a stipulated data access model -- rather than "a more powerful sequencing of actions". The proof appears to involve a means of stating equivalent classical assumptions about the data access model; and showing under these assumptions, many key quantum algorithms have "time-similar" classical versions (ie., the time-complexity difference isnt expotential, as previously claimed).

bombcar 5y ago

I suspect a number of quantum advancements will be this type of two steps forward, one step back as people discover that the quantum part wasn't really necessary.

bredren 5y ago
This is ~what the article suggests near the end. Are there other examples in math or physics where work on some advanced concept (like quantum) results in useful advancements in contemporary / classical systems? If the original authors had set out to prove no faster recommendation system existed, would they have found the same solution? Would this alone have been an interesting enough problem to work on? I suppose I am wondering if the cachet of quantum (or some other field’s killer next thing) alone is useful if it results in driving forward understanding of technology we have at hand.
- bombcar 5y ago
  A decent number of problems come down to “does it have a solution or not” and once it’s known there is a solution it becomes easier to find it in a way. Humans are funny that way - the four minute mile is another example.

userbinator 5y ago

Any relationship between this and integer factoring?

tromp 5y ago
Not until someone finds the classical ploynomial time integer factoring algorithm :-) On a more serious note, the two problems seem to be of a different nature. With integer factoring, the underlying structure of natural numbers is fixed, while in the recommendation problem, the input describes the structure.
- deleted 5y ago
  [deleted]
- whatshisface 5y ago
  The underlying structure of matrices is fixed, but in the recommendation problem you're given a specific matrix. Likewise with integer factoring the underlying structure of integers is fixed, but you're given a specific integer.
tsimionescu 5y ago
No known one. Interestingly, my understanding from Scott Aaronson is that most computer scientists expect there to be a fast classical integer algorithm, it just hasn't been found yet.
- cevi 5y ago
  While computer scientists might expect slightly faster factoring algorithms to exist than the ones we know of - perhaps exp((# bits)^0.25) is plausible - I think the majority of computer scientists, including Aaronson, would be completely shocked if it was possible to factor integers in polynomial time. Factoring isn't a problem like testing primality, or graph isomorphism, where we had algorithms that worked well in practice but not perfectly theoretically for many years before the major breakthroughs. While it wouldn't be quite as mind-boggling to find a fast factoring algorithm as it would be to efficiently solve SAT - factoring almost certainly isn't NP-complete - it definitely seems to fit somewhere into the "hard" side of things from the standpoint of classical complexity. One way to think of it is this: when problems can be solved efficiently, there is generally some sort of nice algebraic structure that makes them easy. Nice, exploitable algebraic structure is extremely rare: if you haven't found hints of it after putting in a fair amount of effort, it probably isn't there at all. Of course, we can't currently rule out the possibility that there are secret ghostly algebraic structures that will render everything easy lurking just beyond our current knowledge, but intuition from studying our best known algorithms and our complete lack of progress on truly hard problems indicates that this isn't the case.

delusional 5y ago

What a beautiful example of science building on itself. A new framework gave way to a new solution, and now that solution has been ported back to the old framework. It's a wonderful process.

jhgb 5y ago

"Millennials^H^H^H^H^H^H^H^H^H^H^H Zoomers killing another industry" > "I was hesitant because it seemed like a hard problem when I looked at it, but it was the easiest of the problems he gave me" For some reason I'm getting some major "Dantzig coming late into lecture" vibes here.

_0ffh 5y ago

Scott Aaronson's blog post about this: https://www.scottaaronson.com/blog/?p=3880 https://www.scottaaronson.com/blog/?p=3880 HN at the time: https://news.ycombinator.com/item?id=17519001 https://news.ycombinator.com/item?id=17519001

mjburgess 5y ago

My initial interpretation: Previously we thought quantum algorithms were radical improvements over classical algorithms. Rather, where this improvement exists at all, it is actually coming from assumptions about the /non-computational/ 'input' preparation. Here, analogously, we thought we had a better CPU, but we were actually just switched the HDD to an SSD. I'd like to be more radical here and say that, perhaps, everything significant about quantum computers has nothing to do with their computational properties (ie., their discrete/sequential properties). But rather, comes from exploiting continuous features of their underlying material states. I'd be grateful if any specialist were able to comment on that; as I think, were it true, we should probably say that "quantum computers" arent (mostly) computers at all -- they are more like "quantum hard-drives".

Strilanc 5y ago
This result is only about one kind of quantum algorithm. I don't agree with the characterization of quantum computers as being more like hard drives. If anything this result pushes in the opposite direction. Quantum algorithms work best when they use an extremely small amount of data; the complexity of querying data can give classical computers a foothold.
- mjburgess 5y ago
  I wasnt clear in the sense of "HDD" I was using; it wasnt about data volume. I mean that a quantum computer isn't strictly a CPU whose computational properties are the ones we are using when we compute stuff (ie., discrete switching of states). It is more like a device which holds state in a non-discrete manner, eg., like freezing water; or the physical structure of a hard-disk. So that if/when we use a quantum computer to "do anything" useful, it is actually useful not because it is a better CPU, but more, because it /holds state/ more usefully. Ie., its computational properties aren't the interesting ones; it's (continuous?) state representation properties are. That's the claim i'm asking about at least, it would helpful if a specialist had a response.
  - feanaro 5y ago

birbs 5y ago

How is integer factoring not the best-known possible example of a quantum speed-up? What was special about this recommender system problem?

mirekrusin 5y ago
Maybe he was scared he may solve it and didn't want to live through apocalypse.
sgt101 5y ago
There don't seem to be many practical applications of integer factoring - basically it's good for cracking PKI. On the other hand these recommender algorithms looked really useful for the applications that folks use recommenders in now and for extending to deal with potentially other sparse matrix problems as well. Which is good because the paper here produced a good classical alternative. This is a problem for QC though because there really aren't many actual algorithms to run on these things that are going to be that useful afaik. At least with analytical complexity results (I think quantum neural nets don't have these yet?) - I would love to see counter examples! Note - a lot of QC algorithms provide only modest speedups like ^2 improvements - the ^n improvements are the ones we want and are v.rare.

sugarkjube 5y ago

This makes me wonder. It occurs once in a while that a student (although in this case a particular bright mind) solves a complicated problem where experienced researchers haven't. One well known example that comes to mind is the famous George Dantzig case (he mistook 2 open statistics problems for an assignment, and promptly solved them). Also in this case Tang apparently was hesitating to approach his his mentor Aaronson about this. And Aaronson also wanted additional scrutiny like presenting to limited audience before publication. Why is it ? Are people just smarter when they are young ? Or is it fear of failure ? Or prejudice - it's unsolvable ? I remember myself in college, cryptology class, where a fellow student invented a shortcut for some calculations. Back then, we didn't know whether it was a known formula or not, or even whether it was correct; we searched but couldn't find it mentioned anywhere. He never dared to tell the prof, but most of us actually used it successfully during our exams to assist and validate our calculations.

thysultan 5y ago
Young minds have less systematic tunnel vision.
- Fjolsvith 5y ago
  Or perhaps, less indoctrinated minds...
hackpert 5y ago
*her mentor :) Source: https://ewintang.com/ https://ewintang.com/
- antisocial 5y ago
  The original article seems to go extra distance to avoid she or her in the article. I was surprised to find that Ewin is female.
  - whatshisface 5y ago
    I can sort of understand why Aaronson would do that, any time you mention a pronoun, a moment later the entire discussion is dominated by nothing but pronoun stuff. It is literally happening right now in this comment thread that I am participating it. :-) (Original article for reference) https://www.scottaaronson.com/blog/?p=3880 https://www.scottaaronson.com/blog/?p=3880

Managor 5y ago

Does anyone know the best place that explains the algorithm to a less educated person? This article treats it as a black box.

echopurity 5y ago

>Kerenidis and Prakash proved that a quantum computer could solve the recommendation problem exponentially faster than any known algorithm That's not a proof. It's a few hopeful examples. The current proof only appears stunning to those who were formerly satisfied with weak evidence.

Atlas667 5y ago

Good on him, but this seems bittersweet to me. This coupled with social media or search engine information can help determine mental states, world outlooks, and can be used to manipulate outcomes. A custom reality for customized behaviour. Anyone knows if this is implemented anywhere?

FpUser 5y ago

What an amazing story and what a brilliant mind. I wish all the best to Tang and hope he would bring more wonders later on.

deleted 5y ago
[deleted]

john579 5y ago

It doesn't take a genius to point out that the emperor has no clothes. Eventually quantum electrodynamics will go the way of geocentrics and the pancake earth. Unfortunately, there will always be charlatans around using sophisticated language to trick the best and brightest into believing absurdity after absurdity. However, quantum computing wins the Darwin award hands down.