Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quantum computers: amazing progress, but probably false supremacy claims

gilkalai.wordpress.com

Post reply on HN
Print view View original

31–40 of 76 posts

Re: Quantum computers: amazing progress, but probably false supremacy claims

#31

Post by shroedingaway »

schoen wrote: post #23
shroedingaway wrote: post #18

Earlier quoted context omitted.

No that's the funniest aspect of the Google result. They barely have any control over what their gates do. Gil makes this point, but doesn't call it out: they're claiming supremacy by turning the challenge around. "You can't classically simulate our device (which largely does it's own thing because of issues)." A kid shoots an arrow at a target. The arrow hits the haybale, but not the target. Suddenly the kid yells "…

Scott Aaronson's description of the result made it out to be more subtle. If I understood it properly, it might be more like the kid shooting 20 arrows, which all form a particular pattern around a point that the kid can't choose or control at all. Now a regular archer can readily choose a particular point, in a way that the kid can't, but can't produce the sort of pattern that the kid does with nearly as much accura…

> Or to make a less specific analogy, there is something about the kid's archery that regular archers can't replicate with their archery skills, but it's not really something that anyone would traditionally have described as "skilled archery".

Yes, I'd call that a fair description.

Re: Quantum computers: amazing progress, but probably false supremacy claims

#32

Post by mlthoughts2018 »

doubleunplussed wrote: post #24
quanticitya wrote: post #12

If quantum supremacy was not possible, wouldn't that mean that something is wrong with our physics understanding? So when people say quantum supremacy is impossible, do they say that the device itself is extremely complicated to build (like an earth to moon elevator for example), or that quantum supremacy isn't allowed not even in principle?

Not necessarily. I believe it's the case that for every quantum algorithm that is exponentially better than the best known classical algorithm for solving the same problem, it is not proven that an equally good (up to polynomial overhead) classical algorithm does not exist. Therefore, one way quantum computers could fail to be exponentially better than classical ones, without us having to revise physics, is that ther…

I remember seeing a lecture by Aaronson where he described the idea of a “relativity computer” where you set a computer running on some exponential task, but then hop in a spaceship and fly off at nearly the speed of light, and come back to find the answer in an amount of time only polynomial for you.

He “debunked” this by mentioning to do it you’d potentially need an exponentially large supply of fuel to accelerate yourself to a speed exponentially close to the speed of light as the problem to solve grows more complex.

I wonder if something similar could be true about quantum computing. Maybe it is theoretically possible to solve problems polynomially that can only be solved exponentially in a classical computer. But maybe it requires “exponentially more” of some resource, like a power supply to power the physical devices needed to do an amount of error correction to make it physically realizable as the problem size grows.

Would it be possible for the Church-Turing thesis to be false mathematically, but for the amount of quantum error correction to require an amount of physical resources that grow prohibitively and prevent it from being practically possible (like the fuel limitation prevents the otherwise physically possible relativity computer)?

Re: Quantum computers: amazing progress, but probably false supremacy claims

#33

Post by shroedingaway »

AlexCoventry wrote: post #26
shroedingaway wrote: post #15

Earlier quoted context omitted.

As a licensed quantum computologist (um... not really, but I do work for a major QC effort)... your skepticism is not misplaced. I can only speak for my place of work (not publicly) and pass along scuttlebutt... but, my understanding is that it's largely the same everywhere. Some efforts have tight budgets, some have billions backing them; but QC research is hugely expensive with more unknowns than knowns. People giv…

That sounds demoralizing and corrosive. What keeps you there?

I fired my therapist for asking that too often. Not really. But that is uncomfortably close to the truth.

Re: Quantum computers: amazing progress, but probably false supremacy claims

#34

Post by the8472 »

undersuit wrote: post #11

My level of expertise on quantum computing is low. The announce of the imminent advent of the Quantum Computer seems to be recurring every few months these last few years because it's a moving target. HN recently featured an article about a supposed quantum-only algorithm being applied to normal computing. Algorithms are a vastly larger space to explore than general computing paradigms. Computer hardware is still adv…

> The announce of the imminent advent of the Quantum Computer seems to be recurring every few months these last few years because it's a moving target.

That's mostly misreporting by the media and perhaps d-wave overselling their capabilities. If you actually listen to experts they're far more guarded in their statements.

Re: Quantum computers: amazing progress, but probably false supremacy claims

#35

Post by rolltiide »

Am I understanding correctly that the whole idea is to get a bunch of qubits in one machine and then have them evaluate every possibility in a super dumb way but count on them to get the desired result faster than a transister based machine that knows what its looking for?

And that we currently just can’t coordinate that many qubits at once and also cant keep them cool long enough to function??

This seems kind of ridiculous idk...

Re: Quantum computers: amazing progress, but probably false supremacy claims

#36

Post by jcoffland »

gregfjohnson wrote: post #22

As far as QC scalability, the thing I wonder about is the cost of maintaining full entanglement of N qubits as N grows large. The debbie-downer perspective would be that for each additional qubit you add, you effectively double the cost of isolation from the environment, quantum error correction schemes, etc. So, while compute power for quantum algorithms grows exponentially in N, so would the cost of operating the m…

> The debbie-downer perspective would be that for each additional qubit you add, you effectively double the cost of isolation from the environment, quantum error correction schemes, etc.

This is exactly my concern with quantum computing. Not only might it get more expensive but it may simply be limited by the laws of our universe. If the difficulty of entangling and isolating qbits increases exponentially with the number of bits then quantum computing could be a dead end. You may still get some nice results of you can decrease the exponent. I'd love to be proven wrong.

Re: Quantum computers: amazing progress, but probably false supremacy claims

#37

Post by anoncareer0212 »

mlthoughts2018 wrote: post #29
kevinwang wrote: post #3

Discussion around the matching bullish take: https://news.ycombinator.com/item?id=21053405

What do you mean by “matching”? The bullish take is just a different take that presumably must develop answers to the points of this post to remain a viable belief option. It actually strikes me somewhat as editorializing to place this link here with the wording you chose. If anything in your linked discussion actually addresses the substantive points of this post, why not link to those items specifically? What would…

hmu, u need some bud

Re: Quantum computers: amazing progress, but probably false supremacy claims

#38

Post by mlthoughts2018 »

anoncareer0212 wrote: post #37
mlthoughts2018 wrote: post #29

Earlier quoted context omitted.

What do you mean by “matching”? The bullish take is just a different take that presumably must develop answers to the points of this post to remain a viable belief option. It actually strikes me somewhat as editorializing to place this link here with the wording you chose. If anything in your linked discussion actually addresses the substantive points of this post, why not link to those items specifically? What would…

hmu, u need some bud

No I just think people eager to push for the positive result interpretation from the Google paper rush to astroturf, and you can reasonably detect it even from limited text like this case.

Re: Quantum computers: amazing progress, but probably false supremacy claims

#39

Post by deevolution »

lawrenceyan wrote: post #4

The usage of the word “supremacy” is probably the primary thing that rubs people the wrong way. When I first heard of it myself, it did feel a little strange. Doing some research into it though, it seems like the phrase and usage of quantum supremacy is pretty well defined and accepted by and large within the physics community. Supposedly the coiner of the term believed “quantum advantage” wouldn’t emphasize the poin…

> basically just about definitively showcasing a problem where using a classical computer would take super polynomial time, but with a quantum computer ends up taking some significantly lesser time complexity.

Quantum computers should only really be able to outperform classical computers on quantum specific problems.

Re: Quantum computers: amazing progress, but probably false supremacy claims

#40

Post by greatquux »

mlthoughts2018 wrote: post #32
doubleunplussed wrote: post #24

Earlier quoted context omitted.

Not necessarily. I believe it's the case that for every quantum algorithm that is exponentially better than the best known classical algorithm for solving the same problem, it is not proven that an equally good (up to polynomial overhead) classical algorithm does not exist. Therefore, one way quantum computers could fail to be exponentially better than classical ones, without us having to revise physics, is that ther…

I remember seeing a lecture by Aaronson where he described the idea of a “relativity computer” where you set a computer running on some exponential task, but then hop in a spaceship and fly off at nearly the speed of light, and come back to find the answer in an amount of time only polynomial for you. He “debunked” this by mentioning to do it you’d potentially need an exponentially large supply of fuel to accelerate…

The universe may not see any difference between the two states!
Post reply on HN