46 ms·

Teenager Finds Classical Alternative to Quantum Recommendation Algorithm

• sharpneli 8y ago
  The headline makes my eye twitch. It is technically correct but pushes age bit too much into forefront. It is a bachelor thesis work supervized by Scott Aaronson of all people. It is going to be really interesting to see if there are other algorithms where we find classical algorithms that run in polynomial time.
  • swizzbeats 8y ago
    You honestly come off as a hater in this comment. It's absolutely remarkable what he did as a teenager, and the kid is obviously a genius. Show some appreciation.
  • dljsjr 8y ago
    Maybe I'm just easily impressed but the idea of a 17 year old who skipped three grades and is already a third-year university student who was talented enough to catch Scott's attention and then address a technically challenging problem like this certainly warrants at least some recognition for the age at which he made this accomplishment. Or maybe I'm just not smart enough to hang out on Hacker News.
    • archgoon 8y ago
      The issue is that the title actually diminishes the accomplishment by focusing on the wrong thing. The work is impressive independent of the authors age. By emphasizing the age, the focus shifts from what he did, which he should be proud of, to something he will no longer have in two years.
      • n4r9 8y ago
        As someone who has done research in quantum information, the age shifts this result from "very impressive" to "extremely impressive".
      • lozenge 8y ago
        "Person discovers result in complexity theory" doesn't really beckon your mouse.
      • lordnacho 8y ago
        Surely him being very young impresses more. Kylian Mbappe won the World Cup a couple of weeks ago. He was 19. That makes it a bigger deal. Generally people are impressed by accomplishments made by younger people. I suppose there is also a similar effect at the other end, for a similar reason: you're disadvantaged in accomplishing stuff if you're at either end of the age spectrum. You either had a lot less time to get to the top, or your faculties are waning precipitously.
      • sharpneli 8y ago
        Precisely this. He already was awesome by getting a bachelors so soon and going to grad school next year. This result is on top of an awesome beginning of a career, not just a thing a random teenager did.
      • chongli 8y ago
        The piece was written by a journalist. Journalists know how to write for a general audience. That means making the story about a human being. The general public loves reading stories about prodigies. They don't care at all about the "quantum advantage" of this or that algorithm.
    • mcguire 8y ago
      Note that Aaronson also thought that a fast classical algorithm was impossible. Tang found the algorithm in spite of that false start.
      • rectangletangle 8y ago
        Always be skeptical of "impossible" without proof.
    • hackernewsacct 8y ago
      >Maybe I'm just easily impressed but the idea of a 17 year old who skipped three grades and is already a third-year university student.. Not saying this applies to Tang. But would you be equally impressed by a 17 year old from an upper middle class family whose parents recognized their gifts and used their influence to assist them in skipping 3 grades and enrolling in college early vs 17 year old from lower income family who is equally bright as the former kid, but graduates at 21 and receives no recognition for it due to an unheard of advisor at a low ranked school? On paper you'd be more amazed by the former, while the latter is equally as bright but is sort of dismissed because of their situation.
      • swiss_beatz 8y ago
        lol, are you seriously implying the kid got to where he got because of his background?
      • trophycase 8y ago
        Ok, so is your solution to be unimpressed by both, or... ?
    • phkahler 8y ago
      I thought it was taking a poke at quantum computing by putting the emphasis on his age. But that could be straight up projection on my part - I admit to having serious doubts about both the relevance and practicality of quantum computers. Yes, how I interpret it is influenced by my own bias ;-)
• classichasclass 8y ago
  I think this might represent an example of another unique value of quantum computing: as a way to get us thinking about computing problems via a different paradigm that can perhaps be translated back to classical computing.
