8:25 "The Quantum Fourier Transform utilizes the ideas of quantum physics to do exactly what we want. It uses resonances to amplify the basic state associated with the correct period and the incorrect answers destructively interfere, which suppress their amplitudes. After applying the quantum Fourier transform, there's a very high probability that we'll pick the correct period." Wow. This is the perfect blend of physics, math, and computer science. I'd love to see more episodes that explore the deep connections between math and physics.
it didnt click for me until she explained about waves constructively interfering or destructively interfering.
7 років тому+2
Great video. Finally I know what's so special about quantum computers, what's their advantage, why it's so hard to program them and a bit about how they work. Well done!
Just imaging how the multilayered, multicore, multichannel computing is handleing the split key merkle decoding atm, glad to see you didnt decend into a fractional argument :) Blessing you and your courage
This really helped me. I think this is the best video on this subject. I know it was hard coming up with a really good example to use to explain constructive and destructive interference and I think that you did a good job.
I wrote an encryption method for messages that quantum computers can’t break. It doesn’t use keys and doesn’t allow you to know exactly when a encoded message stops or starts in the output.
11:13 "Any time we encounter a one, stop" But we can't look at the result, otherwise the super-states collapse. Also, to find the period, you'd have to try out different periods, until you find one where several states (all r states apart) are amplified. Also I'd like to ask a question for clarification: What exactly is in the quantum states? Because from your explanation it seems that only the results of the computations are (a^x mod N), but not any number for the period. But the period is what causes amplification, so I feel like *that* should be in the quantum state... Or maybe I'll take Bob's approach and sleep for now :D
The quantum states in this algorithm are the periods r, as you are trying to find the period r such that a^r mod N = 1. In the example from the video, 2^3 mod 7 = 1, so r = 3. This period is then used to derive the prime factors q and q of N using the formula in step 4. For a period of 3 (as in that example), a^x mod N = 1 every time x is a multiple of 3 (or the period r in the general case). In the example, a^x mod N = [2, 4, *1*, 2, 4, *1*, 2, 4, *1*, ...] for x = [1, 2, *3*, 4, 5, *6*, 7, 8, *9*, ...]. That is, a^x mod N repeats at a length equal to the period and ends with a value of 1. The arrows in the explanation are complex numbers (or 2D vectors) around a unit circle. For example, the arrows pointing east have coordinates (1,0). Lets call these arrows f. Now, scale all the arrows down by a^x mod N (i.e. f' = f / a^x mod N), then sum the resulting arrows up to some x value (e.g. a), what happens to that sum? Notice that if a^x mod N = 1 the magnitude of the arrow at x does not change, but if it is something different the magnitude gets smaller. Thus, the arrows at the multiples of the period stay the same and the arrows at other positions get smaller, so the arrows relating to the period have more of an effect on the result than those that don't. Next, for each "clock", look at the direction the arrows are facing whenever a^x mod N = 1 (i.e. at period r). The clock with r points has these arrows all pointing east. This means that summing over these values will result in an arrow (number) that gets bigger the more numbers you apply to it. The clocks without r points result in arrows pointing in different directions at intervals of the period r. They also have the property that the arrows will return to the starting point. This means that the sum of these arrows will wonder around 0 and a small value. The key here is that this fourier transform is a function of the period r (the thing we are interested in finding), so can be applied to all the quantum states (which are the different values of r). This then makes the correct value of r more likely to be found when you then read the answer from the quantum computer.
Thanks Gerben for the general intuition, and msclrhd for the details about the amplification. Imo the video didn't make very clear, that we're scaling the unit vectors and adding them. From the video it seemed like we were trying one period at a time, rather than all at the same time and amplifying the right result. Or maybe it's just that the details of the amplification are missing, which, at least for me, made it seem like we're missing or skipping something.
Very clever use of Fourier transform! Great video, I enjoyed a lot. However, there is one minor thing I'd like to point out: when you started to talk about swings, you actually showed swings with double the period than what you said. For example, if we start counting seconds when the 3 second swing is at left end, your swing is at right end after 3 seconds, even though it should've returned to it's initial position.
I love the videos you've made on cryptography. Can you make a video explaining ring signatures? I've tried to wrap my mind around them, but I just can't!
I know so little about so much , I feel like I'm drowning in ignorance ..... Your channel feels like a foot pushing me deeper down, away from air.......thank you for wearing that sweater though.... Death didn't seem so bad with my view .....
thanks indeed here is a quick thought: Now that you showed us how current crypto algorithms are easy to be broken by a quantum computer, it would be great if you follow this episode with another one about post quantum cryptography. As it is known, post quantum cryptography is based on several challenging problems that are hard to be solved even with a quantum computer (e.g. SVP challenge [NP-hard]). by the way NIST has called for proposals in this regards in order to be ready before quantum computers become a reality :) amazing channel
FYI: those animated pendulum periods are actually double. It takes 3 seconds for the first to go from one side to the other, and 3 to go back. That would make the period 6 seconds.
I found this question doing some researchers. Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It's called "the traveling sales problem."
Multi-prime RSA is also a thing, but since it is not used that much it can probably be skipped when it comes to explaining Shor's algorithm. But it is even in the PKCS#1 v2.2 standard.
Could you go more in depth on what exactly is happening when you apply the quantum fourier transform? are the roots of unity the amplitude of the waves? if these different amplitudes are assigned to the values of a^r mod n, how does that change the probability, since we only observe one random arrow.
In mathematics unity is the multiplicative identity a.k.a. 1. So she's saying the complex numbers that can be raised to a whole number power to become 1. Examples: (-1)² *=* 1² *= 1* (-1/2 + i*sqrt(3)/2)³ *=* (-1/2 - i*sqrt(3)/2)³ *=* (9/8 - 1/8) *= 1* (i)⁴ *=* (-i)⁴ *=* (-1)⁴ *=* 1⁴ *= 1*
Here are 2 mathematical expressions: 1. P= round(.25*(((3+(2*sqrt(2)))^n)+((3-(2*sqrt(2)))^n))^2)-2 (n=positive integer >=1) 2. Factors = sqrt(((1+T(sqrt(P)))^2)+P) +/- T(sqrt(P)) +/- 1 (P=composite integer,T=truncation operator) The 1st expression above generates Composite integers whose size (no. of digits) grows at an exponential rate with increasing n. The amazing thing about the 1st expression above is that it produces composites that is factorable by the 2nd expression above! Try it! but remember to set the precision for calculation high enough so that the 2 expressions above produce integers as output!
The solution to factoring any composite integer is equivalent to determining the non-trivial, positive real-value of a variable (k) I call the 'Coefficient of factorization' used in a unique, integer-factorization expression of mine which I've termed the 'Transformula'.
So based on the rational of wave reinforcement vs degradation, it it possible to use something like a variable frequency device to combine different frequencies that represent different numerical powers to either amplify or degrate a signal for a similar result? Like a radio signal? Not sure if this is the best explanation of my idea.
The most amazing part is that a quantum computer would peform this operation so much faster (amortized polynomial time) than a classical computer (exponential time), that it doesn't even matter that this type of computer is probabilistic and could give the wrong answer. It's so easy to check if x * y = z than it is to find x and y, that we can just try each answer given out until it finds the answer. This is all assuming that P =/= NP, which is almost certainly true.
Scott Brown I think you misunderstand how it works. Shor's algorithm is only probabilistic in the sense that you might not get an even number for r (the period). The algorithm actually deterministically solves for a multiple of the period m*r, from which the period can easily be retrieved. All the randomness associated with quantum mechanics is actually utilized, not a hindrance.
Also, this really doesn't have much to do with P vs NP, besides the fact that this is an NP problem that happens to also be QP. If you could prove factorization is an NP-hard problem, then it would be very connected to P vs NP
As far as I know, Shor's algorithm only has a high probability of returning the correct value for the period, which then is checked classically. This would make the algorithm at least partially probabalistic, which in the worst-case is the same as truly probabalistic right? This would make it functionally, but not truly, deterministic I think.
Yes, absorption is the first issue! Which is why defining terms doesn't mean that term is accessible immediately after defining. By accessible I mean it can be manipulated by and used to manipulate other symbols. Definitions in math seem to rely on the manipulations to define a term. itself. There is no such thing as a Prime Number, but there is a relationship a given number has to other numbers, and that specific relationship is the entirity of the meaning of Prime. A new term in physics describes an observed or predicted phenomenon. It just adds to a list of things that happen. A new term in math doesn't just expand the list by one though, it expands the list by one for every instance of knowledge already gained, and adds categories which will have to be answered for every instance that will be gained later. Math terms alter one's perception of the abstraction of reality for every new term and in relation to every other term as the definition is absorbed. maybe?
Your statement that the production of efficient, large scale quantum computers is only a matter of time is Shakespearean. I remember hearing of computer scientists saying quantum computing is a fraud, with no agreed upon definition, a decade ago. Keynes is falling out of favor with the rest of economics; but we are still dead in the long run. Current computers could technically crack encryption algorithms given enough years. If "quantum computing" never comes into existence, the theoretical advancements inspired by it may serve as a lasting example of science created by accident, and similarities between science and culturally inspired nonsense including conspiracy theories, urban legends, cults, and groupthink.
LOL I read somewhere (i.e. I am "reciting" from memory and not "citing" - okay citation nazis) that they were able to make a kind of black hole using sound, and were able to simulate behaviour of particles pairs splitting on a black hole's event horizon - i.e. one would fall in to the black hole while another would be freed - using phonons (sound particles/quanta). So maybe we'll see a quantum computer made out of sound or water waves? This was the easiest Infinte Series episode for me to understand, beacuse I'd already researched quantum computers, RSA, and read up on quantum mechanics and super-position. I was a bit confused with the constructive (3 dots on the dial) and destructive (6 dots on the dial) superposition interference of the dials shown in the video (interference happening every 3rd dot on the dial with 3 dots - constructive. And interference happenng every 7th dot on the dial with 6 dots - destructive [as it goes full circle?])... I probably got that wrong, but I get the basic idea I think in terms of waves.
The 6-point circle at the end (which reminds me of Ouroboros kekulei) should have three left arrows and three right arrows, not a hexagon. Still adds up to 0.
Yes, if I recall correctly, there are types of encryption that are currently resistant to quantum computing and some are in use. That said, quantum encryption puts it into another level. There is this thing called quantum encryption. The basic idea is that if you transmit your message in qubits in just the right way, you can create a message that will destroy itself after first try decoding it.
WeepingAngel256 There are dozens of alternative classical crypto-systems for which there are no quantum solutions, and even if there are, if quantum computers take off, then one-way functions will be possible, meaning a provably secure crypto-system could be developed. Mathematicians are always a century ahead of the game.
Well in worst case scenario, public cryptography is abolished. We can still use encryption securely, but you'd have to keep a different password/key for every secure site you visit. The problem gets only worse for the web site, it has to keep a unique key for every user. The biggest problem would be to negotiate these keys over the internet. One way to do it, is to have some trusted authority by both parties.
I paused this video before comments, then I went down a rabbit hole of wikipedia and google search on quantum computing and supremacy, etc, then come back to a her talking about another commenter doing the same. Yup. Community
We just got into wave theory in engineering physics so part of this wave destructive stuff makes a bit of sense, fun cause it would be rad to use some of this tech in some of our huge simulation needs in the nuclear world :D Still way above my pay grade, but gotta start somewhere!
also, a bunch of conventional computers put together already exists and is called a cluster. this is actually the first time seeing that as a description for a quantum computer.
Encryption based on RSA or ECC will become obsolete with quantum cryptography, in fact it is unbreakable due to Heisenberg's uncertainty principle. If I remember correctly, there are companies that offer services of quantum cryptography, that if, should have prices a little exorbitant. On the other hand, have quantum computers already gone from multiplying 2 numbers beyond 100?
This video might have been helpful 20+ years ago but today it's stupefying in context & a diversion from "reality(this AI construct akin to quarantine/Talos IV-The Cage-Menagerie-Zoo for esoteric humor)" itself.
If I have a number of qubits storing the number 12, like b1100. And I would use this theoretical quantum computer to shor's algorithm my way into getting the factors. Would we set it up in such a way that the qubits (or another set of qubits?) would then exhibit constructive interference to spit out the number 1, 2, 2, and 3? So... 01, 10, 10, and 11?
I think falsification can be used to find factors of N , the problem is that we are looking at every possible number as factors instead we should look at probable factors of N like we can guess the pattern of the factors for eg ending with certain digits then we can easily find the factors of N.
Yes. "Shor's algorithm" is actually a pair of algorithms with similar properties. One factors numbers; the other computes discrete logarithms, and can be made to compute discrete logarithms over elliptic curves, thus breaking elliptic curve crypto.
Deep learning for computing will be improved in the future, it's not as fast as the ideal quantum computer but we must continue the effort! Deep learning for mathematics is primitive nowadays. Not because it doesn't work, simply because we Earthlings are lazy sometimes.
math layman here. hypothetically, since we're talking about decryption, could one try to avoid being "hacked" with their own quantum computer through destructive interference?
do you know where can i learn more of the swings and their periods ? That example is very strange, i think i understood the end result but i would be happy to watch it or read it in a comprehensive way
Would finding the factors of numbers be easier to find like say 123 /2 no and can cancel all multiples of 2 /3 yes and count all the multiples of 3 except for the ones divisible by 2 /5 no and not count all multiples of 5 /7 no and not count all the multiples of 7 /9 no and not count all the multiples of 9 and so on. I don't know if it works for big numbers but it might help finding factors
I'm not so sure it's "just a matter of time." With the implementations of Shor's algorithm so far, knowledge of the correct answer has been incorporated into the quantum circuit. And it still only finds the answer about half the time. With a classical computer, if I already know the factorization of a number, I can just check it. And that quantum fourier transform looks like something that is going to be hard to scale. It's interesting and all. And it's certainly a concern, just in case. But so far quantum factorization does not look as promising as it's being presented.
Whoa, the concept that I have of the quantum probabilities that lead to magnetism, lasers; were based upon this -- or surely something of similar provenance?
All this talk about wave functions and FFT made me wonder, in a somewhat unformed way, if rather than exotic new quantum computers, old technology analog computers can be used to crack RSA?
Why whould you check for numbers smaller than N? Shouldn't checking for numbers samller than sqrt(N) be enough? Also, in the swing illustration, depending on the rate of energy loss, pushing every k*period would also resonate, right? ('cause you said "anything other than 3s.)
Also, why check all the numbers? If you are looking for prime factors, wouldn't you only see if N can be divided by the prime numbers. If N can't be divided by 2, why check 4, 6, 8, 10, etc...
FINALLY! Someone explained this in a way that makes sense! Now I just have to watch, pause and Google enough times until I understand the last part about constructive interference. I understand what that is... I just don't understand how it exactly works in a quantum computer to help make the correct answer more likely to appear in some cases
Either this episode is a lot less clear about the subject, or I lack the mental capacity for it. BTW, I love explaining quantum algorithms with Grover's search algorithm. I think it is much more tangible.
I am thinking to make project of RSA Quantum Decryption using IBMQ's 5-qubits sytem available online. But, as you said Shor's algorithm cannot be applied, so can I do the shor on 5-qubit system on IBMQ??
Watched this vid 4 years ago understanding nothing, came back 4 years later right before my quantum computing midterm to review :D
Similar however i came here while going on a tangent while i was studding for my cryptography midterm
That is pretty cool. Kudos to you!
How did your midterm go?
Is 1 a factor?
Yes, quantum computer. 1 is a factor.
"Oh, Ok. Thank you, Dr. Graham [happy face emoticon]"
To be continued...
Came here to say the same thing at 3:39
But it's not a PRIME factor
1 isn't prime
have you yet submitted this new prime? heard you can make a lot of money for each of those
Scientist: What's 1 + 1?
Quantum Computer: most probably 2
Scientist: What's 1 + 1?
Quantum Computer: most probably 2
Scientist: What's 1 + 1?
Quantum Computer: most probably 17
but somehow, that's still useful in certain cases
8:25 "The Quantum Fourier Transform utilizes the ideas of quantum physics to do exactly what we want. It uses resonances to amplify the basic state associated with the correct period and the incorrect answers destructively interfere, which suppress their amplitudes. After applying the quantum Fourier transform, there's a very high probability that we'll pick the correct period." Wow. This is the perfect blend of physics, math, and computer science. I'd love to see more episodes that explore the deep connections between math and physics.
Nothing beats
*Matt Parker's Domino Computer*
it was a parker square of a computer
the only thing that could beat it is if it were turing complete
Ethan Rojek I was about to wrote that too.
lol XD
PlayTheMind That thing is unhackable.
You're an awesome communicator by the way. You're clearly super competent, and you have a great ability to make complex ideas understandable :)
The metaphors for the Fourier transfrom was great
it didnt click for me until she explained about waves constructively interfering or destructively interfering.
Great video. Finally I know what's so special about quantum computers, what's their advantage, why it's so hard to program them and a bit about how they work. Well done!
1:16 "That's kinda true and kinda false" - I see what you did there....
Google would say it's KINDS BLUE , amirite ?
Schrodinger's truth, a.k.a. politics.
These videos are INCREDIBLY GOOD! Congratulations on your excellent work, PBS and Kelsey!
I've been searching for a video like this for forever! Thank you so much!
Just imaging how the multilayered, multicore, multichannel computing is handleing the split key merkle decoding atm, glad to see you didnt decend into a fractional argument :) Blessing you and your courage
God I wish I could do any math further than division
and after that, check out KhanAcademy.org
When they toss in a decimal 😶
It's cool to see all of these different topics intermingling to obtain Shor's algorithm
This really helped me. I think this is the best video on this subject. I know it was hard coming up with a really good example to use to explain constructive and destructive interference and I think that you did a good job.
Great video! Can you do one about set axioms and Peano arithmetic?
Mitch Kovacs Yes please!
Ordinal arithmetic would also be cool since we already talked about them.
I wrote an encryption method for messages that quantum computers can’t break.
It doesn’t use keys and doesn’t allow you to know exactly when a encoded message stops or starts in the output.
11:13
"Any time we encounter a one, stop"
But we can't look at the result, otherwise the super-states collapse.
Also, to find the period, you'd have to try out different periods, until you find one where several states (all r states apart) are amplified.
Also I'd like to ask a question for clarification: What exactly is in the quantum states? Because from your explanation it seems that only the results of the computations are (a^x mod N), but not any number for the period. But the period is what causes amplification, so I feel like *that* should be in the quantum state...
Or maybe I'll take Bob's approach and sleep for now :D
The quantum states in this algorithm are the periods r, as you are trying to find the period r such that a^r mod N = 1. In the example from the video, 2^3 mod 7 = 1, so r = 3. This period is then used to derive the prime factors q and q of N using the formula in step 4.
For a period of 3 (as in that example), a^x mod N = 1 every time x is a multiple of 3 (or the period r in the general case). In the example, a^x mod N = [2, 4, *1*, 2, 4, *1*, 2, 4, *1*, ...] for x = [1, 2, *3*, 4, 5, *6*, 7, 8, *9*, ...]. That is, a^x mod N repeats at a length equal to the period and ends with a value of 1.
The arrows in the explanation are complex numbers (or 2D vectors) around a unit circle. For example, the arrows pointing east have coordinates (1,0). Lets call these arrows f. Now, scale all the arrows down by a^x mod N (i.e. f' = f / a^x mod N), then sum the resulting arrows up to some x value (e.g. a), what happens to that sum?
Notice that if a^x mod N = 1 the magnitude of the arrow at x does not change, but if it is something different the magnitude gets smaller. Thus, the arrows at the multiples of the period stay the same and the arrows at other positions get smaller, so the arrows relating to the period have more of an effect on the result than those that don't.
Next, for each "clock", look at the direction the arrows are facing whenever a^x mod N = 1 (i.e. at period r). The clock with r points has these arrows all pointing east. This means that summing over these values will result in an arrow (number) that gets bigger the more numbers you apply to it.
The clocks without r points result in arrows pointing in different directions at intervals of the period r. They also have the property that the arrows will return to the starting point. This means that the sum of these arrows will wonder around 0 and a small value.
The key here is that this fourier transform is a function of the period r (the thing we are interested in finding), so can be applied to all the quantum states (which are the different values of r). This then makes the correct value of r more likely to be found when you then read the answer from the quantum computer.
Thanks Gerben for the general intuition, and msclrhd for the details about the amplification.
Imo the video didn't make very clear, that we're scaling the unit vectors and adding them. From the video it seemed like we were trying one period at a time, rather than all at the same time and amplifying the right result. Or maybe it's just that the details of the amplification are missing, which, at least for me, made it seem like we're missing or skipping something.
Great explanation.. Especially the Fourier transform.. Thanks a lot..
Very clever use of Fourier transform! Great video, I enjoyed a lot. However, there is one minor thing I'd like to point out: when you started to talk about swings, you actually showed swings with double the period than what you said. For example, if we start counting seconds when the 3 second swing is at left end, your swing is at right end after 3 seconds, even though it should've returned to it's initial position.
kudos for taking a shot at explaining some real complex stuff
I love the videos you've made on cryptography. Can you make a video explaining ring signatures? I've tried to wrap my mind around them, but I just can't!
I know so little about so much , I feel like I'm drowning in ignorance ..... Your channel feels like a foot pushing me deeper down, away from air.......thank you for wearing that sweater though.... Death didn't seem so bad with my view .....
I love this channel, They even explained quantum gates to people who doesn't know what are complex numbers.
God i love it when you talk discrete probability.
God you are sooo indecent
Luke Amendolara my love of math (aside from trig) is continous
thanks indeed here is a quick thought:
Now that you showed us how current crypto algorithms are easy to be broken by a quantum computer, it would be great if you follow this episode with another one about post quantum cryptography. As it is known, post quantum cryptography is based on several challenging problems that are hard to be solved even with a quantum computer (e.g. SVP challenge [NP-hard]). by the way NIST has called for proposals in this regards in order to be ready before quantum computers become a reality :)
amazing channel
I would like to see a spacetime crossover with Shor's algie with multiple worlds calculations.
I miss this channel too. Kelsey is a great teacher.
That is a great explanation & visualization of the Fourier transform, thanks.
FYI: those animated pendulum periods are actually double. It takes 3 seconds for the first to go from one side to the other, and 3 to go back. That would make the period 6 seconds.
I found this question doing some researchers. Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It's called "the traveling sales problem."
That music when she's explaining Complex Roots of Unity is kickin'
Let N represent your knowledge of Math when you were say - 2 years old. Now take N minus infinity and that equals me right now !
Love the Chanel !!
Multi-prime RSA is also a thing, but since it is not used that much it can probably be skipped when it comes to explaining Shor's algorithm. But it is even in the PKCS#1 v2.2 standard.
Great explanation - love this video and great explanation about the 'quantum threat.'
Could you go more in depth on what exactly is happening when you apply the quantum fourier transform? are the roots of unity the amplitude of the waves? if these different amplitudes are assigned to the values of a^r mod n, how does that change the probability, since we only observe one random arrow.
"Complex roots of unity" sounds more like sociology or psychology than math... :o)
In mathematics unity is the multiplicative identity a.k.a. 1. So she's saying the complex numbers that can be raised to a whole number power to become 1.
Examples:
(-1)² *=* 1² *= 1*
(-1/2 + i*sqrt(3)/2)³ *=* (-1/2 - i*sqrt(3)/2)³ *=* (9/8 - 1/8) *= 1*
(i)⁴ *=* (-i)⁴ *=* (-1)⁴ *=* 1⁴ *= 1*
this was actually really helpful, thanks!
I never thought of it that way till now. Thank you for opening our minds to a mathematical pun!
I'd love to see a band with that name :)
I am a simple man with simple needs: I see an Infinite Series video, I smash the like button
smash or pass
SMASH
Here are 2 mathematical expressions:
1. P= round(.25*(((3+(2*sqrt(2)))^n)+((3-(2*sqrt(2)))^n))^2)-2 (n=positive integer >=1)
2. Factors = sqrt(((1+T(sqrt(P)))^2)+P) +/- T(sqrt(P)) +/- 1 (P=composite integer,T=truncation operator)
The 1st expression above generates Composite integers whose size (no. of digits) grows at an exponential rate with increasing n. The amazing thing about the 1st expression above is that it produces composites that is factorable by the 2nd expression above! Try it! but remember to set the precision for calculation high enough so that the 2 expressions above produce integers as output!
The solution to factoring any composite integer is equivalent to determining the non-trivial, positive real-value of a variable (k) I call the 'Coefficient of factorization' used in a unique, integer-factorization expression of mine which I've termed the 'Transformula'.
So based on the rational of wave reinforcement vs degradation, it it possible to use something like a variable frequency device to combine different frequencies that represent different numerical powers to either amplify or degrate a signal for a similar result? Like a radio signal? Not sure if this is the best explanation of my idea.
The most amazing part is that a quantum computer would peform this operation so much faster (amortized polynomial time) than a classical computer (exponential time), that it doesn't even matter that this type of computer is probabilistic and could give the wrong answer. It's so easy to check if x * y = z than it is to find x and y, that we can just try each answer given out until it finds the answer.
This is all assuming that P =/= NP, which is almost certainly true.
trying answers (if check takes polynomial time) until you find the correct one is the very definition NP.
Scott Brown I think you misunderstand how it works. Shor's algorithm is only probabilistic in the sense that you might not get an even number for r (the period). The algorithm actually deterministically solves for a multiple of the period m*r, from which the period can easily be retrieved. All the randomness associated with quantum mechanics is actually utilized, not a hindrance.
Also, this really doesn't have much to do with P vs NP, besides the fact that this is an NP problem that happens to also be QP. If you could prove factorization is an NP-hard problem, then it would be very connected to P vs NP
As far as I know, Shor's algorithm only has a high probability of returning the correct value for the period, which then is checked classically. This would make the algorithm at least partially probabalistic, which in the worst-case is the same as truly probabalistic right? This would make it functionally, but not truly, deterministic I think.
True, I should probably say amortized O(n^k) time, since we would probably ignore the pathological/absolute worst case times.
Wow. Awesome video
such a great series! Thanks so much for creating great content.
Lady, my brain hurts. Please continue.
Yes, absorption is the first issue! Which is why defining terms doesn't mean that term is accessible immediately after defining. By accessible I mean it can be manipulated by and used to manipulate other symbols. Definitions in math seem to rely on the manipulations to define a term. itself. There is no such thing as a Prime Number, but there is a relationship a given number has to other numbers, and that specific relationship is the entirity of the meaning of Prime.
A new term in physics describes an observed or predicted phenomenon. It just adds to a list of things that happen. A new term in math doesn't just expand the list by one though, it expands the list by one for every instance of knowledge already gained, and adds categories which will have to be answered for every instance that will be gained later.
Math terms alter one's perception of the abstraction of reality for every new term and in relation to every other term as the definition is absorbed.
maybe?
I love your sweater and your job 🥺
Music too loud!
Could you do an episode on quantum computer proof cryptography? I'd be really interested to learn more about that.
Your statement that the production of efficient, large scale quantum computers is only a matter of time is Shakespearean. I remember hearing of computer scientists saying quantum computing is a fraud, with no agreed upon definition, a decade ago. Keynes is falling out of favor with the rest of economics; but we are still dead in the long run. Current computers could technically crack encryption algorithms given enough years. If "quantum computing" never comes into existence, the theoretical advancements inspired by it may serve as a lasting example of science created by accident, and similarities between science and culturally inspired nonsense including conspiracy theories, urban legends, cults, and groupthink.
This video is so interesting. Can you do a video on elliptic curves?
LOL I read somewhere (i.e. I am "reciting" from memory and not "citing" - okay citation nazis) that they were able to make a kind of black hole using sound, and were able to simulate behaviour of particles pairs splitting on a black hole's event horizon - i.e. one would fall in to the black hole while another would be freed - using phonons (sound particles/quanta). So maybe we'll see a quantum computer made out of sound or water waves? This was the easiest Infinte Series episode for me to understand, beacuse I'd already researched quantum computers, RSA, and read up on quantum mechanics and super-position. I was a bit confused with the constructive (3 dots on the dial) and destructive (6 dots on the dial) superposition interference of the dials shown in the video (interference happening every 3rd dot on the dial with 3 dots - constructive. And interference happenng every 7th dot on the dial with 6 dots - destructive [as it goes full circle?])... I probably got that wrong, but I get the basic idea I think in terms of waves.
Wonder if you could use audio harmonics and some clever geometric audio chambers to create an analogue computer to factor primes.
The 6-point circle at the end (which reminds me of Ouroboros kekulei) should have three left arrows and three right arrows, not a hexagon. Still adds up to 0.
so...will there be a good alternative for encryption when quantum computers can break what we currently use?
:P
Yes, if I recall correctly, there are types of encryption that are currently resistant to quantum computing and some are in use. That said, quantum encryption puts it into another level. There is this thing called quantum encryption. The basic idea is that if you transmit your message in qubits in just the right way, you can create a message that will destroy itself after first try decoding it.
WeepingAngel256 There are dozens of alternative classical crypto-systems for which there are no quantum solutions, and even if there are, if quantum computers take off, then one-way functions will be possible, meaning a provably secure crypto-system could be developed. Mathematicians are always a century ahead of the game.
Well in worst case scenario, public cryptography is abolished. We can still use encryption securely, but you'd have to keep a different password/key for every secure site you visit. The problem gets only worse for the web site, it has to keep a unique key for every user.
The biggest problem would be to negotiate these keys over the internet. One way to do it, is to have some trusted authority by both parties.
Yes, search term is post-quantum cryptography.
I paused this video before comments, then I went down a rabbit hole of wikipedia and google search on quantum computing and supremacy, etc, then come back to a her talking about another commenter doing the same. Yup. Community
15:47 thank god, I'm not alone
We just got into wave theory in engineering physics so part of this wave destructive stuff makes a bit of sense, fun cause it would be rad to use some of this tech in some of our huge simulation needs in the nuclear world :D
Still way above my pay grade, but gotta start somewhere!
10:00 starts to look a bit like phasor analysis, right?
also, a bunch of conventional computers put together already exists and is called a cluster. this is actually the first time seeing that as a description for a quantum computer.
This is a great video! (I work in quantum computing)
Thanks. You make it nice and simple.
Great video! But how many qubits would we need to figure out a period r for really large numbers N? Do we need at least r qubits or I am wrong?
Encryption based on RSA or ECC will become obsolete with quantum cryptography, in fact it is unbreakable due to Heisenberg's uncertainty principle.
If I remember correctly, there are companies that offer services of quantum cryptography, that if, should have prices a little exorbitant.
On the other hand, have quantum computers already gone from multiplying 2 numbers beyond 100?
Wow you are so good at explaining
This video might have been helpful 20+ years ago but today it's stupefying in context & a diversion from "reality(this AI construct akin to quarantine/Talos IV-The Cage-Menagerie-Zoo for esoteric humor)" itself.
Quick Question, if a
If I have a number of qubits storing the number 12, like b1100. And I would use this theoretical quantum computer to shor's algorithm my way into getting the factors. Would we set it up in such a way that the qubits (or another set of qubits?) would then exhibit constructive interference to spit out the number 1, 2, 2, and 3? So... 01, 10, 10, and 11?
I think falsification can be used to find factors of N , the problem is that we are looking at every possible number as factors instead we should look at probable factors of N like we can guess the pattern of the factors for eg ending with certain digits then we can easily find the factors of N.
Anything you have to watch three times to understand is a good thing.
Wow, you are a great teacher.
The quantum fourier transform for a=2 and N=7 would resonate at 3, 6, 9, ... right? In that case, would we need to apply QSA repeatedly?
This is such a great series. Too bad I'm just to impatient to understand all of this.
Is there a similar quantom algorithm that could break elliptic curve cryptography?
Yes. "Shor's algorithm" is actually a pair of algorithms with similar properties. One factors numbers; the other computes discrete logarithms, and can be made to compute discrete logarithms over elliptic curves, thus breaking elliptic curve crypto.
It's not my area but I've read from reliable sources that elliptic curve cryptography is even more susceptible to quantum attacks.
Hi, will you do a video solely on Fourier series and its various applications?
Deep learning for computing will be improved in the future, it's not as fast as the ideal quantum computer but we must continue the effort! Deep learning for mathematics is primitive nowadays. Not because it doesn't work, simply because we Earthlings are lazy sometimes.
Mind. Blown.
math layman here. hypothetically, since we're talking about decryption, could one try to avoid being "hacked" with their own quantum computer through destructive interference?
do you know where can i learn more of the swings and their periods ? That example is very strange, i think i understood the end result but i would be happy to watch it or read it in a comprehensive way
I'm going to need to watch this a few times...
The music
How about encryption protocols usch as SHA256 or SHA512? Would a Quantum computer be able to break usch encryption?
Those are hashing algorithms, not encryption protocols
Would finding the factors of numbers be easier to find like say 123
/2 no and can cancel all multiples of 2
/3 yes and count all the multiples of 3 except for the ones divisible by 2
/5 no and not count all multiples of 5
/7 no and not count all the multiples of 7
/9 no and not count all the multiples of 9
and so on. I don't know if it works for big numbers but it might help finding factors
I'm not so sure it's "just a matter of time." With the implementations of Shor's algorithm so far, knowledge of the correct answer has been incorporated into the quantum circuit. And it still only finds the answer about half the time. With a classical computer, if I already know the factorization of a number, I can just check it.
And that quantum fourier transform looks like something that is going to be hard to scale. It's interesting and all. And it's certainly a concern, just in case. But so far quantum factorization does not look as promising as it's being presented.
Im in love.
Alternatively, could quantum computing be used to find huge primes?
Why can't a quantum Fourier analysis be used on the hard search? Is the periodicity of the mod function the reason?
Whoa, the concept that I have of the quantum probabilities that lead to magnetism, lasers; were based upon this -- or surely something of similar provenance?
I love the music!
and the content of the video!
I usually understand PBS space time . . . but PBS infinite series. . it hurts my head. . but I still thought this video was great.
What does it mean to "record" where the dial is pointing? How does this translate to actual operations on qubits?
All this talk about wave functions and FFT made me wonder, in a somewhat unformed way, if rather than exotic new quantum computers, old technology analog computers can be used to crack RSA?
why shore algorithm can't run also on classical comp ??
Excellent.
i miss this channel
Why whould you check for numbers smaller than N? Shouldn't checking for numbers samller than sqrt(N) be enough?
Also, in the swing illustration, depending on the rate of energy loss, pushing every k*period would also resonate, right?
('cause you said "anything other than 3s.)
Also, why check all the numbers? If you are looking for prime factors, wouldn't you only see if N can be divided by the prime numbers. If N can't be divided by 2, why check 4, 6, 8, 10, etc...
Quantum Fourier Transform, but how the entanglement is involved?
Wouldn't you need to know the period beforehand to be able to amplify it?
FINALLY! Someone explained this in a way that makes sense! Now I just have to watch, pause and Google enough times until I understand the last part about constructive interference. I understand what that is... I just don't understand how it exactly works in a quantum computer to help make the correct answer more likely to appear in some cases
ua-cam.com/video/spUNpyF58BY/v-deo.html
You can watch 3Blue1Brown's video about the Fourier transform for more info about that interference thing.
Either this episode is a lot less clear about the subject, or I lack the mental capacity for it.
BTW, I love explaining quantum algorithms with Grover's search algorithm. I think it is much more tangible.
I am thinking to make project of RSA Quantum Decryption using IBMQ's
5-qubits sytem available online.
But, as you said Shor's algorithm cannot be applied, so can I do the shor on 5-qubit system on IBMQ??