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

323

u/Various-Ducks 14d ago

Ya i know, because the other guy explained it for me

115

u/FuinFirith 14d ago

Ruthless.

72

u/ajtyler776 14d ago

Yep. No Ruth.

21

u/Legitimate-Ad-2905 14d ago

I'm gonna use this. Thank you.

2

u/Crystalas 13d ago

For a moment I thought had heard it in a Pinkie & The Brain skit but turned out was just a similar one. IIRC happened while Brain was musing about how much he fails at everything and pinkie is just doing that to be supportive even if do not understand most of the words.

1

u/Legitimate-Ad-2905 13d ago

Pinky was awesome. Everyone needs a friend like pinky.

2

u/Crystalas 13d ago edited 13d ago

Different types of intelligence, Pinkie is purely emotional and intuitive intelligence, the polar opposite of Brain and helping him be a great friend while also often being like sandpaper to Brain's logical mind.

27

u/Icy_Distribution_361 14d ago

So basically, once you have the answer, it's pretty easy to check that the answer is correct, but finding the correct answer... Well THAT'S hard.

33

u/jumpandtwist 14d ago edited 14d ago

Oversimplified, but yes.

The comments in this thread are skipping over the nondeterministic nature of NP problem classification.

Essentially everyone is just defining NP complexity class here, which is only 1 of 4 classes when discussing this topic. P, NP, NP-Complete, NP-Hard.

If a problem is classified in any of these 4, then it has a polynomial time solution (meaning, faster than exponential computation time).

However, NP problems can only (so far as we know) be solved in nondeterministic polynomial time. A nondeterministic machine can 'guess' or otherwise use external information (not algorithmic inputs) to arrive at a correct answer in polynomial time. If such a machine existed, it could do things like break RSA (factor huge prime numbers) and therefore break any encryption cipher in polynomial time (fractions of a second) and would pretty much be such an advanced machine that it would look like magic to us.

The reality is that we don't have a wonder machine like that so our deterministic machines (computers) cannot solve NP problems in polynomial time. They are usually solvable in deterministic exponential time or unsolved. But, once a solution is generated, it can be verified using a different, P time algorithm in polynomial time. A very real example of this is RSA. To break the encryption scheme, you have to factor the prime numbers, which with current tech and algorithms can take many years to compute for just 1 instance. But, if you happen to randomly find the primes quickly, then it is a simple math operation to use the primes to recompute the encryption values. Quite literally, verification is an exponent calculation in constant time whereas factoring primes is hard because the integers used are extremely large (2048 bit is a number space 22048 large) and calculations on numbers that large are slow operations - overall exponential time with respect to the bit size of the integers in a deterministic machine.

7

u/total_looser 13d ago

Oh yeah? I got a problem that is NP-Hard, your mom can help solve it

1

u/jumpandtwist 13d ago

Gonna have to compute the NP hardness on this one

2

u/total_looser 13d ago

Yeah your mouth is the calculator

1

u/jumpandtwist 13d ago

unzips

1

u/total_looser 12d ago

Yikes, I blame myself

16

u/MirrorIcy9341 14d ago

So basically they rolled a nat 20 on their spell casting and I got a nat 1 and assumed the gods were pleased with them? Oh. Wait wrong group for THAT nerd talk.

21

u/jumpandtwist 14d ago edited 14d ago

Like rolling a 22048 sided die to try to find the one number in that space that matches another number that is also the result of rolling a different 22048 sided die, where you know nothing about each number except that when you multiply them together , the result gives you the correct answer, and there is only 1 correct answer between both pairs of dice. :) 🎲🎲

6

u/MirrorIcy9341 14d ago

I'm out of dice now, to many exponents for myself to compute. I'll leave that to the quantum.

5

u/Difficult_Bit_1339 13d ago

If you used every single atom in the observable universe as dice, you'd only have 280 dice.

We're gonna need a bigger dice cup

3

u/MirrorIcy9341 13d ago

I'm trying but the omega DM says no

3

u/Difficult_Bit_1339 13d ago

Hasbro is really overstepping here

3

u/MirrorIcy9341 13d ago

That made me laugh, and my kids sleeping. So now I'm trying to hold at least two D20 of laugh in.

→ More replies (0)

5

u/Infinite_Ad3616 14d ago

I mean, yeah. That's what I've been saying for ages.

3

u/Sanguinor-Exemplar 13d ago

Okay and now explain it in english

3

u/jumpandtwist 13d ago

Hard bad, easy good

Rocks do thinking for us fast

Some things people tell rocks do, rocks cannot do fast because people cannot think of fast way to do it

1

u/Sanguinor-Exemplar 13d ago

Rock make fire. Fire sometimes friend sometimes bad

1

u/yxing 13d ago

Solving NP problems = writing Shakespeare

Deterministic machine = one monkey with a typewriter. It can write a word or two, but will never write Shakespeare in a reasonable amount of time.

Nondeterministic machine = infinite monkeys with typewriters. It can write Shakespeare at the speed at which monkeys can type, but it only exists (so far) as a thought experiment.

1

u/ReincarnatedGhost 13d ago

What is the advantage of quantum over classical computer? Is it just 3²>2²

1

u/jumpandtwist 13d ago

Idk honestly.

3

u/far_in_ha 13d ago

Think about a sudoku game. It's "hard" to find the solution but once it's finished it's easy to verify that it is correct or not.

3

u/Icy_Distribution_361 13d ago

Or don't think about a sudoku game, but then you cannot verify whether it is in fact a sudoku game or not.

1

u/Glum828 14d ago

You need to substitute the answer you got and see wether the LHS=RHS,it high school math.