• rukittenme 8y ago
  Wow good on this guy. I thought it might have been a high-school student reading the title but he's a PHD candidate. Incredible. What an accomplishment at 18 to be lecturing a room of PHD holders.
  • gwern 8y ago
    It is, but not as rare as you might think! I've been reading some of the old books/papers about SMPY from the 1970s, a talent search study which uses the SAT-M to screen for visuospatially-gifted middle schoolers; they then study them and try to accelerate their education with summer camps, advanced math classes, and grade-skipping and/or early enrollment in Johns Hopkins (where SMPY is based). SMPY was a big part of making acceleration for gifted children acceptable in America, when the conventional wisdom was that they should be forced into regular classes for their own good. What they often did early on was, around age 14, SMPYers would be admitted to Johns Hopkins to typically start taking math and computer science courses, at which they would often excel and be at the top of the class, expected to go on to post-graduate work around 19, and fit in so well that fellow students and their teachers often (when surveyed or asked) didn't realize they were so young. If you look in OP, that describes Tang remarkably well.
    • fatjokes 8y ago
      > visuospatially-gifted This is such a great term. I never thought about it before or how it could relate to our definitions of intelligence and ability in science/tech. So many generic tests for intelligence that perhaps there should be more focus on this area.
      • gwern 8y ago
        Yes, that's one of the take-aways from SMPY. Focus on identifying visuospatial giftedness, as opposed to simply high scores overall, is especially good at predicting scientific accomplishment. (Hence, 'Study of Mathematically Precocious Youth'.) You might ask, why use only the SAT-M, why not the other subtest, the SAT-V verbal test, since it should be equally difficult? I was surprised to find out that there was in fact a parallel study, 'SVPY', which did just that, but it got canned early on for disappointing results, apparently.
• charleslmunger 8y ago
  Scott Aaronson wrote about this on his own blog too: https://www.scottaaronson.com/blog/?p=3880 https://www.scottaaronson.com/blog/?p=3880
• proto-n 8y ago
  I just want to mention that the "recommendation systems" angle is quite unimportant here. This is a result in complexity theory, a resolution of the question "whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time" (as Scott Aaronson puts it [1]). While this problem does occur in matrix factorization based recommenders, there are a lot of solutions for it without quantum computers that perform well, and it's far from being the one method for recommendation. [1] https://www.scottaaronson.com/blog/?p=3880 https://www.scottaaronson.com/blog/?p=3880
  • vanderZwan 8y ago
    > "whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time" Could that be used in clustering algorithms in BioInformatics? EDIT: Sorry, Aaronson's writing is just too funny not to put that quote in full context: > On the Hacker News thread, some commenters are lamenting that such a brilliant mind as Ewin’s would spend its time figuring out how to entice consumers to buy even more products that they don’t need. I confess that that’s an angle that hadn’t even occurred to me: I simply thought that it was a beautiful question whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time, and if the application to recommendation systems helped to motivate that question, then so much the better. Now, though, I feel compelled to point out that, in addition to the potentially lucrative application to Amazon and Netflix, research on low-rank matrix sampling algorithms might someday find many other, more economically worthless applications as well.
    • jtbayly 8y ago
      "research on low-rank matrix sampling algorithms might someday find many other, more economically worthless applications as well." I'm not sure whether this is a typo, and he means to say that there might be more economically worthwhile applications, or whether he's trolling the people complaining that this is useless by pointing out that there are real economic benefits to it right now.
      • 8y ago
• deleted 8y ago
  [deleted]
• JackFr 8y ago
  I wish an editor would step in: (1) limit the use of 'exponentially faster', simply for the grating repetition. The phrase is used 5 times in the article. (2) In an article that is about time complexity of algorithms, be precise about terms like 'exponentially faster'. (3) In an article that is about quantum computing, don't use 'quantum' in its colloquial sense of 'significant'. That is 'quantum' in quantum computing is different than quantum in 'quantum increase'. The latter is a suspect usage, but potentially defensible as colloquial; mixing the two in the same paragraph reads poorly.
  • jessriedel 8y ago
    Where does it say "quantum increase" in the article? "Quantum speedup" does appear, but this has a specific technical meaning and it is not being used in the colloquial sense. It means that there is an efficient quantum algorithm for solving the computational task but no efficient classical one.
    • HelloNurse 8y ago
      I consider this the colloquial sense: the speedup (or, more generically, the "increase" of throughput, quality, or other performance indicators) obtained by using quantum computers. Unlike the irreducibly mathematical and very narrow concept of "exponential increase", which could be plausibly misunderstood, a quantum speedup (or increase) can be correctly abstracted to the trivial pattern of doing things in a different way which performs better, without really needing to understand the problem and the solution; it's very surprising to hear the term misused to mean "really big". How could it happen?
