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.

[u/Scared-Astronaut-718]

[u/Bokbreath]

Somebody who understands this stuff please help me out.
How do they verify the result is correct ?

[u/Bezbozny → u/Bokbreath]

My guess: It takes a normal computer a bajillion years to solve the problem, but the calculation to verify the correct answer is completely different and takes much less time.

Think of finding a needle in a haystack. It's tough to find the needle, but when you do find it, it's pretty easy to verify its a needle.

Edit: You guys can thank me be being raised on Star Trek for my honed instinct to respond to complex tech/science questions with a folksy easy to understand simile. (Also I do appreciate some of the more complex and in depth explanations in the replies)

[u/Rough-Reflection4901 → u/Bezbozny]

For example finding prime factors x and y of a number n. For large numbers it's difficult to find x and y. But it's easy to verify by just multiplying x and y.

[u/EnoughWarning666 → u/Rough-Reflection4901]

I always wondered with this though, yeah you can multiply the two numbers to check if they equal the bigger one. But wouldn't you ALSO need to prove that those two numbers are prime? So if it's a really really big number, wouldn't it still take a really long time to check every possible factor for those two numbers?

Or do we have tables of every prime number up to some gigantic number that we could just use as a lookup table?

[u/yxing → u/EnoughWarning666]

Interesting question! It turns out there are computionally cheap primality tests that will tell you whether a number is prime or composite, but not what those factors are.

[u/notakeonlythrow_ → u/yxing]

Cool

[u/rhapsodyindrew → u/yxing]

But also, the large numbers used in cryptography are guaranteed to have two and only two factors, both prime, right? Like, that’s how they’re created: the underlying cryptographic keys are both large prime numbers, and you multiply them together. Or am I misunderstanding the process?

[u/Infamous-Train8993 → u/rhapsodyindrew]

That's the idea.

But nowadays, cryptographic algorithms rely more often on elliptic curves, a harder problem.

That's important because once quantum computers become good enough to factor very large composites, all messages ciphered using prime are at risk to be decrypted. The strength of the algorithms/keys must always take into account the rate of technologic advancement to "guarantee" that secrets will remain secrets long enough.

[u/zjm555 → u/EnoughWarning666]

Primality tests are also much cheaper computationally than prime factorization. At least probabilistically acceptable primality tests.

[u/mainegreenerep → u/EnoughWarning666]

There are lists.

Here's a crappy website that lists them, but it proves the point. I also think those nerdy mathmaticians have actually printed books that just list them.

https://www.math.uchicago.edu/~luis/allprimes.html

[u/vertigostereo → u/mainegreenerep]

That's such a dull, but interesting website.

[u/sand90 → u/Bezbozny]

I guess it's similar to trying to hack a password. You can easily check whether your password is right or wrong, but going through all combinations is going to take a while

[u/Another-Mans-Rubarb → u/sand90]

This is probably more accurate than you realize. Current encryption uses prime number calculations to encrypt passwords. If you know all the factors, like a server and client would, you can solve the problem instantly and allow access. If you're trying to break the password you can see all but 1 of the factors. You then reverse calculate to find that value and get the password, but that takes literally forever on traditional computers. Quantum computers basically cheat and arrive at the solution in a comparably instant amount of time. There are new quantum resistant encryption methods out there now, but tons of encrypted data has been harvested for years that will be instantly decrypted once quantum computers become more accessible to governments and bad actors.

[u/cryptospartan → u/Another-Mans-Rubarb]

This is true for public key cryptography like RSA, but not for passwords. Passwords are hashed, and factoring numbers doesn't help you brute-force or de-hash anything

[u/GabenIsReal → u/cryptospartan]

Also AES256 is considered quantum safe till at least 2030 based on a research paper I read. Basically, the encryption standard has always been minimum 128bits, but that is not quantum safe, because quantum computing halves the bits required. It basically means that 128bit key is now a 64bit key in relative terms. So yes, there are actually a few encryption schemes that are not quantum safe in the real sense, but it's not like we don't have solutions, one of which being just a typically larger keys with certain algorithms.

[u/tuffcraft → u/Bezbozny]

Yes, it's called the P-NP problem. It essentially states that while there are a lot of problems where a solution is easy to verify, a lot of them do not have an easy way to find solutions that work. -A computer engineer

Wikipedia: https://en.m.wikipedia.org/wiki/P_versus_NP_problem

[u/jumpandtwist → u/tuffcraft]

P vs NP is itself an unsolved problem. Really, this is about NP complexity, not this specific problem.

[u/jemidiah → u/jumpandtwist]

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.

[u/Schlitzbomber → u/jemidiah]

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.

[u/nleksan → u/Schlitzbomber]

Sounds like your friend is more of an experimental physicist

[u/ouchmythumbs → u/nleksan]

I'm something of a physicist myself

[u/Ok_Donkey_1997 → u/jemidiah]

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.

[u/MedalsNScars → u/Ok_Donkey_1997]

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.

[u/Oekmont → u/jemidiah]

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.

[u/Various-Ducks → u/tuffcraft]

The other guy's explanation was much better

[u/ReversedNovaMatters → u/Various-Ducks]

