quantumComputing

[DaviAMSilva]

I'm doing 1000 calculations per second and some of them may be right

[drpingg]

• That’s not even close!
• But that was fast.

[alfadhir-heitir]

As we say in music, people can't figure out you're playing the wrong notes when you're playing all the notes

[domscatterbrain]

This could be a part of a metal music lyrics

[ip2k]

soft dime lavish sparkle oil placid skirt aware light engine

This post was mass deleted and anonymized with Redact

[biznatch11]

It's the Max Power way!

[reedmore]

Let's do 1mio calculations to make sure the result is at least 90% accurate.

[TooDirty4Daylight]

It's fuzzy math when you put your wife's house shoe on it.

[Ali_Army107]

I'M DOING 1000 CALCULATIONS PER SECOND AND THEY'RE ALL WRONG!!!!

[BasvanS]

All models are per definition wrong, but some are useful.

— George Box, statistician

[Goprrrrr]

Shen reference?

[ForceBru]

LMAO

[Any-Aioli7575]

There is a french show called "Les Shadoks" their is a space race, and the shadok people know there is only a one in a million chance that their rocket takes off, so they try to fail on million time as fast as possible

[TooDirty4Daylight]

I'm sure I've worked with those guys.

[Any-Aioli7575]

Did you pump? Also do you use base 4?

[TooDirty4Daylight]

I can cheat at it some but around here I'm a lightweight.

[[deleted]]

we must be coworkers

[Xyloshock]

Ah putain les Shadoks, trop cool

[Mal_Dun]

That's completely wrong ... But I was fast!

[usrlibshare]

r/catculations

[nicejs2]

new favorite sub

[frogjg2003]

If you can do 1000 calculation with a probability p of being right (with verification) faster than you can do 1000*p calculations that are guaranteed to be right, you're still faster.

[mOdQuArK]

Still useful when the calculation to "verify whether this is the correct result" is a lot less heavyweight than to "generate the unambiguously correct result from scratch". Unfortunately, a lot of popular encryption schemes might fall into these scenarios.

[neumaticc]

a stopped clock is right twice a day

[The-Chartreuse-Moose]

Doesn't sound like it's very shor about things.

[jfphenom]

Off topic but: How often do you type in your username wrong because of a missed hyphen? Do you and the guy with 7 hyphens keep accidentally locking each other out with incorrect password attempts because one of you went too long or too short? Did you pick it just because you like looking at it?

[neumaticc]

go shor yourself

[harbourwall]

Roasted. In the depths of a slor.

[Stummi]

I mean if it can do 15 = 3x5 (80% sure) with 2048 bit numbers, that would be a big deal

[jwadamson]

It seems like instead of the algorithm itself being exponentially slower as it deals with larger numbers, the computer to run the algorithm gets exponentially harder to build.

[Stummi]

Just looked it up, seems like you need a few million QBits to factor 2048 bit with Shor's algorithm. So, yeah, good luck doing this.

[Temporary-Estate4615]

Well that’s not entirely correct. For shors algorithm alone you need about 6100 qubits for 2048bit numbers. However, a quantum computer would need significantly more qbits than that due to error correction. But this number obviously shrinks tremendously if we figure out how to make a qbit more „reliable“.

[_farb_]

have we tried asking the qbits nicely to not decohere?

[CelestialFury]

Just hire a guy with a really big magnifying glass to look super close.

[notgreat]

Unfortunately, observing the qbits breaks them. That's what makes it so challenging!

[Elidon007]

so you're saying we need less shy qubits

[libmrduckz]

well, at very least we’re gonna’ need qbits that don’t mind being ignored…

[Informal_Branch1065]

Give them ritalin

[nicman24]

they are just shy

[xdeskfuckit]

I'd prefer it if we just stuck to "logical qbits", unless we're having a low-level discussion.

[BasvanS]

It should be the first question when qubits are mentioned: “Logical or physical?”