• jack6e 8y ago
  This is awesome work, and kudos to Tang, but I am also really impressed with how his advisor, Scott Aaronson, seems to have so selflessly supported his research and given him full credit. Even in Aaronson's quotes within the article he talks about it entirely as Tang's work, and he seems to have considered Tang's best interests in deciding how and when to let him present the work - even that he let Tang present it! Given a different person, we may have read about "UT-Austin Professor and Quantum Researcher Finds Classical Alternative to Quantum Recommendation Algorithm" (with generic help from students in a footnote somewhere). It's great to see this type of collegial mentorship.
  • lisper 8y ago
    Scott Aaronson is just one of the most awesome human beings ever. He is brilliant yet modest, and his writing is at once deeply enlightening and eminently accessible. The world would be a better place if more academics adopted him as a role model.
    • swiss_beatz 8y ago
      Just can't give the Asian kid his 15 minutes of fame, eh?
    • cambalache 8y ago
      Just to provide a counterpoint based on the scant evidence of his blog (post and comments). He is , of course , brilliant, and has a refreshing no-nonsense approach. Modest, he is not, not that is anything wrong with that, I would call modest for example Terence Tao a far more accomplished academic. This is something that should be a "law", the more accomplished a person is the most it can "afford" to be modest. So for example Einstein was more modest than say Feynman, and Edward Witten is way way more modest than your typical string theorist. The other thing I dont like about Aaronson is his weird fetish with STEM people , he seems to think scientists and technologists are somehow superior or more worthy than regular folk. I also dont agree with some of his opinions on the actions of the state of Israel, but I will avoid that, being this the Internet.
• vanderZwan 8y ago
  > “Tang is killing [Kerenidis and Prakash’s] quantum speedup, but then in another sense Tang is giving a big improvement and building on what they did. Tang never would have come up with this classical algorithm but for their quantum algorithm,” Aaronson said. I think this deserves more emphasis: regardless of whether or not we need a quantum computer in the end, as a model quantum computing is apparently useful to do research with and advance the status quo of our knowledge.
  • fossuser 8y ago
    It's worth noting that the title of the paper does emphasize this: A quantum-inspired classical algorithm for recommendation systems. The abstract does too: https://arxiv.org/abs/1807.04271 https://arxiv.org/abs/1807.04271
    • sitkack 8y ago
      Humble scientist right there, live long and prosper brother.
  • akvadrako 8y ago
    This is a bit speculative, but I suspect quantum theory is essentially god's programming language. It seems to crop up everywhere we look, like in psychology, biology, machine learning, computer science and general probability.
    • jonny_eh 8y ago
      > essentially god's programming language That metaphor seems to confuse people more than it clarifies. Did you perhaps mean "nature's programming language"?
      • pluto9 8y ago
        What's confusing about it?