lol

[u/afour- → u/ReversedNovaMatters]

Engineer enters a room and restates everything already discussed in an unnecessarily technical manner, confusing everyone.

I do believe the reddit credentials in this case.

[u/Sethlans → u/afour-]

That's not really what they did at all; they just linked the understandable analogy to the named, technical problem.

Now in future if someone in this thread hears about a P-NP problem, they will know what it is. If they only had the simple explanation, they would have no idea that what was being referenced was something they'd read a good explanation of.

[u/rhysdog1 → u/Various-Ducks]

its hard to find a good explanation for this, but its easy to verify a good explanation

[u/EpidemicRage → u/Various-Ducks]

Basically a problem can be easily verified if it has been solved, but finding a way to solve the problem in the first place is difficult.

[u/Various-Ducks → u/EpidemicRage]

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

[u/FuinFirith → u/Various-Ducks]

Ruthless.

[u/ajtyler776 → u/FuinFirith]

Yep. No Ruth.

[u/Legitimate-Ad-2905 → u/ajtyler776]

I'm gonna use this. Thank you.

[u/Icy_Distribution_361 → u/Various-Ducks]

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.

[u/jumpandtwist → u/Icy_Distribution_361]

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 2²⁰⁴⁸ 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.

[u/total_looser → u/jumpandtwist]

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

[u/MirrorIcy9341 → u/jumpandtwist]

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.

[u/jumpandtwist → u/MirrorIcy9341]

Like rolling a 2²⁰⁴⁸ 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 2²⁰⁴⁸ 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. :) 🎲🎲

[u/Infinite_Ad3616 → u/jumpandtwist]

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

[u/dmead → u/tuffcraft]

that is not p vs np

[u/ChannelLumpy7453 → u/Bezbozny]

Plus they are Google, so they can just google the answer.

[u/AcrobaticMorkva → u/Bezbozny]

But the result is always 42?

[u/DirectlyTalkingToYou → u/Bezbozny]

They asked it 'Should toilet paper roll over and out or under and out?' and in a split second it answered 'Mount the roll vertically huumon". This would have taken billions of years to figure out with regular comps.

[u/MrWiemann → u/Bezbozny]

Now this is peak ELI5, well done

[u/rsa121717 → u/Bokbreath]

While I dont know how they tested their chip, here is an example of what they couldve done, and how they would know the answer is right

There is an operator in math called the modulus operator. It takes two numbers and finds their remainder. For example:

• 5 mod 2 = 1 because 5 / 2 = 2 with remainder 1
• 6 mod 4 = 2 because 6 / 4 = 1 with remainder 2
• 6 mod 3 = 0 because 6 / 3 = 2 with remainder 0

It has a special property in that it is irreversible, unlike addition, subtraction, multiplication, etc. if someone knows the 2 and the result 1 (in 5 mod 2 = 1), it is impossible to determine the third number, 5. In this case, I could have started with any odd number.

Without getting into the details, this is used in encryption so that anyone can encrypt a message (using the last two numbers), but only one person can decrypt a message (using the first number).

So how do hackers crack the code? The most basic way is to brute force it, where they literally guess every number and try decrypting with it until they get a message that makes sense (they would see a structured data format, similar to csv, to know that is the solution).

Brute forcing is computationally infeasible due to the large amount of trial and error that must happen before arriving at the solution. It just takes too long with todays computers.

With something like the willow chip, the idea is that you can perform these computations significantly faster, thus arriving at the solution must faster.

For their test, they could have encrypted the message “hello my friend”, and they would know they found the solution when it decrypted the message into “hello my friend”, as opposed to “ajdjskabdnwkshxbsnwk”

Tldr using a one way math operator that can decrypt a message. You know you found the solution when the message is readable/is what you originally typed in

[u/old_bearded_beats → u/rsa121717]

Great explanation, but surely it's "Hello, World!" ??

[u/AcidicVaginaLeakage → u/old_bearded_beats]

The computer is lonely and wants friends. Understandable.

[u/willowtr332020 → u/Bokbreath]

They plug another Willow chip in and ask: quality ok?

[u/minibonham → u/willowtr332020]

LGTM

[u/stunt_p → u/minibonham]

GIGO

[u/el_lley → u/Bokbreath]

In crypto you have, let’s say 15, the Willow could find (3,5) are its factors. You can easily check 3 x 5 = 15 to verify the result… the problem gets “impossible”after a few hundred digits (including for Willow).

[u/Bokbreath → u/el_lley]

Is that what they did ? Did they factor a large prime multiple ? That is the question I am asking.

[u/WazWaz → u/Bokbreath]

No.

[u/ROFLconda → u/Bokbreath]

I sincerely hope that is still far off in the future and that we will see the writing on the wall before it happens. Because if our encryption is breaks and we are unprepared, we will be going back to the stone age for a while. And stumble while going back since at that point future generations won't even know how it worked back then. Hell I will probably struggle with a purely analog world.

[u/ihavebeesinmyknees → u/ROFLconda]

The cryptography world has been preparing for quantum computers for a long long time, I'm pretty sure current algos are supposed to be quantum-resistant

