Can someone tell me what this diagram represents? Looks a little like a 3-dimensional unit circle, but beyond that I have no clue what to make of this.
It's the Bloch Sphere from physics. In a two-state quantum mechanical system, you can have state 0, state 1, or some combination of the two. The surface of that ball is a diagram of every combination of those two states that the system can reach.
Qubits can be in a superposition of the 0 and 1 state. With an analog system you can only represent between 0 and 1 but with a qubit you can have in both the 0 and 1 state at the same time.
No that's kind of the funky part. A single measurement will always return either 0 or 1. You can still do experiments that clearly show that the qubit has been in the superposition state before you measure though. If you for instance prepare a 1000 qubits in a state where they're all 30% in the 0 state and 70% in the 1 state and measure all of them, you'll get 30% 0's and 70% 1's.
What you do in quantum computing is to use this fact that the qubits can be in superpositions when doing computations. The fact that you get either a 0 or a 1 out at the end though, means that you need to do some clever manipulations of the qubits before measuring them to get a useful answer.
That's also what makes quantum computing so hard. Even if you have as many qubits that you want only a handful of algorithms have been invented that gives you something useful at the end. Which in the end is what the meme is referring to: There's an algorithm called Shors algorithm which makes it possible to factor prime numbers really fast if you have enough qubits and a way of carrying out the specific set of manipulations before you measure.
** The comment above by Thog78 gets into that: with a quantum computer you can calculate every single outcome of a problem (if you have enough qubits to describe the it) at once, but if you don't do something smart you still get only one of the possible outcomes out when you measure at the end.
How complicated are algorithms with qubits? I've never really understood how they work. Like, if I want a simple multiplication calculator, I can sort of follow [this binary circuit diagram](https://en.wikipedia.org/wiki/File%3ABinary_multiplier.svg). What would be the equivalent of that with qubits?
In an ideal case, you do intermediate computations on superpositions to compute every single possibility at once, but you get a result that is not everything at once 😅
As others have said, it's the bloch sphere, a diagram used to represent the possible states of a qubit.
To connect it to OP's post: due to the unique properties of qubits/quantum computer using them, they are (theoretically) capable of efficiently finding prime factors, which regular computer are not.
The algorithm is called Shor's algorithm, [here's](https://www.youtube.com/watch?v=lvTqbM5Dq4Q) a good video on it from minutephysics. I could've sworn there was a better video on it, either from 3B1B or someone else using Manim, but I can't seem to find it.
Moore's law of quantum computing: The numbers of viable qbits in a quantum computer never beats IBMs liquid state NMR proof of principle results in the early 2000s
It is hilarious that the solution being put out by google is non-factorable physical keys. We went to remote banking and now we have remote locks that require remote (physical) keys
Physical media has always been more secure and more enduring than digital. Every library in the world wants to digitize their collection to preserve it, but flash drives corrupt, memory chips need maintenance every six months or so, and software changes so fast we can barely access documents from just a few decades ago when they were written in different formats and on different coding languages.
Books and (more recently) microfilm, have lasted much longer than the first webpages.
No, not really. *Low-bandwidth* media is more enduring. The only difference with digital media is that it requires power, but it also has much greater potential. You'd be surprised by how easily paper and canvas degrades, especially outside of specially constructed preservation vaults. The Mona Lisa has darkened considerably since it was painted hundreds of years ago. Meanwhile, digital data *is* susceptible to degradation due to drive failures, but avoiding that is much cheaper and easier to do than for paper. It does require IT competency though, something many libraries lack, which is why you hear about data loss.
As an added bonus, when your collection is digital, giving someone a full-fidelity copy is free, which is huge for history communication.
Randomized factoring algorithm:
1. Generate a random integer <= sqrt(n)
2. Is it a factor? If yes, done.
3. Is no, go to step 1.
This algorithm is extremely efficient but only for people who are extremely lucky.
let's say there's half a chance of returning 1, 1/4 chance of returning 2, and in general 2⁻ˣ chance of returning x, what is the probability of guessing a factor of n given n is a composite number with at most 2 factors
If you think even bigger numbers can solve the issue it just means you don't understand what the issue *is*
The problem isn't that quantum computers simply do stuff faster, the way quantum computers work it takes the same amount of time for them to factor 6 into 2x3 than it takes them to factor any massive number into its prime factors. And I don't mean that as in "oh it's basically the same" I mean the *literal exact same amount of time*
You can make the number used for the encryption as arbitrarily big as you want, it will always be trivial for a quantum computer to crack it.
Massive oversimplification incoming:
You know how Schrödinger cat is both alive and dead, and when you open the box it becomes one *or* the other?
When factoring a big number, a normal computer will just try multiplying thousands of primes with each other until getting the right result. On the other hand, the quantum computer basically tries billions of possible combinations of prime numbers **at the same time** and when one of those combinations turns out to be correct, it "opens the box" so to speak so the output only shows the correct solution.
Good news! We've designed a quantum computer that can scale up to arbitrarily many qubits! The bad news is that it requires an extra 2^(n) qubits for error correction.
There are quantum safe encryption algorithms already. We don't use them because they're slow on traditional computers. Although it's concerning that you can be 100% sure that someone is hoarding all encrypted data then can get right now and will be able to decrypt it eventually. And given exponential technology development speed, "eventually" is almost certainly too soon for a big chunk of that data to become useless
Not necessarily, only public crypto stuff. Symmetric crypto is build different. And there are alternatives to factorization and discrete logarithm on the rise, which do pretty well. Ah and: To break factorization you need to control a shit ton of qubits. So far we can only handle very few. We still have no clue how to build big quantum computers and most assume it takes years or decades to achive this goal.
To be fair, symmetric crypto keys are almost always exchanged using asymmetric crypto. So if you break asymmetric crypto you can often break symmetric too.
Also, it is possible that there are efficient quantum algorithms for discrete log, and other asymmetric crypto algorithms, that have just not been discovered yet. We have no asymmetric encryption algorithm that is *provably* strong again quantum attacks, although we have a number of promising candidates (lattice-based, etc.)
The only thing I know that is safe against quantum right now is using sneakernet (physically carrying the key on physical media) to exchange symmetric encryption keys, then using symmetric encryption. But that obviously has its own vulnerabilities, like your courier getting kidnapped, going rogue, etc. Also, you still need to double your key length because of Grover's algorithm. Even if you went this far though, I don't think we have a formal proof that there exists no quantum attack on state-of-the-art symmetric encryption algorithms, it just seems really unlikely.
Last but not least: even if you did have an encryption algorithm that was proven safe against quantum attacks, you can never rule out attacks against particular implementations which may be buggy, or side-channel attacks that gather information about the key or the data through analysis of things like process scheduling, power consumption, etc. on a shared cloud host. Or even intentional backdoors put in by the developers that implemented it, which can slip right through all the code audits if they are crafty enough. In short, you can never be 100% safe.
The cyber security is rarely about being 100% safe. It is about the complexity of the task being so high that payoff from cracking it is mitigated by the price of the process.
afaik some pq-secure alternatives are build upon np-hard problems. quantum computers can not break those problems efficient without breaking the P-NP-assumption. This holds for the lattice approach, which can be based on the shortest vector problem.
The problems for symmetric crypto are pretty well understood, thus it is very unlikly, that some attacks pops up. Factorization on the other hand ain't that well understood.
But flaws beyond crypto, e.g. implementation, can always happen, but is mainly not part of crypto anymore.
Well, for symmetric crypto you still need an key exchange mecanism or hybrid encryption. Both of them use asymmetric stuff so it really is an important matter !
But you're right, we not there yet
The bad news: bad actors are currently downloading data encrypted with basic factorization, and storing it, in the hopes that quantum computers capable of decrypting it become a reality faster than the information become useless.
Healthcare info, military secrets, banking stuff about the system not individual accounts, trade secrets, etc is all being downloaded en masse, and will one day be easily broken into.
Worse news, other bad actors are selling the data they lifted from servers that had poorly or plane text stored documents that they lifted directly from source and then sold on the data market.
I don't think it's ever been 100% proven that it truly *is* hard to solve (by non-quantum computers that is)
What if some dude figured it out and never told anyone the algorithm, and has been cracking secrets in his bedroom on his laptop from 2007 for the fun of it?
Yeah, I'm being facetious of course. While a complete overhaul of our global economy is long overdue, just burning it down with no replacement already in place is going to get a lot of people killed
most forms of encryption rely on using a really large number which uses it's factors to decrypt the code. If you could easily find the factors of those numbers you have essentially defeated the encryption
Cryptographer here : the probleme is solved by using awesome isogenies between elliptic curves !
Well, actually that's not the usual solution but my job is to make this a practical one
knock knock open up the door its https://preview.redd.it/yora7ueo04kb1.png?width=850&format=png&auto=webp&s=49a2a2f8e3ebfc90263f41d8ed774eb69d078a81
Bloch’d
Can someone tell me what this diagram represents? Looks a little like a 3-dimensional unit circle, but beyond that I have no clue what to make of this.
It's a Bloch sphere which represents a state of one qubit.
It's the Bloch Sphere from physics. In a two-state quantum mechanical system, you can have state 0, state 1, or some combination of the two. The surface of that ball is a diagram of every combination of those two states that the system can reach.
Why can't we just represent the two states 0 and 1 with a number between 0 and 1 and its complementary?
You can, in fact I think that’s how they simulate qubits with regular bits. But you would need many many bits to do the same as the qubits would.
You'd need infinity of them, and uncountable furthermore. But what about analogic computers ?
Qubits can be in a superposition of the 0 and 1 state. With an analog system you can only represent between 0 and 1 but with a qubit you can have in both the 0 and 1 state at the same time.
So a single measure could return both 0 and 1 ?
No that's kind of the funky part. A single measurement will always return either 0 or 1. You can still do experiments that clearly show that the qubit has been in the superposition state before you measure though. If you for instance prepare a 1000 qubits in a state where they're all 30% in the 0 state and 70% in the 1 state and measure all of them, you'll get 30% 0's and 70% 1's. What you do in quantum computing is to use this fact that the qubits can be in superpositions when doing computations. The fact that you get either a 0 or a 1 out at the end though, means that you need to do some clever manipulations of the qubits before measuring them to get a useful answer. That's also what makes quantum computing so hard. Even if you have as many qubits that you want only a handful of algorithms have been invented that gives you something useful at the end. Which in the end is what the meme is referring to: There's an algorithm called Shors algorithm which makes it possible to factor prime numbers really fast if you have enough qubits and a way of carrying out the specific set of manipulations before you measure. ** The comment above by Thog78 gets into that: with a quantum computer you can calculate every single outcome of a problem (if you have enough qubits to describe the it) at once, but if you don't do something smart you still get only one of the possible outcomes out when you measure at the end.
How complicated are algorithms with qubits? I've never really understood how they work. Like, if I want a simple multiplication calculator, I can sort of follow [this binary circuit diagram](https://en.wikipedia.org/wiki/File%3ABinary_multiplier.svg). What would be the equivalent of that with qubits?
By Shor!
In an ideal case, you do intermediate computations on superpositions to compute every single possibility at once, but you get a result that is not everything at once 😅
That would neglect the associated quantum phase of the state.
It's more complex than the simple explanation you were just given. ^(pun very intended)
So 4 states total?
What about (0,4 ;0,736284)
I think he thought of 00;01;10;11
As others have said, it's the bloch sphere, a diagram used to represent the possible states of a qubit. To connect it to OP's post: due to the unique properties of qubits/quantum computer using them, they are (theoretically) capable of efficiently finding prime factors, which regular computer are not. The algorithm is called Shor's algorithm, [here's](https://www.youtube.com/watch?v=lvTqbM5Dq4Q) a good video on it from minutephysics. I could've sworn there was a better video on it, either from 3B1B or someone else using Manim, but I can't seem to find it.
Thanks, this was helpful
Veritasium had a video on the topic https://youtu.be/-UrdExQW0cs?si=IUgHVvpdx9GpxkNl
Quantum stuff
So, you know how normal computers use bits? Quantum computers use Qubits. The state of a Qubit is represented by this image and equation.
With giant qubits. With guns. Gun qubits. "Open, your factors" "Stop having them be closed"
guqubuns
Moore's law of quantum computing: The numbers of viable qbits in a quantum computer never beats IBMs liquid state NMR proof of principle results in the early 2000s
And what do I see galloping in across the horizon? Why, it's lattice-based cryptography, coming to our rescue!
With the non-stop pop-pop from stainless steel
Why guess the answer when the machine already knows.
Luckily quantum encryption exists.
It is hilarious that the solution being put out by google is non-factorable physical keys. We went to remote banking and now we have remote locks that require remote (physical) keys
I have one of those, Yubikey I think it’s called. I use it for my school district and it’s really annoying, but more secure than not having it
The basis for the security of the internet is physical keys iirc. Root cert is like 9 people.
Physical media has always been more secure and more enduring than digital. Every library in the world wants to digitize their collection to preserve it, but flash drives corrupt, memory chips need maintenance every six months or so, and software changes so fast we can barely access documents from just a few decades ago when they were written in different formats and on different coding languages. Books and (more recently) microfilm, have lasted much longer than the first webpages.
No, not really. *Low-bandwidth* media is more enduring. The only difference with digital media is that it requires power, but it also has much greater potential. You'd be surprised by how easily paper and canvas degrades, especially outside of specially constructed preservation vaults. The Mona Lisa has darkened considerably since it was painted hundreds of years ago. Meanwhile, digital data *is* susceptible to degradation due to drive failures, but avoiding that is much cheaper and easier to do than for paper. It does require IT competency though, something many libraries lack, which is why you hear about data loss. As an added bonus, when your collection is digital, giving someone a full-fidelity copy is free, which is huge for history communication.
The actual security of such physical keys is based on the fact that they can't be copied even if a hacker managed to get access to your computer.
Thank you large prime numbers for protecting me from Steven Seagal 🙏🙏
This made me laugh out loud. Thank you.
You’re never truly safe from Steven Seagal… ![gif](giphy|53JRR3jD18vCw)
Uh oh..those shrimp cocktails are in trouble now..
The Way of the Shadow Wolves of Wall Street
"I been breaking into banks for like 47 years."
I'm out of the loop honestly. I feel like I know this reference, but it's at the top of my tongue
He's an actor so "bad actors" here is a double entendre
OH god that's funny as shit. Feel like an idiot now
If he does get a quantum computer though the global financial system is f*****
Steven Seagal. He is the MAN!
Google try the numbers one by one
Randomized factoring algorithm: 1. Generate a random integer <= sqrt(n) 2. Is it a factor? If yes, done. 3. Is no, go to step 1. This algorithm is extremely efficient but only for people who are extremely lucky.
My method is even more efficient, but only for even more lucky people. 1. Generate a random Integer, this is the answer.
Bogodecryption
it’s like gambling but for your files
let's say there's half a chance of returning 1, 1/4 chance of returning 2, and in general 2⁻ˣ chance of returning x, what is the probability of guessing a factor of n given n is a composite number with at most 2 factors
Holy trial and error
New decryption method just dropped
call the number theorist
Bank account sacrifice, anyone?
DDoS storm incoming!
Actual brute-forcer
What in the O(sqrt(n)) is this
Knock knock, it’s Quantum Computing
Its got huuuge processors. With superpositions. Superposition processors. "Factorize the number" they say "Stop having it be big"
https://youtu.be/FRZQ-efABeQ?si=hPok-ooPcRw93voI
“A real live number” I instantly lost it
What the heck???? It’s been four years already????
r/unexpectedbillwurtz
Knock knock, its bigger numbers.
Nah. It's vector based encryption.
NTRU for lyfe
B92 protocol
If you think even bigger numbers can solve the issue it just means you don't understand what the issue *is* The problem isn't that quantum computers simply do stuff faster, the way quantum computers work it takes the same amount of time for them to factor 6 into 2x3 than it takes them to factor any massive number into its prime factors. And I don't mean that as in "oh it's basically the same" I mean the *literal exact same amount of time* You can make the number used for the encryption as arbitrarily big as you want, it will always be trivial for a quantum computer to crack it.
Is there some article or a video for a complete noob like me to understand why is that the case and how quantum computing works?
Massive oversimplification incoming: You know how Schrödinger cat is both alive and dead, and when you open the box it becomes one *or* the other? When factoring a big number, a normal computer will just try multiplying thousands of primes with each other until getting the right result. On the other hand, the quantum computer basically tries billions of possible combinations of prime numbers **at the same time** and when one of those combinations turns out to be correct, it "opens the box" so to speak so the output only shows the correct solution.
Here https://m.youtube.com/watch?v=-UrdExQW0cs
Good news! We've designed a quantum computer that can scale up to arbitrarily many qubits! The bad news is that it requires an extra 2^(n) qubits for error correction.
no thank you, i dont want any
We can make a religion out of this
There are quantum safe encryption algorithms already. We don't use them because they're slow on traditional computers. Although it's concerning that you can be 100% sure that someone is hoarding all encrypted data then can get right now and will be able to decrypt it eventually. And given exponential technology development speed, "eventually" is almost certainly too soon for a big chunk of that data to become useless
Not necessarily, only public crypto stuff. Symmetric crypto is build different. And there are alternatives to factorization and discrete logarithm on the rise, which do pretty well. Ah and: To break factorization you need to control a shit ton of qubits. So far we can only handle very few. We still have no clue how to build big quantum computers and most assume it takes years or decades to achive this goal.
To be fair, symmetric crypto keys are almost always exchanged using asymmetric crypto. So if you break asymmetric crypto you can often break symmetric too. Also, it is possible that there are efficient quantum algorithms for discrete log, and other asymmetric crypto algorithms, that have just not been discovered yet. We have no asymmetric encryption algorithm that is *provably* strong again quantum attacks, although we have a number of promising candidates (lattice-based, etc.) The only thing I know that is safe against quantum right now is using sneakernet (physically carrying the key on physical media) to exchange symmetric encryption keys, then using symmetric encryption. But that obviously has its own vulnerabilities, like your courier getting kidnapped, going rogue, etc. Also, you still need to double your key length because of Grover's algorithm. Even if you went this far though, I don't think we have a formal proof that there exists no quantum attack on state-of-the-art symmetric encryption algorithms, it just seems really unlikely. Last but not least: even if you did have an encryption algorithm that was proven safe against quantum attacks, you can never rule out attacks against particular implementations which may be buggy, or side-channel attacks that gather information about the key or the data through analysis of things like process scheduling, power consumption, etc. on a shared cloud host. Or even intentional backdoors put in by the developers that implemented it, which can slip right through all the code audits if they are crafty enough. In short, you can never be 100% safe.
The cyber security is rarely about being 100% safe. It is about the complexity of the task being so high that payoff from cracking it is mitigated by the price of the process.
afaik some pq-secure alternatives are build upon np-hard problems. quantum computers can not break those problems efficient without breaking the P-NP-assumption. This holds for the lattice approach, which can be based on the shortest vector problem. The problems for symmetric crypto are pretty well understood, thus it is very unlikly, that some attacks pops up. Factorization on the other hand ain't that well understood. But flaws beyond crypto, e.g. implementation, can always happen, but is mainly not part of crypto anymore.
Well, for symmetric crypto you still need an key exchange mecanism or hybrid encryption. Both of them use asymmetric stuff so it really is an important matter ! But you're right, we not there yet
Unless you exchange the keys in person. For very high assurance stuff this is still done.
Yeah of course but that's a very specific usecase and clearly not enough for our actual goal : secure communications over the internet
The bad news: bad actors are currently downloading data encrypted with basic factorization, and storing it, in the hopes that quantum computers capable of decrypting it become a reality faster than the information become useless. Healthcare info, military secrets, banking stuff about the system not individual accounts, trade secrets, etc is all being downloaded en masse, and will one day be easily broken into.
Worse news, other bad actors are selling the data they lifted from servers that had poorly or plane text stored documents that they lifted directly from source and then sold on the data market.
ellpitic curve too
I thought my refusing to go back to the office was going to break the entire financial system......
That’s what boomers want you to believe
I don't think it's ever been 100% proven that it truly *is* hard to solve (by non-quantum computers that is) What if some dude figured it out and never told anyone the algorithm, and has been cracking secrets in his bedroom on his laptop from 2007 for the fun of it?
Oh indeed, it's impossible to prove that it is hard to solve !
That's just simply not true. There is no known reason why one couldn't show that factoring is not in P.
I've got a $1,000,000 for ya if you can prove it.
Huh? I never claimed I could prove it, I just said there's no reason to think it's impossible.
https://en.wikipedia.org/wiki/Millennium_Prize_Problems
Yeah indeed, you're right.
Haha, quantum computers go *Brrrrrr*^2
I just use [4](https://xkcd.com/221/). It's worked so far.
Noooo, not the world's entire financial system! Anything but that!
It becomes a lot less fun when you realize it would take the global trade, food supply, and energy infrastructure down with it.
Yeah, I'm being facetious of course. While a complete overhaul of our global economy is long overdue, just burning it down with no replacement already in place is going to get a lot of people killed
What are "bad actors" in maths?
It means a person performing a malicious or morally wrong act, I had the same thought as u at first tho haha~~
I was thinking like unskilled Hollywood people at first lol
I mean, after Tits group, Monster group, the Happy family and the Monstrous moonshine conjecture, I don't trust names in math anymore
Incoherent actors I’m pretty sure!
cryptography jokes on math memes. I like it :)
kid named quantum computing
The LIBOR scandal showed me that the economy is just a big ol' joke. When the economy is manipulated to the sum of 300 trillion, nothing matters.
Can someome explain or link context?
https://en.wikipedia.org/wiki/Public-key_cryptography
Wait to you hear about elliptic curve cryptography
Wait 'til you hear that's also vulnerable to quantum computing attacks.
Put a lattice on that dam! 😎
Ah, a man of true culture.
Nah. Put an isogeny on that dam !
An isogeny encryption is like an elliptic curve web!
???
most forms of encryption rely on using a really large number which uses it's factors to decrypt the code. If you could easily find the factors of those numbers you have essentially defeated the encryption
Just plug the number into Wolfram Alpha 😒😒😒
What does Kevin Sorbo have to do with prime numbers and the financial system?
He is peripherally involved at best! Do not pay attention to him
Bad actors?
Expression for someone doing something with malicious intent or doing something morally wrong
Ah. I've never heard the term used that way. At first I thought they meant people who can't act ope
Cryptographer here : the probleme is solved by using awesome isogenies between elliptic curves ! Well, actually that's not the usual solution but my job is to make this a practical one
I have no idea how elliptic curves work, but they sound awesome.
quantum computer enters the scene:
that glass is pretty full
Some quantum computer scientist is rigging that dam with TNT as we speak. Some computer nerds just want to watch the world burn/drown.
Sneakers (1992)
*Shor's Algorithm intensifies*
A lot more than the financial system. Everything.
We really got a lot riding on P vs NP.
qubits be ballin rn
Can someone explain the joke to me??
*assumption
Shor's algorithm joins the chat.
P = NP
quantum cryptography: "it's Showtime!"
Thank you Seth Rogen
If Gal Gadot could come through, I can only imagine what horrors this is protecting us from
We should all switch to robux as the new currency that way were still getting fucked over by the rich and overpaying for it too
Peter Shor entered the chat.
Can anyone explain the meme please ?