• devy 8y ago
  A little bit backdrop of Ewin Tang: http://www.uta.edu/utamagazine/archive-issues/2010-13/2012/12/cultivating-genius/index.html http://www.uta.edu/utamagazine/archive-issues/2010-13/2012/1...
  • fatjokes 8y ago
    I like the last line: > And what about the future of UT Arlington’s latest wunderkind, Ewin Tang? “I haven’t come up with anything that is really ingenious yet,” he says. Be patient; he’s only 12. It only took 6 years. Not bad at all!
    • theparanoid 8y ago
      As someone who finished undergrad classes as a teenager. I totally failed to live up to my potential.
      • lixtra 8y ago
        It’s a probability game. The article states that he picked the problem that seemed easiest to him. Other people make different choices. And finally: even if you don’t achieve anything ground breaking till the end of your life it’s good you tried your chances.
      • contingencies 8y ago
        Don't sell yourself short. Lots of important stuff happens when inquiring minds age and have the benefit of cross-disciplinary experience and perspective, plus new social, temporal and fiscal resources.
  • sltkr 8y ago
    I was pretty confused by this link, until I realized that the part about Ewin Tang has been deleted from that page, which must have happened shortly after posting the link. Archive.org has the original text: https://web.archive.org/web/20180725201359/http://www.uta.edu/utamagazine/archive-issues/2010-13/2012/12/cultivating-genius/index.html https://web.archive.org/web/20180725201359/http://www.uta.ed... Quoting for posterity: ---8<--- Twelve-year-old Ewin Tang is the latest in a line of wunderkinds to begin their UT Arlington careers while other students their age are still in elementary school or junior high. History suggests he’ll continue to amaze. Ewin Tang’s classmates tend to overlook the slight, bespectacled youth sitting in the front row until he answers the professor’s queries—all correctly. Then they ask their own questions. “Who is this guy?” “Why is he here?” And always, “How old is he?” At 12, Ewin, the son of bioengineering Professor Liping Tang, is the youngest student on campus and among the youngest in UT Arlington history. Since taking his first college courses at age 10, he has completed 20 hours, including classes in calculus and differential equations, all with a 4.0 GPA. “Other students just seem kind of amazed,” he says. “They ask about my age, what I’m majoring in. Some of them actually take pictures of me. They’re pretty cool with it, though; they really don’t bother me a lot.” Although the age gap usually prevents Ewin from forming close friendships with his classmates, many are eager to work with him once they recognize his abilities. Ewin’s college career began after he completed every math course available in his K-12 private school. His intellect had already prompted school officials to move him from third to seventh grade, but it was soon apparent that he needed more. After he scored 1920 on the SAT at age 10, his parents and school officials explored college enrollment. Dr. Tang acknowledges that having an immensely bright child can be challenging. “There are no books, no guidance on exactly what to do. This (college for someone so young) is a totally gray area.” The Tangs met with then-Provost Donald Bobbitt and later with Senior Vice Provost and Dean of Undergraduate Studies Michael Moore. Ewin’s first classes, an online course in history and an on-campus calculus class, were tests he passed easily. “I think it makes a difference that I’m here,” Dr. Tang says. “Ewin has a place to go and a built-in support system.” In addition to his University coursework, Ewin works part time in his dad’s nanotechnology laboratory. He is developing a probe to detect bacterial infection, something that would greatly assist in diagnosing diseases. His career plans involve science or engineering, but he hasn’t yet settled on a specialty. “Our main concern when we began this was his social life,” says Dr. Tang, who notes that Ewin attends a private high school with students his own age for some courses and activities. “Academically he is fine, but we want him to stay in school and stay with kids his own age, to have friends his own age. So far it’s working out pretty well. Thanks to Dr. Moore, he’s having a very good experience.” “Other students just seem kind of amazed. They ask about my age, what I’m majoring in. Some of them actually take pictures of me.” Ewin spends part of Monday, Wednesday, and Friday at the private school, where he takes classes and participates in soccer, basketball, cross country, and the Science Olympiad. He also attends UT Arlington on Monday, Wednesday, and Friday and does research in his father’s lab Tuesday and Thursday. As if that’s not enough, he works with a private tutor, studies Chinese, and plays the piano and erhu, a traditional Chinese instrument akin to a violin. While it might seem that Ewin’s case is unique, Moore and his predecessors in the Provost’s Office have seen others. Because such students don’t meet traditional enrollment requirements, they are evaluated case by case. “Typically, there is a detailed conversation with the parents about the challenges and rigors of college work as well as a thorough review of the student’s academic history,” Moore explains. “Obviously, we are looking for exceptional young men and women who show the ability to excel in the classroom as well as handle the collegiate environment.” Over the past two decades, several of these exceptionally young and brilliant students have used UT Arlington as a springboard to success. ---8<---
• peter_retief 8y ago
  I am impressed, what an interesting piece
• zghst 8y ago
  Poor Chad Rigetti
• deleted 8y ago
  [deleted]