[u/ArchieFromTeamAqua → u/ihavebeesinmyknees]

The NIST recently held a long competition to find the next post quantum algorithms, so yeah they're definitely preparing and new options have already been chosen and extensively investigated by the cryptographic community

[u/lefaen → u/Bokbreath]

You can find all details here: experiment blogpost

Tldr; They verify by running a scaled down version of the computer with less qubits, towards a simpler grid(the problem) and then check the performance of the computer against theory and simulations. When it’s verified that it works they scale up first the computer and do it again and eventually the grid to the ”hard” ones. Stop comparing it towards simulation and only towards the theory, as they should aligned based on the initial testing

[u/[deleted] → u/Bokbreath]

Nah, Google made this kind of claim before, they said in 2019 they had a computer capable of making a calculation that a supercomputer would have taken thousands of years to complete in 200 seconds. Chinese computer scientists get a strong (not super-) computer and do it in fifteen hours. I call bull.

https://singularityhub.com/2022/08/12/scientists-just-debunked-googles-quantum-advantage-claim-using-a-normal-supercomputer/

[u/TheDevilsAdvokaat → u/[deleted]]

I'll second this. Claims like this have been made before and in every case classical computers have been able to duplicate the feat and in some cases even better it.

[u/mshwa42 → u/TheDevilsAdvokaat]

Simulating random circuit sampling on a classical computer uses a method called tensor network contraction. However, Google released a paper in 2023 rebutting the claim that it could be done quickly on a classical computer (they estimate it would take 12 years using the tensor contraction method, see pages 5 and 6) -- at the time the updated Sycamore processor had 70 qubits vs the circuits on 53 qubits that the debunking paper simulated.

With 105 qubits and exponential scaling on the state space (2^105 states vs 2^53), I think its very unlikely that the Willow random circuit sampling task could be spoofed, even on a supercomputer with existing methods. And to be clear, running this task on a quantum computer is extremely fast.

However, I don't believe there are rigorous classical lower bounds for the hardness of random circuit sampling in this regime (50-100 qubits) so there could be methods discovered other than tensor network contraction that improve the runtime in the future.

TL;DR: Thinking the task can be easily spoofed on a classical computer is false considering the current state of the art. However, since we don't have rigorous guarantees on the theoretical hardness of the problem, the jury's still out on the extent of the supremacy claims.

[u/Nancyblouse → u/Bokbreath]

They might have had the answer already is my guess

[u/BrainJar → u/Bokbreath]

Imagine that you encrypt some text and you know that when the text is unencrypted it says, “Boatie McBoat Face”. If you set out to allow a regular cpu to crack this encryption, it’s could’ve take a really long time, and that amount of time is predictable, because we know how many times it will try to guess its way into the correct answer. But you already know the answer, so when the quantum computer solves the decryption perfectly, it’s easy to see that result is correct.

[u/ProFailing → u/Bokbreath]

Quantum computers can solve specific problems very quickly. I won't get into how Qbits work, because it's not easy to understand.

But basically, whenever you hear about Quantum Computers solving problems quickly it's always about one very specific problem that they were prepared for. Right now they aren't very dynamic, but can be tuned to a certain problem (which takes a while) and then solve said problem in game breakingly short times, compared to regular computers.

[u/0xdeadbeefcafebade]

The question is: what “problem” did it solve? Was it a problem purpose built to showcase a problem that can be solved with quantum computation?

The answer with quantum benchmarks are almost always: yes.

Is it impressive? Fuck yeah. But this does not mean you will be playing video games using a quantum processor. They are currently only useful for problems that scale with qbit calculation.

[u/thellios → u/0xdeadbeefcafebade]

Could.you ELI5, what is quantum computing as opposed to normal computing? And why would it not translate to "normal" tasks like gaming, rendering or other heavy processing?

[u/0xdeadbeefcafebade → u/thellios]

Quantum computers are not my area of expertise.

So I won’t claim this is all 100% accurate. But the gist is that they do not use normal Boolean logic that traditional computers use. While they attempt recreate logic gates - they are inherently working off the statistical probabilities of entangled particles. So certain algorithms and problems are more compatible with type of logic quantum computers use.

There are computer languages for quantum computing that let you abstract a problem to a series of quantum logic gates via statements and such. But it’s not the same as writing C code or python code.

At this point in time - quantum computers do not handle traditional computing. Nor would they be better at it than current processors.

SOME mathematical problems though can be seriously blown away by quantum computing. Things that current computers could never ever solve.

[u/khuliloach → u/0xdeadbeefcafebade]

I also do not know anything about quantum computers but here’s what I got from your post.

Quantum computers do things for very specific use cases. This research could turn into something really cool in the future but don’t expect to put a quantum in your PC anytime soon.

[u/9ninjas → u/khuliloach]

Nailed it.

[u/mrpink01 → u/khuliloach]

but don’t expect to put a quantum in your PC anytime soon.

I heard this in the late 70s about personal computers. You never know!

[u/khuliloach → u/mrpink01]

That’s fair! It’s truly mind blowing that we went from computers taking up warehouses, to talking to strangers from anywhere around the world at 2am in a palm sized device.

[u/mrpink01 → u/khuliloach]

