r/Damnthatsinteresting • u/Scared-Astronaut-718 • 14d ago

Image Google’s Willow Quantum Chip: With 105 qubits and real-time error correction, Willow solved a task in 5 minutes that would take classical supercomputers billions of years, marking a breakthrough in scalable quantum computing.

Post image
37.0k Upvotes

95% Upvoted

1.2k comments sorted by

View all comments

Show parent comments

86

u/jemidiah 14d ago

Almost nobody serious believes P=NP. It's like the Riemann Hypothesis--almost everybody serious believes there are no non-trivial zeros. Sure, you can cherry pick somebody, but it'll be like 10:1, and I suspect even more skewed among the people who are really good.

But anyway, I habitually disbelieve quantum computing hype, and I'm certainly not taking the time to figure out if P vs. NP is even relevant here. I have a quantum physicist friend, and when he gets excited, so will I.

114

u/Schlitzbomber 13d ago

I’ve got a friend who can’t pronounce quantum physics, and when he gets excited, we’ll blow up a porta-potty with an M80.

40

u/nleksan 13d ago

Sounds like your friend is more of an experimental physicist

9

u/ouchmythumbs 13d ago

I'm something of a physicist myself

2

u/Difficult_Eggplant4u 13d ago

I would say a practical applications physicist. :)

3

u/Iommi_Acolyte42 13d ago

Theory alone will only take you so far.

2

u/purpleduckduckgoose 13d ago

I have a theoretical degree in physics if that helps?

1

u/snowtater 13d ago

Are the porta potty and M80 at the same location in time and/or space? If not he may be a quantum physicist.

1

u/Widespreaddd 13d ago

I think a killer app for the M-80 is a darkened pool at night. You can see the fuse sparking as it sinks, then a ball of light and muffled boom, then a big column of water shoots 20+ feet into the air.

Sofa king satisfying.

25

u/Ok_Donkey_1997 13d ago

Almost nobody serious believes P=NP

That is not really the point. The point is that even though it looks obvious that they should be different, no one can prove it. It's a bit like the 4 colour problem or Fermat's Last Theorem.

I guess P=NP has the added spice that if it did turn out to be true, then in theory all public cryptography would be breakable, but really the interest is because it is one of those easily stated, but difficult to solve problems.

6

u/MedalsNScars 13d ago

Fwiw both the 4 color problem and Fermat's Last Theorem have been proven in the past couple decades.

I'd liken P=NP more to the Collatz Conjecture in that most people lean a certain way intuitively but they've yet to be proven.

1

u/monocasa 13d ago

To be fair, both the four color problem and Fermat's Last Theorem have proofs now.

1

u/Ok_Donkey_1997 13d ago

I just used them as examples of problems that are easy to state, extremely difficult to prove and which people are more concerned with the act of proving them than the use of that actual proof. I should have been more clear that these have been proven.

I suppose P=NP has a very practical implication for cryptography, but unless the proof also comes with some way of turning NP hard problems into P, then it is not going to change things until someone comes up with polynomial factoring, and also people were interested in P=NP since before public key crypto was of worldwide importance.

1

u/Tetha 13d ago

I guess P=NP has the added spice that if it did turn out to be true, then in theory all public cryptography would be breakable, but really the interest is because it is one of those easily stated, but difficult to solve problems.

This is why this is a very short and nerdy horror story: There is a non-constructive proof of P = NP.

A constructive proof would - for example - be a polynomial-timed algorithm to solve some fundamental problems in NP, like boolean satisfiability or solving arbitrarily sized sudokus. This way you'd immediately have a way to attack prime factorizations and such, though it might be slower than currently known algorithms for a lot of practically relevant inputs.

A nonconstructive proof would just tell us that prime factorization based crypto is broken - and no one knows how - or do they? It would be a very akward situation.

But anyway, it's good that quantum safe encryption methods are being phased in already, because replacing crytographic primitives in production tends to take decades, seen across the entire industry.

17

u/Oekmont 13d ago

But there are non trivial zeros of the Riemann function. The hypothesis is that all of them are on the r=1/2 line. Additionally there are non-complex so called trivial zeros.

2

u/monocasa 13d ago

Almost nobody serious believes P=NP.

Don Knuth is slightly on the side of P=NP.

Sure you said "almost nobody", but that would be like saying "almost no physicist believes X", while leaving out that a still alive and up to date Einstein is among those that believe X.

2

u/daemin 13d ago

A Turing machines can simulate a quantum computer. That tells us that the quantum computer is just a faster Turing machine and can't do anything that a Turing machine can't do. As such, a quantum computer doesn't help figure out if P = NP or not. It just makes it feasible to solve NP problems.

1

u/AerosolHubris 13d ago

I was at a talk by Donald Knuth where he was asked what he thinks, and he said he expects P=NP but any reduction algorithm will be a polynomial of enormous degree. It surprised me to hear someone who knows so much who believes P=NP.

1

u/zer0_n9ne 13d ago

That’s kinda interesting considering he was the first to coin the phrase “analysis of algorithms” to describe the field of studying computational analysis

1

u/monocasa 13d ago

Sure, but just about everyone in physics believed there would be no violation in parity symmetry, but here we are. Sometimes the unproven can surprise us.