• greg7mdp 8y ago
  If he had discovered this algo a few years back, he might have won the $1 million netflix prize (https://en.wikipedia.org/wiki/Netflix_Prize https://en.wikipedia.org/wiki/Netflix_Prize).
  • dapf73 8y ago
    I'm pretty sure Netflix can give him another million.
    • fatjokes 8y ago
      Pretty sure at the current rate star ML researchers are paid, a million for Tang would be low-balling him.
      • quickthrower2 8y ago
        It could just be a handcuffless gift.
  • rspeer 8y ago
    The Netflix Prize was not concerned with the asymptotic complexity of the algorithms. It measured them only by their results.
  • modells 8y ago
    It’s doubtful that the results would rank well because they bin sort people into types of movies, which is what most algorithms likely did anyhow. In fact, the results are probably awful if it’s not built to be optimal for such a challenge. Deep learning / similar ML would take some CPU but likely outperform all brute-force or even non-ML quantum algorithms because it’s able to elucidate knowledge of likes and whatever else ephemeral metadata or movie semantic analysis can be shoveled in. Unfortunately, this seems like a “look at this trained mammal can eat out of a plate, wow!” story. Kid probably had to endure those innane 6x6 and up IQ red/white triangle blocks tests over and over. He won’t get much of a high-school life or college dorm/party experience.
• tsucres 8y ago
  The paper [1] states: > There is a classical algorithm whose output distribution is O(ε)-close in total variation distance to the distribution given by l2-norm sampling from the ith row of a low- rank approximation D of A in query and time complexity [O(poly-func)] where δ is the probability of failure. So the classical algorithm would give a "sufficiently close" approximation of what the QML would output? The article doesn't mention this at all. Is it fair to compare a quantum algorithm with an equivalent classical approximation algorithm? From the quanta magazine article: > Computer scientists had considered [the recommendation problem] to be one of the best examples of a problem that’s exponentially faster to solve on quantum computers — making it an important validation of the power of these futuristic machines. Now Tang has stripped that validation away. Has he really? [1] https://arxiv.org/pdf/1807.04271.pdf https://arxiv.org/pdf/1807.04271.pdf
  • sheroze 8y ago
    > As a consequence, we show that Kerenidis and Prakash’s quantum machine learning (QML) algorithm, one of the strongest candidates for provably exponential speedups in QML, does not, in fact, give an exponential speedup over classical algorithms. The comparison is fair and the author is giving a metric to compare the algorithms too.
  • HelloNurse 8y ago
    The quantum algorithm is exact if it works, the new classical algorithm is negligibly worse at a negligibly higher cost. Even if there's a formal difference, practical performance is what matters when discussing useful real-world applications as motivating examples for new and expensive technology.
• nsxwolf 8y ago
  Skipped 4th through 6th grades. Impressive. Is this innate or did his parents do something to make this happen? Is there anything I'm supposed to be doing with my own kids? How/when do you know when your child has this potential?
  • pbh101 8y ago
    I was around some people who did this growing up. In outlier cases like this it tends to get extremely obvious to anyone nearby, and then usually the onus is on the parents to push this process forward, keeping in mind what is best for the student holistically rather than solely educationally. Of course other situations are not as clear and the judgement call aspect becomes more pronounced, but at the same time the potential downsides are usually much smaller, i.e. skipping one grade is nowhere near the same thing as skipping three.
    • paulpauper 8y ago
      this is someone who at the age 10 could have gone to college. That's how smart he is. One in 50 million IQ. I don't think parents are that involved, imho. This is the digital age. All you need in is an internet connection to learn the same material as everyone else has access to. This kid as a 10 year could have self-taught himself calculus online. if a 10-year old shows up to school knowing as much as a 20-year-old, then grades will be skipped..lots of them.
  • paulpauper 8y ago
    probably really high IQ and knew all the material
  • acangiano 8y ago
    Nature is important but people massively underestimate the nurturing component. Parents are most definitely key for these types of outcomes. If you're not familiar with the story already, read about the Polgar sisters. https://www.psychologytoday.com/us/articles/200507/the-grandmaster-experiment https://www.psychologytoday.com/us/articles/200507/the-grand... To your question, my immediate answer was, "let them play outside". But it sounds dismissive of what you are asking. So the better answer is: provide them with the opportunity to learn, encourage their curiosity, praise them for their work not innate intelligence while still telling them that they are smart, create an environment that values and promotes education, create a program for them to follow when they show interest in a particular discipline, have great mentors help them develop, etc. The truth is, there is always going to be a compromise between having a care-free childhood and top performance from an early age. You can't really have both no matter how smart your kids are. Asian parents stereotypically tend to opt for the latter end of the spectrum with, on average, very successful outcomes.
• cwkoss 8y ago
  Scott Aaronson posted about this on his blog https://www.scottaaronson.com/blog/?p=3880 https://www.scottaaronson.com/blog/?p=3880 I like his update - a message to Hacker News commenters: "On the Hacker News thread, some commenters are lamenting that such a brilliant mind as Ewin’s would spend its time figuring out how to entice consumers to buy even more products that they don’t need. I confess that that’s an angle that hadn’t even occurred to me: I simply thought that it was a beautiful question whether you actually need a quantum computer to sample the rows of a partially-specified low-rank matrix in polylogarithmic time, and if the application to recommendation systems helped to motivate that question, then so much the better. Now, though, I feel compelled to point out that, in addition to the potentially lucrative application to Amazon and Netflix, research on low-rank matrix sampling algorithms might someday find many other, more economically worthless applications as well."
  • deleted 8y ago
    [deleted]
  • HiroshiSan 8y ago
    note that this was reference to a previous HN thread.
  • Alex3917 8y ago
    This result is really a benefit for startups building on Filecoin-type platforms, not for FAANG companies that are already at scale. Reducing the barrier to creating good recommendation algorithms is an import step in re-democratizing the web.
  • tensor 8y ago
    That seems a bit passive aggressive. I don't think economical value is what is in question, but rather the social impact of the application (or lack of positive social impact). Applications can be both economically valuable and have positive social impact. Now recommender systems are in fact useful to discover new things, not just to entice people to buy more. E.g. finding new music, related research, or other things.
    • 8y ago
• dvh 8y ago
  Conjecture: for every quantum algorithm that is faster than current classical algorithm exists yet undiscovered classical algorithm that is equally fast.
  • qzw 8y ago
    Not sure if you’re being serious, but there are already quantum algorithms that have been mathematically proven to not be dequantizable, i.e. have no possible classical version that's as fast.
    • Ar-Curunir 8y ago
      What's your definition of "as fast"? We can't separate BQP from P right now. That is, we don't know any problems that run in polynomial time on a quantum computer, but provably have no polynomial time classical algorithms.
      • qzw 8y ago
        “As fast” in the big-O sense. Here’s what Scott Aaronson says in reply to one of the comments on his blogpost about this paper: I should point out, though, that in many cases (Simon’s problem, period-finding, Forrelation, quantum walk on glued trees…), people have proved exponential separations between the quantum and randomized query complexities, which means that there certainly won’t be a dequantization in those cases along the same lines as what Ewin did.
    • guelo 8y ago
      But nobody can figure out anything useful that those algorithms would be good for.
      • qzw 8y ago
        For literally centuries, people thought that number theory had no practical applications. Same for a number of other fields of mathematics. Is quantum computing somewhat overhyped at this moment in history? Undoubtedly (but way less so than block chains, I would argue). But that doesn’t mean it won’t ever become practically useful.
• FactolSarin 8y ago
  Sometimes I think I'm smart because I can configure WebPack, and then I read an article like this.
  • efdee 8y ago
    I'd like to see him try that.
    • travmatt 8y ago
      Can he vertically center a div though?
      • Aeolun 8y ago
        Flex!
        • mkoryak 8y ago
          tables!
          • i6mi6 8y ago
            Early 2000s strike back
        • silvestrov 8y ago
          Flexbox’s Best-Kept Secret (margin: auto) https://hackernoon.com/flexbox-s-best-kept-secret-bd3d892826b6 https://hackernoon.com/flexbox-s-best-kept-secret-bd3d892826...
      • twic 8y ago
        Sure, simply construct an evenly-distributed superposition of centerings, and let the divfunction collapse! It will work on average.
    • carterehsmith 8y ago
      Heh, I can imagine him in front of some whiteboard, while some interviewer dude is like... "uh... the candidate does not even understand the basic WebPack.keepCompatWithWebPack0.1.11='comp,3t,all'. And I am not even joking. What's next, the candidate cannot count? If you don't know the basics, what good can you do? No hire. "
• pulkitsh1234 8y ago
  And here I am, struggling to solve TopCoder problems....
  • thegrasshopper 8y ago
    Because that's what you get paid for as a techie (and in turn, what most tech companies relentlessly grill people for in the interview process): the ability to jump through hoops others have set up for you. Not the ability to do original, groundbreaking work.
  • pseudolus 8y ago
    You can always console yourself with the knowledge that you* can rent a car and buy a beer in any state and he can't. *I'm assuming you're at least 26.
    • DoctorOetker 8y ago
      ... and listen MC++ all night long
• TheRealPomax 8y ago
  But why does the title focus on the person's age, instead of their skill? This should just read "Grad student finds classical alternative to quantum recommendation algorithm". Sure, he's young, but that's also 100% irrelevant to the actual work presented.
  • SimbaOnSteroids 8y ago
    It may not seem as noteworthy to the HN crowd given the demographics, however his age makes it all the more impressive.
    • TheRealPomax 8y ago
      What makes it impressive is that this is a grad student. By all means, compound that in the article by going "it's a teenager" but calling an 18 year old going on 19 a teenager is kiiind of pushing it for the sake of getting more clicks. Yes, he's doing amazing work at a young age, and that's super special. But from a result perspective, this is special because it's a grad student doing the work that usually happens at the phd or faculty level.
  • Doradus 8y ago
    His youth is remarkable, so they remarked on it. I'm not sure what about this troubles you.
    • TheRealPomax 8y ago
      Given the audience of the magazine in question, writing the headline to focus on how young he is (which tells us nothing in relation to quantum computing) instead of the fact that this is a grad student (which DOES tell us something: it gives readers a frame of reference in terms of this person's academic knowledge and skillsets) is disappointing at best, and clickbait at worst.
  • panic 8y ago
    Because it makes more people click on the link.
• rurban 8y ago
  I don't get why they don't just prepare the dataset for optimal search beforehand, as done in compgeom, like a quadtree or voronoi or in this case clustering into k regions. K dimensions are not so hard to handle. Then search will always be logarithmic. Even Google prepares it's datastructures for fast queries, a reverse index.
• carbocation 8y ago
  Has anyone started an implementation of this yet in python, go, rust, etc?
  • DoctorOetker 8y ago
    From the paper: "Second, while the recommendation system algorithm we give is asymptotically exponentially faster than previous algorithms, there are several aspects of this algorithm that make direct application infeasible in practice. First, the model assumptions are somewhat constrictive. It is unclear whether the algorithm still performs well when such assumptions are not satisfied. Second, the exponents and constant factors are large (mostly as a result of using Frieze, Kannan, and Vempala’s algorithm [10]). We believe that the “true” exponents are much smaller, but our technique is fairly roundabout and likely compounds exponents unnecessarily. These issues could be addressed with more straightforward analysis combined with more sophisticated techniques."
• HarmlessHacker 8y ago
  Loooool
• kbatdorf 8y ago
  Maybe now Netflix will show me titles I'm actually interested in.
  • the_new_guy_29 8y ago
    Not enough content on netflix unfortunetly
• hi41 8y ago
  This is amazing and he is just 18 years old!
• known 8y ago
  50% of land is uninhabited
• jaddood 8y ago
  From the paper, > The only difference between Theorem 1 and its quantum equivalent in [13] is that the quantum algorithm has no ε approximation factors (so ε=0 and 1/ε does not appear in the runtime). Thus, we can say that our algorithm performs just as well, up to polynomial slowdown and ε approximation factors. With ε being the accepted margin of error, theorem 1 being the algorithm produced by Tang, and [13] being a reference to Kerenidis and Prakash's quantum algorithm kept here in the quote for fidelity of quoting. This means that this algorithm is not really a substitue for the quantum algorithm because it will require a level of error to be accepted (something which might work in recommendation engines, but not necessarily outside that context) and it still has polynomial slowdown over the quantum algorithm. One thing to note is that not all quantum algorithms will perform exponenttially better than their classical counterparts. Particularily, some quantum search algorithms perform only quadratically better than the classical search algorithms. This means that even if an exponential speedup was not achieved by quantum computers, (which it still is because of the ε factor meaning they don't give the same results) it is expected that they still achieve polynomial speedup as they do in this case. In conclusion, stating that this algorithm threatens the prospects of quantum computation is probably an exageration.
• estomagordo 8y ago
  When I was 18, I could operate an oven.
• dingoegret 8y ago
  Chinese geniuses have done it again
• Elrac 8y ago
  I would have liked to read this article, but the page refuses to load in my bog-standard Mozilla browser. Ironically, there's an article in HN today about "The Bullshit Web." This is exactly what that article is about. Apparently Quanta Magazine is trying to do something clever, and that "clever" thing is stopping their content from reaching me.
  • suluke 8y ago
    Since I really had trouble finding a way to read the article (source seems to have depublished it?) I just wanted to leave a small how-to on how I succeeded eventually: - Look up the page in wayback machine - Open the first snapshot - JS seems to delete the content immediately - Open developer tools - Reload the page - View the HTML response in the response preview window Bullshit Web it is Edit: Article seems to be back online now
• newyearnewyou 8y ago
  Can anyone explain the significance of this in a few sentences for the non-expert? I read the article but am struggling to understand.