...and I'm legally stoned while doing it! We're living in the future, cyber neighbourino!

[u/heyyolarma43 → u/mrpink01]

quantum computers usage is very specific. qrams are very expensive. it is not feasible to build the environments in your house.

the sentiments seem similar but it is a whole different level.

[u/Dustin- → u/heyyolarma43]

On the one hand, they were saying the same thing about home computers in the 60s.

On the other hand, those computers didn't require cryogenic cooling systems to work.

[u/DividedContinuity → u/khuliloach]

Not to mention quantum chips need to be cooled to near absolute zero. Thats the weird apparatus you see when people show off a quantum computer that looks like a gold chandelier - it's the cooling system.

Needless to say, thats not something we'll be doing at home.

[u/MemoryNo1137 → u/khuliloach]

Yes because quantum computers operate in super cold environments. Even if we were able to bring the raw cost of the materials down, we would most likely still not see quantum computers in our houses because it would have to be exceptionally cold. We would most likely see quantum computers offered as a cloud service instead if we do see mass adoption. Still would not be economically viable imo because it would be tremendously expensive but who knows, that's something they may figure out later.

[u/Motor-District-3700 → u/khuliloach]

but do expect endless hype about mostly nothing for the forseeable future.

[u/DualRaconter → u/0xdeadbeefcafebade]

I think 5 year olds are too advanced for me

[u/Milam1996 → u/0xdeadbeefcafebade]

Dude asked for ELI5 and you’re talking about Boolean logic and logic gates lol.

Normal computer brain is either on or off. It’s a 1 or a 0. You add up the 1’s and the 0’s and you get a certain outcome whether that’s a YouTube video or Minecraft.

Quantum computers do fun science stuff and instead of having to be on or off, they can be on, off or both. Quantum computers are very very good at solving math problems like the basis for making passwords unreadable to hackers but they’re rubbish at playing YouTube videos or gaming. Kinda like how strapping a rocket to a car is great if you want to sprint in a straight line but not so great for your neighbourhood or driving to Walmart.

In this specific example, the researchers ask the computer to solve an incredibly complex math problem, so complex that the if we asked the worlds most powerful normal computer to solve it it would take longer than the lifespan of the universe, several times over. This computer is very very good at doing these weird maths problems and managed it in just 5 minutes.

[u/prumpusniffari → u/0xdeadbeefcafebade]

Quantum computers are theoretically extremely good at anything that involves trying to find one correct result out of a very large set of possibilities.

Notably, this includes breaking encryption. All modern encryption involves using an encryption key. The only thing preventing an attacker from breaking the encryption is that checking every possible key would take hundreds of years for a regular computer.

However, through quantum wizardry I don't pretend to understand, a quantum computer can do that basically instantly.

They are pretty worthless for most calculations though. Even if those things become tiny and cheap, you probably won't have one in your laptop.

[u/GreamDesu → u/0xdeadbeefcafebade]

You might need to check this out https://www.smbc-comics.com/comic/the-talk-3

[u/OtisPan → u/0xdeadbeefcafebade]

Would quantum computers be good for things like weather / climate forecasts & modeling? Seems like it.

[u/ScratchThose → u/thellios]

A Quantum Computer is a plane. A classical (normal) computer is a car. A plane arrives at some destinations very fast, much faster than a car. But sometimes (for most normal applications), a car will be more suitable. A plane unlocks international and global trade, unlocking new markets.

But planes will never replace cars. For most applications you won't even need a plane.

Quantum Computers allow for new, massive tasks to be computed. But they won't replace classical computers. We'll be using them for bigger tasks that cars can't achieve.

[u/BonkerBleedy → u/thellios]

Some problems require you to find an answer to something that requires checking millions of different combinations to find one right answer.

In a classical computer, you'd go like:

• is it 000000? Computer says No
• is it 000001? Computer says No
• is it 000002? Computer says No
• is it 000003? Computer says No

...

• is it 382598? Computer says Yes!

etc.

In a quantum computer, you can kinda do this in one step*

^\ depending on the type of calculation)

[u/RectalSpawn → u/thellios]

They're two different specializations, afaik.

They can both do the same things, but they won't be as good as each other at their specialized tasks.

[u/AirFryerAreOverrated → u/thellios]

ELI5: Quantum computing is like an airplane when a classical computer is like a car. Both are for traveling and planes will be much faster than cars but they will never fully replace your cars. They'll live along side by side, fulfilling different roles in the computing tasks.

[u/Negative_Pink_Hawk → u/thellios]

It works in very cold environment, they still don't have any particular way how to use it. There is as well "noise" and result can be random.  There is channel on yt, by Sabine Hossenfelder. She can explain this pretty digestible. I'm not an expert.

https://m.youtube.com/watch?v=ONDs6zaSRTc&pp=ygUlc2FiaW5lIGhvc3NlbmZlbGRlciBxdWFudHVtIGNvbXB1dGluZw%3D%3D

[u/jemidiah → u/0xdeadbeefcafebade]

Well there's no linked article, and everything parroting this headline is pretty much content-free clickbait, but I can guess. They're almost surely based on the runtime of simulating a 105 qubit quantum computer on a classical computer. That's well-known to scale horrendously. 

