Major Quantum Computing Advance Made Obsolete by Teenager (2018) | Hacker News Reader

Major Quantum Computing Advance Made Obsolete by Teenager (2018)

quantamagazine.org

113 pointsg42gregory44 comments

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.

Young minds have less systematic tunnel vision.

Or perhaps, less indoctrinated minds...

*her mentor :)

Source: https://ewintang.com/

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.

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

Young people have less memory and running “threads” dedicated to adult things. They will not mind branching out to go down a rabbit hole, which will cost time and mental resources.

It's probably a mix of a lot of effects, but if memory serves me right, in management science its a bit of a non-result that local maxima in decision making/search space is a real thing, so TRULY diversifying a group of people looking at a problem can kinda bump you out of that. This explains why sometimes a complete novice can meaningfully contribute in ways like this -- you haven't been taught/trained/inculcated that "this will never work," and are also probably more willing because of it to try outlandish/left-field things that maybe an established person may not.

One interesting thing to think about in the context of this is the way we approve budgets for basic research, which often is hostile to this very sort of contribution. If you are applying from grants from NIH, for instance, the surest way to succeed is to do things or make it look like things that are the sorts of things that NIH funds to begin with, which is a bit of a paradox if the whole reason you are funding this stuff in the first place is to try to nudge along some breakthrough in a traditionally intractable domain where many people have taken a stab at it.

One thing that is very hard if not impossible for the human mind is to 'unsee' stuff. Once you have learned a certain method or theory it becomes almost impossible to think creatively about a problem and attack it from different angles, because you already know what works.

Repeated exposure also reduces skepticism. The writing world has already long known this, you can not proofread your own work. You will read 50 times over a silly mistake without ever noticing it. Software engineering is understanding this more and more through code review as well, but academia is slow on the uptake. Groups or individuals will spend months on their work without anyone else to check on it.

The young are not yet cursed with knowledge. They can look at things with a fresh look. They can poke holes in stuff others are 'reading over', and find completely new approaches.

As others have said, a large part of it is probably due to 'belief systems' we develop and don't question, so reduced creativity.

I think another reason that is often overlooked in this kind of discussion, is that our society offers much greater incentives for young people to discover something new. If you're at an advanced age, there are way less opportunities to still have the 'leisure' to work on something fundamental, because our expectations are that ppl generally come up with their big idea before the age of about 30.

So perhaps it is a self-reinforcing mechanism.

To be fair, in this case and I suspect in many others, the popular article has greatly oversold the importance of the problem. When you are considering a problem that only a handful of others have ever looked at, there's no reason why a new person shouldn't find a new approach. of course, it helps when she's a genius.

True. Adding an extra, capable person to an incredibly small number of people who've considered a problem is a huge increase in total throughput on it. Might be that there isn't much more to it.

Aaronson is probably better than average at assigning problems, and of course he'd be assigning them to young people. Simultaneously, there are several intelligence tests for which performance peaks in many people before 20 [0]. Someone who is experienced and knows what to do combined with a very sharp young person at the peak of their raw ability may be the ideal academic team.

[0] https://blogs.scientificamerican.com/beautiful-minds/when-do...

I would think they are more willing to spend time on something hard (and that they don’t know is impossible, see the book Uncle Petros and Goldbach's Conjecture).

Older people have to actually make progress in their careers and make money so they are much more hesitant to “waste” time on a major open problem.

You’re overthinking this maybe. Every problem that is solved, is solved by an individual, not the group of established folks working on it. Hence, even if the age of the solver is evenly distributed, you’ll have hard problems being solved by young people. And that’s what gets remembered.

To add to the anecdotes, an undergraduate proposed the structure of diborane off the cuff while doing his homework research on Boron so the legend goes.

https://en.m.wikipedia.org/wiki/Diborane

I too wonder if certain "unsolvable" problems could be solved by bright minds if presented as something as mundane as "homework".

The 4 minute mile was thought to be impossible for a long time. Then within a year of a it being broken - countless other athletes also ran 4 minute miles because they now knew it was actually possible.

It can be surprising just how effective limiting beliefs can be.

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.12... [2]: https://arxiv.org/abs/1811.00414

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?

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.

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

Scott Aaronson's blog post about this: https://www.scottaaronson.com/blog/?p=3880

HN at the time: https://news.ycombinator.com/item?id=17519001

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

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.

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.

I think the identification of "discrete" with "computational" is not very useful. There is such a thing as an analogue computer after all.

We'd need to look at analogue computers in a lot of detail to figure out in what sense they count as computers.

I am taking the computer science defintion, ie., a universal Turing machine. All computable functions are over discrete inputs and outputs.

I suspect either (1) the sense of computer at-work in "analogue computer" might just be problem-relative, ie., it is just that someone uses this device to help them compute something; or (2) that analogue computers do compute computable functions (ie., their computation is discrete).

I suspect it is the latter, ie., the output and input to an analogue computer is discrete. As I'm pretty sure there isnt any coherent sense of "computer" as defined for continuous "input".

There are a lot of different ways of understanding what exactly it is that makes quantum computers more powerful. There isn't one simple clean answer.

As a counterpoint to the "it's the bigger state space" idea, note that quantum computations over a polynomial number of qubits with a polynomial number of steps can be simulated by a classical computer using polynomial space (but not polynomial time). So the quantum state space isn't "intrinsically huge" or beyond-the-reach-of-classcal; at least not in that particular sense. Also note that every quantum state we will ever make will be generated by some tractable number of operations done with a tractable amount of precision. So the reachable in practice states are discrete and compressible into a tractable number of bits [the bits being a description of the operations used to produce them].

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

Maybe he was scared he may solve it and didn't want to live through apocalypse.

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.

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.

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.

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.

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.

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

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

Any relationship between this and integer factoring?

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.

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.

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.

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.

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.

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

Reply on news.ycombinator.com