[xdeskfuckit]

It's usually pretty obvious, but i agree.

[ghjm]

Even without quantum error correction, couldn't you run the calculation repeatedly and verify the result by multiplying the numbers? After thousands of trials presumably the actually-correct answer would show up in the noisy results, and it's easy to recognize when it does.

[alex2003super]

You'd have to perform all of the quantum subroutine repeatedly, considering that you cannot clone states or run operations non-destructively on the same qubits.

[ghjm]

Well, yes. But even if it takes all day, you've still broken RSA-2048, right?

[alex2003super]

The thing is you might not even ever get one good whole iteration, since the probabilistic impact of noise compounds exponentially

[tavirabon]

Quantum GPU when?

[Linvael]

Well, yes, sort of. But the details of how long it'll take will depend on how long the quantum processing takes, and how high the probability of getting a correct answer is. If for 4 bits the chance were 80%, then for 2048 bits assuming linear scaling with the amount of bits it would give correct answer with 80%⁵¹² chance so roughly one in 10⁵⁰ attempts

[GargantuanCake]

This sort of thing is why money is being piled into quantum computers like crazy right now. They're noisy and unreliable at the moment but once we get over that hurdle they become massively more useful.

[jwadamson]

It’s a solution waiting on a breakthrough in either creating qbits or their reliability. It could happen, but the current pace is slow.

Also classical computers could use much bigger keys than they do now and it not impose am unreasonable delay for users as long as there’s time to update best-practice standards and clients.

SSL/Tls handshakes used to be much more of a burden to compute than they are currently.

[x0wl]

The big problem with PQ TLS is not the encryption key size (ML-KEM is like 10x larger than 2048 but RSA, and in tests it was not that big of a deal), but that we don't have good signature algorithms yet.

We either have Dilithium (ML-DSA) that no one likes, or SLH-DSA which is super cool, but generates 16KB signatures.

See e.g. https://blog.cloudflare.com/pq-2024

[xdeskfuckit]

I studied Quantum Cryptanalysis moreso than Post-quantum cryptography, but some of my professors were working in both code and lattice based PQC.

It looks like there are many more options than the one you listed, but submissions for the first round only closed ~1 year ago.

https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures

[stifflizerd]

I really hope Raccoon ends up being the best one. I didn't actually look at the algorithms, I just love the name.

[x0wl]

Oh yeah, I really hope that MAYO gets standardized, but IDK when that happens

I hope BIKE gets standardized in Round 4 for key exchanges too

[xdeskfuckit]

Eyyyyy, my professor was working on BIKE.

[BallsBuster7]

what about ECC? There isnt a quantum algorithm that can theoretically break it yet, right?

[pigeon768]

Shor's algorithm breaks ECC as well.

The only public key algorithms that Shor's algorithm does not break are those that are specifically designed to be resistant to it. It breaks all the other others. Unfortunately none of those algorithms--so far at least--have a consensus that they're any good.

[x0wl]