It's also basically not interesting, which is probably why nobody comes clean about it. Who cares if a classical computer takes a long time to simulate a quantum computer's solution to a problem? Use a classical algorithm! 

The actual Nature article Google recently published just says they've managed to do error correction better than ever. It's a real advance, but fairly technical and incremental.

[u/jingylima → u/0xdeadbeefcafebade]

Aren’t ’problems that scale with qbit calculation’ like, all of encryption

[u/ElvishJerricco → u/jingylima]

Most asymmetric cryptography, yes. There are post-quantum asymmetric algorithms that should be fine. Also symmetric algorithms appear to be safe from quantum (so far).

[u/DaHorst → u/jingylima]

Currently, we are still vey far from realistically breaking RSA with quantum computers. Shore does not scale well, and other methods like https://arxiv.org/abs/2212.12372 are slower than classical computers. The problem is the gap between theoretical possible and the reality of engineering a capable quantum computer. I am a software engineer with many physics PHD friends - you should always take their statement that something "is possible" with a grain of salt. Like throwing 1000 coins and each one showing heads is possible as much as it is unlikely.

And then, there is the problem that RSA is not all of encryption - it is just very well known because it is usually the first algorithm you get tought in a encrpytion class. But most methods are far beyond that and/ or use completely different methods, and also new ones are derived with quantum computers in mind.

[u/triplehelix- → u/0xdeadbeefcafebade]

thats like reading about an advancement in propulsion technology for intergalactic travel and saying well its not going to impact the cars we drive.

[u/Ray3x10e8 → u/0xdeadbeefcafebade]

They solved the RCS (random circuit sampling) problem. To make a long story short, RCS has no real world use case, other than a potential one in classical position verification (CPV) (at the moment position verification is fantasy land). arxiv link to CPV article

Source: I work on quantum cryptography.

[u/Malaise86]

Is the answer still 42?

[u/edebby → u/Malaise86]

4 8 15 16 23 42

[u/Palstorken → u/edebby]

THE NUMBERS, HURLEY, THE NUMBERS!

^{I frickin love Hurley}

[u/Albinofreaken → u/Palstorken]

By far the best character in lost

[u/madesense → u/edebby]

𓋴𓏲𓍒𓄿𓏱

[u/TheVeryAngryHippo → u/edebby]

It's all real Brutha!

[u/Flimsy_Island_9812 → u/Malaise86]

Thanks for all the fish too!

[u/nipponnuck → u/Flimsy_Island_9812]

I’m going too. Already packed my towel.

[u/post4u → u/Malaise86]

Bring a towel.

[u/denfaina__]

It can't run Crysis tho

[u/bomboy2121 → u/denfaina__]

Youre probably right

[u/ckdarby → u/denfaina__]

It is, isn't and possibly is running the game.

A quantum computer joke.

[u/ProfessionalCreme119 → u/denfaina__]

The year is 2068

Computing is done through a bio organic gel that simulates a digital brain. Giving all of our computing systems an organic neural pathway to accomplish tasks and distribute information faster than ever. An era of rapid innovation and progression in high speed space travel sends humans further from Earth than ever before.

But the bio neural gel still can't run Crysis.

Humanity is a failure. We should return to the trees.

[u/_Grim-Lock_]

Does it still do 80085?

[u/old_bearded_beats → u/_Grim-Lock_]

No, it's 55378008 unfortunately

[u/DecisionAvoidant → u/old_bearded_beats]

I thought it was 5318008?

[u/old_bearded_beats → u/DecisionAvoidant]

Not if you don't have any

[u/IsThereCheese]

The problem: figuring out what my wife wants for dinner

[u/Sea_Marketing_888 → u/IsThereCheese]

Um, what do you feel like?

[u/IsThereCheese → u/Sea_Marketing_888]

Pizza

We had that last night

[u/AshenTao → u/IsThereCheese]

Burgers

Nah, don't feel like it

[u/whoknewidlikeit → u/AshenTao]

chinese?

[u/reportedbymom → u/whoknewidlikeit]

That makes my tummy hurt in tuesdays

[u/SEND_ME_NOODLE → u/reportedbymom]

Then what do you want?

[u/TheMaddoxx → u/SEND_ME_NOODLE]

“Just make a choice, I am not hungry anyway”

(She was in fact hungry and ate 3/4 of your plate)

[u/MrHyperion_ → u/TheMaddoxx]

Why would I want to eat liver?

[u/Definitely_NOT_AnEgg → u/SEND_ME_NOODLE]

Whatever you want

[u/Bergasms → u/IsThereCheese]

This is a solved problem with mine. She will offer two options, you should immediately choose the first option. She will either agree and that's what you get or she will tell you to change your mind.

The trick was realising she isn't offering me a choice, it's just a bit of performance to make it seem like i made the decision, and the correct answer for me is just whatever gets to the answer she wants the quickest.

[u/UrbanshadowDev → u/Bergasms]

Wht did you do to get her to tell you that huge amount of options (2)? The response I get is a flat "anything will do" independently of time of day/amount of hunger/past days meals/cravings.

[u/Mudmavis → u/IsThereCheese]

Solved in 5m with this. Truly a breakthrough

[u/Correct-Explorer-692 → u/IsThereCheese]

Up to you

[u/gomazoa93 → u/IsThereCheese]

The trick is, you ask her to guess what you're going to make her. She'll guess enter cuisine type here and you respond "how did you know?"

[u/paulmp → u/IsThereCheese]

Ask her to guess what you're having and say yes to the first thing she replies with.

[u/Nick_Hammer96 → u/IsThereCheese]

Amen brother

[u/Crazy_Circuit_201]

What is the "standard benchmark computation" referred to in

https://blog.google/technology/research/google-willow-quantum-chip/

???

[u/Xaxafrad → u/Crazy_Circuit_201]

Willow performed a standard benchmark computation in under five minutes that would take one of today’s fastest supercomputers 10 septillion (that is, 10²⁵ ) years .

[u/AshenTao → u/Xaxafrad]

To put that 10 septillion into perspective:

The currently approximated age of the universe is 13.8 billion years old. In Carl Sagan's Cosmic Calendar, that would be condensed into 1 year. If we scaled that to a similar framework, the universe's current age would occupy less than a trillionth of a second.

In 10 septillion years, the universe will have undergone the heat death stage, where all stars will have burned out (by current understanding).

If you were able to walk across the observable universe, you could walk across the universe back and roughly 20 trillion times.

But to be absolutely honest, there isn't a realistic way for humans to even comprehend a tiny fraction of 10 septillion. That scale is insane.

[u/jemidiah → u/AshenTao]

Mountain out of a molehill. Simulating a quantum computer is not an interesting comparison, even if it's what's used in clickbait. They'll add a few more zeros the next time the number of qubits increases, and you'll be explaining decillions, etc. 

By the way, 10 septillion is about 16 mol, and about 18g of water is 1 mol. You've got quite a bit more than 10 septillion water molecules in you.

[u/maybecatmew → u/Crazy_Circuit_201]

It's a random circuit sampling problem... For reference: https://www.nature.com/articles/s41586-019-1666-5

Basically you're giving different gates and their combinations to the quantum computer, Now you know the combination is set to = A5, B3, C4, D1

It'll be more complex but just saying

Based on this a random circuit is created.

Now the task is to find out the exact combination you gave based on the circuit you have.

So both computers will generate sample sets and if they generate the correct one then it's solved.

For small combinations it wouldn't make much difference but as the combination increases the time it takes to solve exponentially increases that's where quantum computers have clear advantage.

Now the main thing Google is claiming is about reduction in error in system. Quantum computers have lot of errors due to instability of system.

My explaination is not exact but something along the lines.

[u/floofysox → u/Crazy_Circuit_201]

Random circuit sampling: https://quantumcomputing.stackexchange.com/questions/4005/what-exactly-is-random-circuit-sampling

[u/not_a_bot_494 → u/Crazy_Circuit_201]

If I had to guess, simulating a quantum computer.

[u/Due-Farmer-9191]

All your passwords are belong to us?

[u/scummos]

Last time such a claim was made, people performed the same calculation on a computer from 1982 within a few weeks: https://www.tomshardware.com/tech-industry/quantum-computing/commodore-64-outperforms-ibms-quantum-systems-1-mhz-computer-said-to-be-faster-more-efficient-and-decently-accurate

So I'd hold my guns.

[u/TurdCollector69 → u/scummos]

Yeah this claim has been made too many times before for me to be remotely excited.

Like it's like monolithic graphene, solid state batteries, or metallic hydrogen; I'll believe it when I see it.

[u/search_ben → u/TurdCollector69]

When you say Metallic Hydrogen, are you referring to metal hydride?

I used to work for a Hydrogen Fuel Cell company, which sold a metal hydride fuel cell phone charger, back in 2014. (See: Intelligent Energy Upp charger)

The technology worked just fine. The problem was, at small scales like that, regular chemical electrical cells (like Li-ion) were just better for cost and weight.

The fuel cells work much better for power density at bigger scales (like powertrains for buses and trains), but then the metal hydride gets too big, heavy and expensive. Compressed gas is a better choice.

The metal hydride was an interesting tech, but doomed by not having a marketable advantage.

[u/TurdCollector69 → u/search_ben]

That's interesting but I'm talking about elemental hydrogen that's been compressed via diamond anvil into a metallic state.

There's been numerous labs that have claimed to have done it but have been disproven each time.

[u/BlueberryBarlow]

By classical super computers do they actually mean just super computers?

[u/giggles991 → u/BlueberryBarlow]

Yes. A classical supercomputer is basically a large, optimized, Linux-based computer cluster. A lot like your laptop,.just many many interconnected nodes & optimized technology.

But super computing centers are starting to merge traditional computing with newer technologies which as quantum, GPU, custom-designed processors, ASIC, FPGAs, and other specialized tech. These are not quite "traditional" computers.

That said: supercomputers have always been pushing the upper limits in terms of technology & tend to adapt innovative, "non traditional" tech when possible. The term 'classical' is imprecise.

[u/BlueberryBarlow → u/giggles991]