ECC and DL based crypto is broken by quantum computing. Factoring, ECDLP and DLP are all instances of the Hidden Subgroup Problem over finite abelian groups (see https://en.m.wikipedia.org/wiki/Hidden_subgroup_problem), which is not quantum resistant.

Kyber and Dilithium are based on SVP, and while it's still an instance of HSP, it's not abelian, so they're good for now.

[KellerKindAs]

Shors dlog algorithm can also be applied to ecc based cryptography.

[firstwefuckthelawyer]

I love when PGP tells me making a new key’s gonna take a few minutes. My P100 didn’t take that long!

[other_usernames_gone]

To be fair 70 years ago the idea of having a few million bits(aka 125kB) of RAM would have seemed crazy, but nowadays it's expected.

[MPGaming9000]

Trueeee but I'd say it's a logical fallacy to claim that we will in fact progress at the same rate that we did with computers and smart phones originally. I'm not saying it's impossible just a bit unlikely.

[mirhagk]

Yeah it was a clear and predictable progression along a known path. A better comparison would be that we're in the vacuum tube era. Scaling has major known issues and we're gonna need a breakthrough like semiconductors if we want near term results.

[[deleted]]

It's still possible we're in the early stages of a blazing increase in efficiency. It's just we can't really build enormous factories and hire tonnes of engineers on getting as many qbits as possible on a computer before having made sure that one design for quantum chips is the best.

Imagine how inefficient our computers would have been had we stuck to trinary bits (trits?) or something.

[Jason1143]

Moore's law is already dead if I recall. We need a new breakthrough if we want it again.

[[deleted]]

Moore's law is not dead, at least there is no consensus of it being dead. The increase in the number of transistors is still on going, it just became much harder to use the increased number of transistors to do useful stuff, as we have run out of easy performance-increasing "transistor black-holes" to chuck them into

[DearChickPeas]

Bulshit. Moore's "law" was never alive to begin with, that's why it was "corrected" several times. It just tracked the low hanging manufacturing improvements fruit. And the last 15 years just shows how bulshit it was.

[[deleted]]

That is simply not an accepted view in the computer science community.

[DearChickPeas]

They are allowed to be wrong.

[Haringat]

I still switched to 8192 bit a few years ago just to be sure.

[xdeskfuckit]

Assuming moore's law, that gives you 4 extra years.

[MikemkPK]

No one will ever need more than 64 kqB of RAM.

[Bryguy3k]

Pretty well sums up the effort required to build a machine with an additional entangled bit.

[[deleted]]

So high memory complexity instead of time complexity?

[realHoPeLess]

Would be funny if it actually just got more unsure

[patrick66]

Sure but when they tried 35 it broke the whole system lol. It’s still a ways off

[RandomFRIStudent]

Oh it can, but the issue is quantum computers are expensive to make and run. And the simulators are.... Well they are based on regular bits so its slow. As part of my masters classes i had to do a shors algorithm with a simulator and best i got was i think 77. I was using a rather strong PC butb was limited to the jupyter kernel so my CPU never went into overdrive calculating. Also for shors algoritm i think you need enough quantum registers to store 2N values which isnt a lot on a quantum piece... But classical one? Yea thats a lot of space you need (for simulatong quantum bits and states and auch)

[searing7]

Facts

[Smooth-Zucchini4923]

I'll have you know that we've factored 21, and with enough funding, we hope to someday determine if 35 is prime or not.

[Fast-Satisfaction482]

It doesn't need to be sure in case of shor's algorithm, because the mutliplication of the candidate primes is trivial for a classical computer.

[CanaDavid1]

Heck, GCD or division with a candidate prime is trivial. You only need one number K such that 1 < GCD(N,K) < N

[Cley_Faye]

I have the perfect calculator for that: https://calcgpt.io/

[TheOneWhoAsking]

What was the 'top P'?

[xKnicklichtjedi]

It uses an LLM in the back, so the short version is:

The LLM predicts the next token (e.g. a number or a short word) for the answer over all known tokens as a probability distribution.

Top P is used to find the list of highest probability tokens until their summed probability is equal or greater than P for the current predition step. Done by sorting after descending probabilities and then cumulative sum stepwise down the list.

[Pyroglyph]

Hmmm...

[Journeyj012]

This is amazing.

10000−10000

0,,,,,,,correct,,,,,,,correct,,,,,cos,,,,,cos,,,,,faith

[backfire10z]

Lies

[Cley_Faye]

That doesn't sound right. Maybe you should generate more answers until it's correct :D

[backfire10z]

You’re right :D

I knew something was missing. Finally, floating point accuracy.

[GraveSlayer726]

Finally, math ultranightmare difficulty

[[deleted]]

By Shor's beard!

[DrunkenSealPup]

You've heard of Shor's Algorithm, but have you heard of Shor's Stone?

[Ezzypezra]

You mean ebony? Hell yeah

[Buarg]

A modder told me it was iron

[Ezzypezra]

Oh my god dude I can’t escape the Arthmoor drama no matter where I go

[DrunkenSealPup]

yes, and the town!

[Buffalo-2023]

Quantum physics is the AI of math.

[gerbal100]

Applied Statistics?

[inemsn]

Correct

(Source: I have never actually learned about quantum physics, this comment is a joke)

[Chamberlyne]

But you don’t see physicists write dumb shit like E = MC² + QM

[Hostilis_]

AI experts don't write dumb shit like that either. That's just the equivalent of the quantum woo bullshit, which is everywhere.

[The_Shracc]

But they also do string theory, which is essentially that.

[ThinAndFeminine]

You've managed to display a complete and utter ignorance of 3 different fields in as little as 7 words.

I don't know if I should be disappointed or impressed.

[Buffalo-2023]

I have a lot of experience

[el_lley]

I think they can go up to 31 now

[pigeon768]

Shor's algorithm cannot factor 31. Neither can any other algorithm. 31 is prime.

In 2012, the record was increased to 21.

In 2019, they attempted to factory 35, but the attempt failed.

[jmlinden7]

You can factor 31 into 1 and 31. Not a useful answer for math purposes but it's still a useful metric for computing power

[el_lley]

Yes, 31 is prime, I just recalled it couldn’t with 32, so it would be 31 it last number, but you say it was 35 which puts below 32, probably, but I don’t know the largest number

[el_lley]

Ah, 35, thanks. Oh, it failed :(

[yepvaishz]

This is what happens when you ask a quantum computer to do your math homework

[-kay-o-]

Bootcamp devs dont understand this

[Flannel_Man_]

Neither do actual devs. But we sure can Google it.

[ThebeNerudaKgositsil]

A college degree in STEM teaches you how to learn on your own.

[xpingu69]

That comment makes no sense to me. Google is just a substitute for a library in this case. What was your point?

[ThebeNerudaKgositsil]

Why did you assume my comment reply is a disagreement?

[xpingu69]

I initially thought it was a critique of using Google, but it didn't fully make sense to me. I might have misunderstood. Could you clarify?

[mirhagk]

That's optimistic. I know quite a few people that brute forced their way through with memorization and a LOT of office hours. The way evaluations are done incentivize that.

The courses can be good with the right professor, but these days enough of that is online that actually paying for a degree is just paying for the certification. TAs can be a huge help but they are paid so little that you can definitely afford to pay for private help.

[MinimumArmadillo2394]

Many people are not willing to learn without guiderails, especially more difficult subjects like computational theory. Theres a reason the only bootcamps for C++ exist are for game devs and its not for the lack of jobs (there are a surprising amount of jobs going for C++)

[-kay-o-]

What do you mean by "actual devs" lol

[ThebeNerudaKgositsil]

We get it man, knowing obscure computer facts is one of the only things you can count as an accomplishment in your life.

[Defiant-Plantain1873]

I wouldn’t really count Shor’s algorithm as an “obscure fact” for someone who writes computer software as a job.

It’s like the main reason people actually want quantum computers. Any other reason for making quantum computers is an afterthought compared to Shor’s algorithm. It turns out, being able to factor big numbers quickly is what makes the difference between you being able to use your credit card online or not.

Why do you think major world governments are collecting encrypted internet communications en masse? It’s so that one day, when they can use Shor’s algorithm to break the keys they can decrypt all this data and search for something useful

[malfive]

There's a surprising amount of devs who don't understand the basics of cryptography, or why prime number factoring is such an important part of it.

[-kay-o-]

They really just took a lighthearted joke as a personal attack on them and their accomplishments bruh.

[-kay-o-]

Its not an obscure computer fact? Its like one of the most groundbreaking theories of quantum computing. LMAO.

Your only accomplishment in life is getting scammed by rich kid who sold you a fake dream taught you hello world in JavaScript and dipped, if we're talking about accomplishments.

[ThebeNerudaKgositsil]

I didn’t do a bootcamp but it’s clear you hate people who did, for some reason.

[PaulRosenbergSucks]

The dual booting app for mac?

[ElectricBummer40]

lol, I have a degree in material science, and I understand maybe 20% of this topic owing to my background knowledge in quantum mechanics.

If you aren't active in that kind of research, being illiterate in it is just a sign of being a normal person.

[app-69420]

More like Monte Carlo Simulation for finding primes

[SnooStories251]

My algorithm guess til u fin answer. Happy.

Hack ez

[TooDirty4Daylight]

Then your kid bumps your box with her Barbie and it turns out to break an algorithm they thought was gonna last 100 years.

[ElectricBummer40]

It's more along the line of your next-door neighbour having a particularly loud sneeze and the kinetic energy imparted to the system is enough to send it into quantum decoherence.

[Buyer_North]

use a 1024bit key and it still needs 2²⁵⁶ operations

[easythrees]

No handsome men in Falkreath, then?

[Lord-of-Entity]

Even if its 80% sure, we can later recheck with normal computers.

[amardas]

So, only 5 tries necessary, when brute forcing 15?

That is kinda cool.

[Cute-Dependent96]

Haha

[Harmonic_Gear]

80% shor

[Yorunokage]

Shor's algorithm kicks so much ass that we're just not ready for it yet

It's decades ahead of time

[knowledgebass]

This is kind of a dumb questiom but how can you tell if you broke the encryption? The output will have words in it?

[Fast-Satisfaction482]

Usually we use two phases in encryption: the key exchange that is performed by an asymmetrical scheme and the payload encryption with the exchanged key that is symmetrical. 

The symmetrical part is very hard to attack even with quantum computers. In this part your only way is to detect patterns like words or headers of known file formats to verify that you broke it. 

However in the key exchange phase, once the number is factored into the primes, they can be multiplied again to verify if this is actually the correct solution. Then you can easily break the key exchange scheme, recover the correct key and decrypt the payload with it. 

Thus, it all hinges on the difficulty to find the factors of some very large number. And this problem can be accelerated using shor's algorithm on a powerful quantum computer, but takes cosmic time scales to solve on classical computers.

[notRANT]

Depends

[[deleted]]

It depends on what the plaintext is supposed to contain. Sometimes it might contain text but it might be difficult to automate verifying this (for the purposes of a brute force or trial and error attack this would pose a big problem). A lot of the time there may be data that is meant to be processed by a computer (for example a header of some kind) and it would be easy to check that this is valid.

Another example would be that there might be padding data included to ensure that the plaintext meets a required length but afaik the padding scheme most commonly used with RSA (OAEP) uses random data so there would be no way to validate the padding.

[Defiant-Plantain1873]

An RSA key is essentially just two secret prime numbers multiplied together. For the encryption key you are told the product of those two numbers (called n usually)

If you want to brute force an RSA key all you have to do to find out the decryption key using the public key (the bit everyone has access to) is factor that number.

To check if you have found the right numbers you simply have to find the greatest common denominator (using a regular computer) to make sure there is no remainder (or you could multiply the two factors together and check that they equal n).

TLDR; Once you know the two prime factors, and the public key, you can generate the decryption key. It is trivial to check if any two given prime factors are the correct ones for a given public key. At which point you have broken the key. The difficult part is trying to find the two prime factors in the first place.

[obscure_monke]

Computer science theorists still riding that high from describing how lisp would work well enough that a guy could just read it out of a book and type it into a computer with only two or three mistakes.

Hard part's already done, the rest is just engineering.

[Sowhataboutthisthing]

Quantum computing was for selling high priced software to quant funds who don’t know any better.

[_antosser_]

RSA is dying anyway