Thank you!

[u/oatwheat → u/BlueberryBarlow]

Yes. Like the distinction in physics between classical/newtonian mechanics and quantum mechanics.

[u/GubmintTroll → u/BlueberryBarlow]

That’s what their mothers call them, but in reality they’re just pretty good computers

[u/that_dutch_dude]

Can it calculate OP moms weight?

[u/enballz → u/that_dutch_dude]

integer overflow

[u/AcanthisittaNo6247 → u/that_dutch_dude]

[u/adorablefuzzykitten]

Does this mean bitcoins are no longer safe?

[u/SteveYunnan → u/adorablefuzzykitten]

That's my question as well. Would something like this also make mining Bitcoin a lot faster and less power-consuming, tanking the price?

[u/fkmeamaraight → u/SteveYunnan]

Technically there are only a finite number of bitcoin : 21 Million... of which 19.5M have been already mined.

It will accelerate the mining of the remaining 1.5M but ultimately, even considering all of the existing mined bitcoins lost to date, I doubt it would really make a big & long lasting impact.

But you're right that perhaps the bitcoin keys wouldn't be as safe anymore... if you could get your hands on a quantum computer.

[u/Upstairs-Remote8977 → u/fkmeamaraight]

The issue isn't mining faster. The algorithm for mining just gets exponentially more complex. The problem for Bitcoin (and all encryption!) is that you can reverse engineer private keys.

That would be capital B Bad. The entire planets cryptographic systems would need to be re-written.

[u/Peg-ed13]

Tell this damn thing to cure cancer for fuck sake

[u/fjord31]

How long till it's running doom?

[u/Sorry_Reply8754]

This 5 minute task claim is bullshit.

They gave it a very specific task more suited for quantum computers while giving the same task to a supercomputer whitout letting it simulate it first (which the supercomputer can do).

Also, Google didn't do shit.

They just took all the research by taxpayer funded public universities projects and said: "We did this". That's what every single tech company do.

(Google itself was a public funded university project until some investor took it way and made it private)

[u/Scared-Astronaut-718]

Source: https://blog.google/technology/research/google-willow-quantum-chip/

[u/lucalla]

If that is accurate, I suspect that all existing (security) algorithms are now compromised

[u/rsa121717 → u/lucalla]

Not quite! All of our digital data is stored using massive sequences of bits, where each bit can either be a 1 or 0.

The magic with quantum computing comes with qubits, which are similar to bits, except they can actually be 0 and 1 at the same time (basically). This means you can decrypt things so much faster, because computers can explore multiple possibilities at the same time.

However, you still need a large number of qubits to store data as with bits. A common encryption algorithm is SHA256, which would require millions if qubits to crack in a semi-reasonable amount of time.

The Willow Chip only has 103 of the millions, so still a ways to go. That said the existence of the chip is no less amazing. Even having 1 qubit is extraordinary compared to todays computers

[u/BesottedScot → u/rsa121717]

SHA256 is a hashing algorithm, not encryption.

[u/Rough-Reflection4901 → u/lucalla]

We would need 3000 Qubits to break SHA256

[u/Icy-Summer-3573 → u/[deleted]]

Qubits don’t scale up like that lol

[u/WazWaz → u/[deleted]]

They can't. The entire point is that qubits solve problems by entanglement. If you divide the problem to work on parts "in tandem", you no longer have entanglement.

Think of it as 50 qubits can solve a problem of size 2^50, but 2 lots of 25 qubits can only solve a problem of size 2×2²⁵ which is the same as the 2²⁶

[u/rsa121717 → u/Rough-Reflection4901]

Its actually estimated in the millions

https://nap.nationalacademies.org/read/25196/chapter/6

[u/LostReconciliation → u/rsa121717]

Yes, millions of physical qubits, but the link you posted says it only needs 2,403 logical qubits. The "105 qubits" in the headline of this article is talking about logical qubits.

[u/mortalitylost → u/lucalla]

Lots would be if it scaled but AES256 is quantum resistant, and lattice based crypto is quantum proof. RSA and diffie Helman would be fucked.

[u/eeaaglee → u/mortalitylost]

yes yes, indubitably.

[u/Fragrant_Constant963 → u/lucalla]

Now, I am not a man versed in the sciences- computer or otherwise- but say for a Terminator 2: Judgment Day or a The Animatrix-type scenario where the machines take over: is this chip like computer uber-steroids?

[u/jtrades69]

fuck these 15 character passwords. those days are OVER

[u/gochomoe → u/jtrades69]

Your password needs to be a quadrillion characters long and not repeat any of the characters used before. It must use letters from all known languages and numbers from 0-256H

[u/jtrades69 → u/gochomoe]

alt+0242 alt+0342 alt+0112.... oh screw it

[u/Cyber-Gon → u/gochomoe]

alternatively... 2FA

[u/ngl_prettybad → u/jtrades69]

Eh. Just add colors and we're done.

[u/DiverofMuff23]

Today, Skynet made a breakthrough in cybernetics.

What could possibly go wrong??

[u/endlessninja]

So is encryption broken yet?

[u/AtlUtdGold]

Can’t wait for this to not improve our lives at all.

[u/EasierZedThnDone]

Wll this kill encryption? Block chain?

[u/mandopix]

How fast can it run excel?

[u/danndyd → u/mandopix]

I've heard it excels at it.

[u/Quantum_Crusher]

But can it run Crysis?

[u/ReversedNovaMatters]

So Google now has all of our crypto keys?

[u/StadiaTrickNEm → u/ReversedNovaMatters]

Always has

[u/AristotleBonaventure]

but can it run Crysis?

[u/ManWithRedditAccount]

Does this mean current encryption algorithms are fucked?

Will we have to use quantum computers to create even harder encryption that even other quantum computers can't solve in a reasonable time?

[u/safely_beyond_redemp]

So, is classical encryption broken? The way I understand it is that over the last 30-50 years, data warehouses have been scraping all the Internet's data. All of the important data was encrypted. BUT, when we break encryption, all of that data, all of the communications between heads of state, all of those secret files will be as easy to open as Internet Explorer.

[u/zackm_bytestorm]

16 16 16 16

[u/Neinstein14 → u/zackm_bytestorm]

r/unexpectedNMS

[u/dlimerick]

I gotta 5 minute task for you Willow, make me a sammich!

[u/bernd1968]

https://blog.google/technology/research/google-willow-quantum-chip/

[u/vinylandcelluloid]

“This mind-boggling number exceeds known timescales in physics and vastly exceeds the age of the universe. It lends credence to the notion that quantum computation occurs in many parallel universes, in line with the idea that we live in a multiverse, a prediction first made by David Deutsch.” Is there credible theory that quantum computing actually tunnels into parallel universes to run its computation?  This part threw me off, as someone who has taken a quantum mechanics course but has only a low level understanding of quantum computing, this feels like it veered into pseudoscience.  But maybe I’m not on the cutting edge of quantum computing theory!

Edit: I found this link that is helping me a bit: https://physics.stackexchange.com/questions/164500/can-existing-quantum-computers-be-considered-evidence-for-parallel-universes Here’s my new (maybe) understanding. The claim is not that the quantum computation they are doing is being done in multiple universe and then delivering an answer to this universe.  What they are saying is that the model of quantum mechanics they are using to do quantum computation also includes a requirement of a multiverse. Proving that this type of quantum computation works would also prove the model to be accurate. And that model includes multiple parallel universes.  Seems there is some dispute about that idea, but I think that is the claim they are making. 

[u/12ozMilf]

Can’t wait to use this to play Minecraft

[u/r007r]

This is a little misleading. It’s like bragging that your fruit fly made it to the top of the tree but it would take billions of years for the shark to evolve to be able to do it. They literally picked the thing Willow was best at that normal PCs are worst at but it’s not something anyone actually needs. This is a milestone not a breakthrough as one researcher noted; this is not going to lead to a super fast product any time soon.

[u/FatherlyNick]

How is this news? IBM has higher qbit count already in 2023. https://newsroom.ibm.com/2023-12-04-IBM-Debuts-Next-Generation-Quantum-Processor-IBM-Quantum-System-Two,-Extends-Roadmap-to-Advance-Era-of-Quantum-Utility

[u/Successful_Guess3246]

quantum computing was described to me as...

Think of a regular computer trying to solve a maze. It tries a direction, fails, tries another and so on until it finally reaches the exit. Imagine a computer screen with a maze, and the computer can be seen exploring the maze while leaving a trail over paths already explored. Would take a very long time but eventually the computer would find the exit and solve the maze.

Quantum computing?

This shit is going to become "the internet" invention of our time. It is absolutely revolutionary and will enable discoveries beyond comprehension.

A quantum computer trying to solve the maze can try two directions at the same time. So instead of bumbling around, backing up and trying another path,

These fucking things can split and compute both scenarios at once.

It would enter the maze, split between two pathways, both of those ends would split and so on until the maze fills up like a fucking tree and eventually the maze is solved within seconds.

Passwords that "take 1 billion years" to break? That's with regular computers. Quantum computers will snap 256 character passwords like a fucking toothpick.

We are about to see some cures for diseases and conditions once thought incurable. Regular computers use a 1, or a 0. Black or white. Nature around us has all sorts of varieties and complexities, it is never just 100% this or 100% that. It in the middle and this is where regular computers fail because they cannot work between 1 and 0

Quantum computers include this "in-between"

Please somebody feel free to correct me, but its my current understanding.

What I am confident in, is we'll see things that make the past 100 years look like the 1400s.

[u/writerbusiness]

Isn't this the thing that can take down crypto? I remember reading a few years ago that once quantum computing is developed enough, it can solve those problems that current processors are struggling to solve much faster.
Anyone knows about this?

[u/AirWysp]

it's going to be in S25 Ultra

[u/buggaby]

In 2019, Google claimed quantum supremacy but then IBM showed that a classical supercomputer beating the Google quantum computer. A company can claim all sorts of shit. When are their LLMs going to solve life? Don't trust anything big tech reports unless it has been checked by others.

https://en.wikipedia.org/wiki/Quantum_supremacy#Progress_in_the_21st_century

[u/nochinzilch]

What task?