Post-quantum blockchains | Valeria Nikolaenko

Transcript

[Music] thank you very much for the introduction uh yeah my name is Valeria you can call me Lara that's less formal I prefer that um if you're cool with that so today we're going to discuss post Quantum blockchains Quantum Computing this is an exciting topic I know it was prompted by your questions so you get the message here the more technical questions you ask the more technical talks you're gonna get probably so but feel free to jump in with questions if you have any I'd be happy to answer them as we go I think this audience has no other audience would probably appreciate this topic because it's very futuristic we are look we'll be looking far ahead into

the future and how the world of computing is gonna probably be changing uh governed by new laws of physics so it's kind of exciting but it has implications of the blockchains that are gonna devote a lot of time speaking about and what can we do to protect our blockchains in the post Quantum world so I want to start with kind of scaring you a little bit um you can argue that today blockchain attacks could have been prevented typically we look at how the attack has happened and we know what exactly was the problem and how it could be avoided so it could be maybe an implementation bug maybe uh there is an error in the code that got exploited maybe it was a

bad design maybe cryptographers didn't do a good job maybe they didn't prove the protocol secure and it was exploited that way it could have been also that the protocol was not decentralized that there was in fact a centralized party who was taking too much control over the protocol and this party got corrupt or hacked that's also a typical scenario for blockchain attacks there are many others but the type of attacker I wanted to talk to you about today is kind of a larger adversary it's not operating yet but it's kind of lurking in the future it did make come about and we will discuss what are the implications that it's going to bring so the adversary is a Quantum adversary I kind of Drew this Gloomy picture when

quantum computers come about that the world is going to be that gloomy doesn't necessarily have to be the case and I'll try to convey in more optimistic view around Quantum Computing and what kind of new Realms it can bring for us as computer scientists and engineers um so the main problem with the quantum adversary for our setting for blockchain developers is that Quantum adversary can break our blockchains in three main different ways really there are just three problems that we have to deal with if we are worried about Quantum attackers the first is an implication of the fact that Quantum photographers can forge currently use digital signatures so all the digital signatures we use in our

blockchains and all the internet today they're Quantum attackable we know efficient Quantum algorithms that can forge those signatures so those are all the signatures will have BLS ecdsa ddsa you name it so if an attacker can forge digital signatures it means that first of all it can steal funds it can just try to move funds out of honest users and into his own accounts so that's problem number one problem number two is that it can Fork proof of stake consensus it can break uh validator signatures pretend to be um impersonate the validators and just create an alternative work of the blockchain either disrupting the

blockchain to double spending or kind of disrupting the ecosystem that's a problem number two and the less of a known problem and only recently people have started discussing it is the implication for the Bitcoin for proof of work puzzles turns out there is a slight advantage that the quantum attack is going to have in solving proof of work puzzles and that might cause centralization of proof of mining power around the quantum adversary so it will kind of push away classical Miners and probably will be in the world where only Quantum miners are going to be supporting the Bitcoin um so let me give you an outline of what I'm going to talk about so first I will

explain what the quantum Technologies I will focus on three main topics here Quantum channels Quantum annulars and general purpose quantum computers those those are the main three kind of Technologies you're going to be hearing about when you read the news or when you research what quantum computers are people are talking about either of these three then I'll show you what's the progress in general purpose quantum computers and how we can extrapolate it to figure out when we're gonna get a large scale quantum computer so we will see how what's the current size of a quantum computer and how it's been growing for the last five years um then I will focus on the blockchain and why Quantum other series are a

threat we'll go into more depth on on all of these problems I just mentioned and then I explain how to defend our blockchains how to make them more secure so they're not susceptible to Quantum attacks and I'll show you a hint kind of just a glance at new cryptography that is being developed and deployed and explain how to deploy to protect the blockchains today all right so I want to start this main body of the talk with a quote from Richard Feynman who is saying that nature isn't classical so last century we figured that uh nature is quantum mechanical so if you want to make a simulation of nature you'd better make one to Mechanical and I think it's very inspiring quote

because classical computers are kind of boring things even others are just zero ones and you do some basic operations with those kind of classical analog bits but in Quantum world you can do much more fascinating stuff um and you know in the world when we have you know Dark Matter black holes um all these different Quantum effects when you start looking at the world at microscopic level it's kind of would be very interesting and inspiring to bring this new laws of nature that we just discovered and make them serve computer science so that we can either simulate the nature or we can maybe use it to

help us discover new laws of nature or you you know the possibilities here are endless so that really opens up like a new door for computer science I think to just look forward to possibly um so let me start with Quantum channels those are the simplest Quantum techniques you're gonna you're gonna see and they're not nothing fancy they're already practical today so Quantum channels are used for private communication you can if you have a Quantum Channel you can do secure communication with very minimal cryptography if you look at secure connections we don't want any internet today for example if you go to your website URL yeah you you do

um an https connection if you look at the amount of cryptography that happening there it's insane you have digital signatures you have public encryption you have message authentication codes um you have symmetric cryptography hash functions I mean there are tons of stuff going on it's a very complicated protocol just accessing your bank's web page but if you had a Quantum Channel between your computer and your bank you can do secure private communication with very minimal cryptography it's unconditionally secure assuming you have authenticated classical Channel I want to go into the great depth there but things become more simpler and when I say Quantum Channel I mean nothing fancy here Quantum channel is for example just

free space communication so if you have on Earth station and a satellite flying in the sky and you have direct visibility of this satellite that's a Quantum Channel that's it you can shoot polarized photons from your own Earth station to the satellite that's a Quantum Channel or if you have fiber optic channels between on Earth stations that's also a Quantum Channel and there are companies building businesses around providing functionality of quantum channels and recently or quite recently five years ago China made an experiment where they established a secure connection between Beijing and Vienna I think that's current record for the distance at which you can establish a secure Channel using a Quantum Channel Through Chinese satellite

okay so that's the simplest Quantum technology we kind of already started to have um in the real world another interesting technology is quantum Maneuvers those are special purpose quantum computers and they are used to um for optimization problems so here an interesting Quantum effect is exploited that the quantum system aims at minimizing the energy so it always will tend towards a lower energy state so for example if you're trying to minimize the function if you end up at a local minimum and there is a better local minimum nearby the quantum system will kind of slowly move to that local to that other better local minimum to the right

that's easier in with the quantum systems that's much harder with classical systems when we have gradient descent uh you know when you if you want to find another local minimum we have to start all over again from the top of some Hill and kind of going down you may not end up in a global minimum but with Quantum machines like Quantum Maneuvers that can be possible and the potential use here are the main one is training deep neural networks so you'll be able to find better solutions for your optimization problems there we do drug Discovery protein folding d-wave systems is a company to kind of uh that that's trying to build Quantum on yours and there are pioneers in this space there are a lot of controversies around d-wave systems every time they make an announcement

there is an army of academics trying to discuss whether their claims is true it's kind of an interesting debate to keep an eye on and finally quantum computers those are the technology we are really hopeful for those uh going to be general purpose solving General problems so if you've seen a quantum computer before is kind of this chandelier typically that hangs from the ceiling um and in fact the quantum computer itself is just a small chip that lays at the bottom of this chandelier and the whole chandelier is just a cooling system and it dumps vibrations so all it does all this fancy golden wirings they're just cooling the tiny chip at the bottom and the size of the quantum

chip is not much larger than the size of our laptop chips um so because of this kind of complicated cooling that has to happen to create this pristine environment for the quantum chip to Lion uh it's unlikely that quantum computers are going to be embedded in our laptops or as we will it's unlikely we're going to have an as personal computers those are going to be cloud-based so we'll have a bunch of personal laptops kind of connecting to a quantum computer over the cloud so that's good news because it means we still have to develop classical cryptography and classical machines are still going to be in use not everything in the world is going to be replaced by quantum computers if you're going to build them so they are

likely going to be just used for hard computational problems that you can just send over to them they will compute the solution and give it back to you okay so where's the power of a quantum computer coming from it's kind of complicated to explain I won't go into great depth but I give you a hint at why quantum computers are more powerful than classical and the power is coming from the qubit so if you look at our classical bit it can only take two values zero or one occasionally the bit can give errors if there's a cosmic ray hitting it it can Jitter a little bit but more or less it's just two values zero and one qubit on the other hand can take a whole spectrum of values in fact the qubit state can be anywhere on the sphere or

on the circle in a two-dimensional space between zero and one so it's a superposition of the two states of zero and one and because qubits can take this whole range of values they are kind of more expressive you can already see that they're more expressive than typical bits uh the way to the the most promising technology right now to instantiate the qubit the superconducting circuits that's what IBM is using you can also do trapped irons photons but those have to be really tiny and those have to be cooled down um to absolute zero temperatures in order to exhibit the quantum effects and if you apply you can apply

transformations to your qubit and what's going to happen underneath the hood is you're going to be applying your function f to both values zero and one so if you're starting with a superposition of zero and one and you apply the function f you'll end up with the superposition of f of 0 and F of one so for one qubit you can compute F at both values at once okay you apply F once but under the hood you're Computing it twice if you go to more qubits so if you look at two qubit 2 qubit system can be in superposition of four states yeah all possible combinations zero zero zero one one zero one one those are four values two qubit system can be in

superposition of four values when you apply the function um you'll end up applying it to all four possible values under the hood and if you go to a larger qubit system like n qubit system you will be Computing a 2 to the n the possible combinations of this bit values okay so this is really where the power is coming from and under the hood you're Computing the function exponential on exponential many values well you only do apply this function once effectively um quantum computers so though there's this exponent there it's kind of they're not it's not straightforward that they um that they give exponential speed up in fact they know it but they are really

great and helping us understand the properties of the functions that just because they can avoid the function at many many values all at once but this is really where the power is coming from okay uh so let's see um what's the progress in Quantum Computing in recent years so here you have a growing uh chronic if you're you see how the number of Cubes grow so the last years and in particular I want you to look at the last five years so IBM and the U.S spy nearing the space we also know the Chinese building a quantum computer but we don't have public announcements around that so IBM numbers are really promising the last five years the number of qubits are

doubling and this year they plan to announce a thousand qubit processor so I would say if it continues to double each year we can call this progress quite rapid so there are two main Quantum algorithms that you should be aware of and every time you read about quantum computers you will Loop you will see dimensions of the sub two algorithms probably both are from the mid 90s their Shore algorithm and Grover's algorithm sure algorithm gives you efficient way to factor numbers and to solve discrete logarithms and that's the reason why our today's cryptography gets broken just because

schwar invented this really efficient algorithm for factoring and finding discrete logs and Grover algorithm improves the search problem so that has some implications for symmetric cryptography and hash functions they're going to talk about in a little more in just a second uh so let's focus on short algorithm just because that's the most important algorithm for blockchains so for our algorithm for factoring um if you have a large number and that is a product of two primes um to find the factors to find p and Q quantumly you only need to spend polynomial time so the length of n to the to the to the to degree three operations on quantumally and

classically we don't know anything better than normal Fields if which takes exponential number of operations so quantumly you have a polynomial time algorithm but classically you only know how to factor an exponential time so the implication is that we know RSA would be quantumly broken and RSA certificates are 90 of the internet okay so if you go to any website if you click this green lock button next to the URL in your browser you look what certificate they use to secure a connection it's likely going to be RSA certificate so if RSA gets broken that's we are in big big trouble and the rest of the certificates are kind of discrete log based and turns out short algorithm

generalizes to discrete log based certificates as well so basically if somebody builds a quantum computer today the internet is gone okay so I just want to take a moment and for you just to imagine this world like what what it's going to be like so in the presence of a quantum computer out of the internet is completely insecure so what it means is that you can attack you cannot access your bank web page Banks cannot do Financial transactions the blockchain stops working you can't send secure messages you cannot even you know upload the update to your machine to fix it to make it quantum resistant so it's really really devastating we hope nobody is building a quantum

computer kind of in private right now and we really hope that nobody will just show up for the quantum computer Bureau all of a sudden um yeah so Quantum attackers will be able to read all the traffic and impersonate anybody on the internet all right so uh that's kind of a gloomy view of the world let's uh let me show you a little bit more optimistic view so the largest current processor has 400 qubits but how many qubits do you really need to break cryptography Well turns out you need a lot more so for example you need 20 million uh qubits to break RSA and 30 million to break elliptic curved the Hellman so you see this gov is quite

High okay we only have 400 and we need 30 million but the number of qubits seems like it's doubling every year so if it continues along the same lines it will if it will continue to double every year this Gap will be breached in 15 years so that's kind of enough time for us to prepare probably but it's kind of a short amount of time that we might you know want to keep an eye on this and the progress that we have here uh great so I went also to highlight the recent paper that came out last year December 2022 that were saying that they figured a new algorithm to break RSA and

you can now run it on an existing quantum computer so it only requires 372 qubits to break RSA and it caused a big hiccup of the community like everybody was suddenly in panic people started you know analyzing the paper seeing if the claims are really true or not and after a while a few weeks have passed people concluded this paper has some problems that the claims are not quite true and the RSA is still secure and Peter Shore in fact is quite active on Twitter if you want to follow him that's the author of The algorithm that breaks RSA he was saying that this paper apparently has problems but it might be the case that as we go we see more and more results like that and we might better think about how to

prepare ourselves just in case some of this result turns out to be true and even if you're on the skeptical side and you think that the probability of building a quantum computer is small just think about the huge devastating effect that is going to have in our world in our society so if you multiply this tiny probability of building a quantum computer with tens of millions qubits if you multiply it by this huge effect that it's going to have maybe the probability one seem so small anymore but uh I want to just for a second take the side of the Skeptics and say that we from quantum mechanics we know that when we have few particles when the particles are really tiny they exhibit

Quantum effects but when you start putting a lot of quantum particles together they start looking more like a classical system so for example a tiny electron can go through two tiny slits at the same time so it exhibits a Quantum effect but we as humans we are considered many many electrons and many many Quantum particles we cannot go through two doors all at once so we're classical beings so it's the question of whether we can keep increasing the number of qubits and keep up this Quantum effect present or rather the system will start collapsing to a classical state so we still don't know if the physics kind of created a ceiling there that we cannot penetrate and maybe

we will not be able to grow our quantum computers to have millions of qubits but we will reach some ceiling maybe in the future we don't know we'll still need to find this boundary of physics but so far you've seen that the number of qubit qubits grow quite rapidly yeah doubling every year great so um going back to our Quantum adversary that can forge digital signatures of the bad news of course that is the supplies to all current use digital signatures all of our favorite ones and there are two problems for blockchains going kind of back to what I said in the beginning uh Quantum watarka can either steal funds on the honest users accounts or it can Fork proof-of-state consensus it can

do both as well and the good news is that there are secure Alternatives we started developing New cryptographic Primitives that we know that we kind of a confident or secure against Quantum attacks and let me just give you uh two slides kind of summary at what those Alternatives look like and the Pioneer here to just keep an eye on its nist its National Institute of Standards and Technology us-based institution that pioneered the post Quantum standardization effort nist is a prominent body whatever cryptography standardizes ends up kind of used all over the world so in 2016 nist announced the competition he kind of recognized that the quantum computers might come about

and we need to start preparing for this event if it happens it announced the competition and asked academics and Research Laboratories to submit proposals for new secure signatures and it got a ton of submissions I was on one of them and um it was really nice to see this collaborative effort of the community trying to come up and standardize your cryptography for post Quantum world uh this summary announced the signature final is that it's gonna standardize and next year anist is going to roll out the standards so it promises so far it's been keeping up with the schedule so the finalists are three new digital

signature schemes the lithium Falcon and things Plus and just to put this number three into perspective the digital signatures that we use today are just three we have only three standard signature schemes ecdsa RSA and addsa and we also love and use BLS now all over the place it's not standardized yet there are decision efforts but this kind of adds a four signature so it's only four signatures that we have on our toolkit and it's really nice that nist started adding new signatures we're gonna almost double the the number of signature schemes that we have on our toolkit which is great the bad news is that those signatures are gonna be horrible for us so at the bottom those are the signatures that we use today you see

though they have really tiny public and signature key sizes it's just tons of bytes but this new signature schemes that missed will roll out standards for kilobytes in size and the public is really large so if you ever was worried about the ever-growing state of the blockchain just imagine how much larger the state going to be if you are to use post Quantum signatures so for blockchains you know it it's not the end of the world like several kilobytes we probably can handle it but it's kind of nasty it's not going to be easy to maintain the same performance with this new signature schemes so the top three are the coming standards there is an already existing

standard that was standardized just in case because when you how to do stateful Post Quantum signatures the problem with stateful is you need to maintain secure State and it's very hard in practice if you suddenly crash and reboot and you don't know how many signatures you've already produced and you reuse your state the security is gone its signature scheme is very hard to use but in devastating in fact that suddenly a quantum computer comes about there is a signature scheme that can be plugged and the new promising uh new signature scheme sqi sign that could be nice for blockchains because the thing the signature size and public key size

is small is not was not part of the competition it's very very new but people keep an eye on it the problem with that is that signing time is horrible it's like tens of thousands times slower to produce a signature so in consensus is going to be traveling to have to use it maybe for wallets it's going to be fine all right so let me walk you through the transition of blockchain account to post Quantum so the access is the time and we are now in this green region we're accepting classical signatures only at some point when good post Quantum signatures are available when new standardizes new cryptography we can maybe start accepting both classical and post Quantum signatures so

have those bottom three signatures and top three signatures accepted and then when we expect the quantum adversary might start to exist close to that region we can restrict our users to only use classically signed transactions to do key rotations to post Quantum keys to make sure that first thing they secure their account against the quantum adversary so they rotate their key and then they can transact using the secure key onwards and then there is this red region where we know the quantum attack might exist so we cannot accept classical signatures in our blockchain so that's a happy path if we if our predictions are correct if we are

standardizing good signature scheme just in time and we have when we have good prediction of when the quantum attack might exists and happy path uh we're gonna be in the world like that if quantum computers are possible but the problem the main problem with this approach is that what do we do with sleepy users so if you created your account in this green region and then you didn't transact at all and you woke up and suddenly you're in postcondu world and your classical signatures are not accepting accepted so what do you do how do you transact out of your classical account so um the easiest approach to do is to introduce a hash somewhere on the path from the secret key derivation to the

public key or others derivation and the hash will act as a shield for the secret key because hash is a Quantum safe we don't know if affect efficient algorithm to attack the hashing so uh by introducing the hash on the for example by hashing the seed to produce the secret key you are creating the shield for your secret key and then later on if the user walks up and his signatures are not accepted anymore he can use a stark proof to show that he knows the seed to show that he is the owner of the seed that he knows it and be able to transact out of his account in the quantum safe account because fortunately we know zero

knowledge Stark systems Stark proofs are quantum safe as well okay so we can use the hash and Stark proof to help those sleepy users but that's something to design for in the beginning you have to keep this in mind and if you want to be post Quantum safe for sleepy users you have to introduce this hash somewhere in your derivation of the secret key that's important for wallets um and the other problem is that Quantum attackers can Fork proof of stake consensus So validators currently has to improve of stake assigning blocks with classical signatures but if the quantum attack comes about it can just go back in history and uh Forge validator signatures from some point

creating alternative blockchain there are two problems first of all Quantum at Target can double spend and can spend funds on the top chain and at the bottom and also it can confuse the user as the user will not be able to differentiate which chain is the correct one what's the correct file that you said so it will cause um it caused a lot of disruption as well so to protect against that um the current most viable solution is to make validators produce Quantum safe certificates ask validators to use this heavy unpleasant post Quantum signatures to sign blocks infrequently and then frequently just because those Quantum signatures are expensive they're large

and they're take more time to produce so we can just ask the validator set when it changes to produce a post quantum a signature certificate on the Block before they change the validate set and you can start with varying infrequent signing but you can put those certificates closer together and ask about the validators to sign more and more frequently as we are kind of approached as the number of qubits in the quantum computer grows and we think we might be approaching post Quantum State at the end just having a validators sign every block with post Quantum signatures okay so that's the protection you're gonna you can introduce today to defend

your consensus okay so there are two actions for blockchain developers the first one is kind of easier to roll out you just introduce the hash on the past the secret key derivation and the other is kind of more complicated because you need to implement this post Quantum signature Alternatives there are implementations available but those are kind of prototype State um but that's something you can also do Implement post Quantum signatures and ask validators to sign using those signatures infrequently cool so we looked at Schwarz algorithm we just saw how to protect blockchains against that and let me quickly show you the Grover's algorithm it also has some implications but they're not so devastating as for

sure um so Grover's algorithm is for search problems if you have a function that takes n bit input produces zero one the search problem asks you to find X such that f of x equals one so classically you will have to trial possible inputs and do two to the N number of steps to figure out where your function is one and quantumly and very surprisingly turns out you can do this with fewer number of steps it's not exponentially fewer steps but it's still an improvements it's 2 to the N over 2.

and this was a very exciting result because it showed the separation between classical and Quantum algorithms you know showing concretely that quantum computers are more Superior to classical and the example here is for example finding pre-images of a hash function for some value H you need to find the message M such that the hash of the message equals the value h so Grover's search will be faster than classical here an implication for the blockchain is that Quantum miners will be solving proof of work puzzles faster so in order to search DSi space Quantum miners will be spending square root of D time and

classical miners will be spending D time so Quantum miners are going to be faster so that's something to keep in mind if you're worried about if you're designing a proof of work blockchain that's not a problem for proof of stake of course and uh the possible implication for hash as I shown in the example is that you can find primages faster but that just brings you know pretty much resistance to much Collision resistance but the hash functions stay secure um you cannot improve on the Collision resistance and you maintain 128-bit security for both problems so hash functions is really not a problem hash stays secure in post Quantum world cool

um so I am ready to wrap up and give you some thoughts to take home so the progress in quantum computers is very rapid um with the same face we can break cryptography in 15 years but we might be bounded by the laws of physics we don't know if there is a ceiling that we cannot penetrate or not we will see maybe we'll see this in the next five years or so whether we um we can keep keep up with the growth in the number of qubits or not and the quantum addresser sign did a threat for blockchains but we know how to defend them so there are two action items for blockchain developers that I showed you one is to protect your secret

key by introducing a hash by the way Bitcoin for example does this naturally because all you see on the blockchain is the address and the address is the hash of the public key so you don't see the public key itself um you only see the address and that also gives you a shield um from the quantum attacker if every time you transact out of the address you Reveal Your public you rotate to the new key you're fine so Bitcoin kind of naturally has this protection by the way but that's something you can do for your blockchain and the other is to protect the consensus you need to periodically sign with post Quantum signatures um okay and I I think it's really

exciting topic and it's worth keeping an eye on it those I would say that the quantum mechanics is really hard to understand and even physicists they debate on um how it should be interpreted and what it really means and it might be another topic like similar to AI where we know how to use it and it's very useful but we just don't understand why it works so you can do the same with Quantum Computing that we build quantum computers but when you're trying to understand why quantum mechanics works why the quantum computer is actually behaving the way um it is can be like out of the possibility for our human understanding

uh great so I want to conclude with suggesting using further reading on the topic there is a classical book like textbook on any course uh it's called Ike and Mike and Ike informally it's kind of old but it um covers the whole Century of developments so from 2010 it still remains to be a classical textbook I think the best way to get started if you're interested is to watch online lectures there was a very nice course by mesh bazirani he was a professor at Berkeley uh he did a mooc in 2013 on Quantum Computing unfortunately it's not archived on the official website but you can find YouTube lectures archived by

some enthusiasts I really encourage you to follow Scott Aronson and he has a lecture notes published it can be read as a book as well it's available online it's a very pleasant read if um you don't need to know a lot of math you're going to follow and Scott arenson's block is the best way to kind of see what's the recent news in there none of that will go unnoticed by Scott and he will come and then on that and give his thoughts um they can be controversial even you may disagree but that's a great resource to just keep an eye on what's going on in the field fantastic I think that's all I have in

this bonus line there [Applause] hi Emmanuel from Shield awesome presentation um so you mentioned that uh the the whole study that basically talked about how many qubits would be necessary to crack the RSA certificates um that was like a dispute um and validated so I'm wondering what goes into those calculations of like how many qubits are required to crack a specific system and how trustworthy are those calculations uh today yeah great question so typically the algorithm is described and you just look at how many qubits it needs

um so it's pretty easy number to just figure out just looking at the algorithm uh the the what makes it a little harder is that typically those algorithms are designed for logical qubits assuming the system performs um without any errors and just performs correctly and that's the operations that you want there to be done but unfortunately in practice that's not the case the qubits are very very noisy and you need they they err all the time you need to repeat the computation many many times where you need to apply error correcting codes so a lot of calculations about what the actual number of qubits you need will go into figure out what error correcting scheme you need for that for that algorithm so

that's not such a trivial problem if you really need to figure out the number of physical qubits yeah but that's a great question error correcting is definitely something quite painful for the developers of quantum Computing there thank you thanks for the great talk um Nikita from chain Patrol uh I had a question around you mentioned that the you know the quantum system will try to enter into like a lower energy state so it's useful for like escaping these local minimum um does it have like a limit on how far it can kind of like travel or move is there like a certain like it won't jump further than like a certain barrier so like yeah well that's my first question is there a limit yeah that's a great question that's indeed the main critique

of this computers is that if you other local minimum that slower is too far the system will not penetrate that barrier so it only um it's not going to work for finding Global minimums of any function it's only kind of will be able to penetrate small barriers yeah for shorter jump space exactly for sure okay yeah and then uh just one more question is around um you know when dealing with digital like you there's in when you're doing like arithmetic I don't know like machine learning or something you always have to do all these tricks to like get sort of like floating Point errors but here it seems like it's more like you can get any value in between so does it get rid of like basically like floating Point errors and you know like overflows

and that kind of stuff oh great question actually it's very interesting you ask that because indeed you may think the qubit is you can kind of encode yes in superposition of zero and one with some floating Point coefficients that's true and in principle you can encode a lot of information into each of these coefficients because those are real numbers but in practice the information that we use extract information from the qubit is you measure it and when you measure it it only collapses to one of the states with the probabilities that are defined by the sex and Y so we only get zero or one in fact it's very difficult to get a sense of the values of X and Y if you don't know them so if you want to figure out the floating Point number you can

only ask why you can only figure it out with certain Precision okay um yeah you will not have infinite Precision there so we're dealing with 14 hours is still tricky that's really interesting thank you sure so if I remember correctly um like from complex classes forever ago where they have you prove lots of or if a problem is non-polynomial a lot the often way the way you do this is use like the NP reduction where you sort of take a non-politanober problem and turn it into another problem and you can sort of say you eventually come to the conclusion that like any non-polynomial problem can be represented as any other non-polynomial problem right yeah um so does the existence and you can sort of like use the individual non-polar problem as sort of like a

uh inside as I got like an inside step right and you come out in polynomial time so does he exist in something like Shores algorithm which is like was a classically like a known non-polynomial problem mean that you could take any other non-polynomial problem right and represent it as Shores out or as a factoring problem right so there's like there's just the existence of Shores being solved in polynomial time in a quantum computer mean that like you can solve all of the non-polomial problems in polynomial time on a quantum computer or those is there like some Quantum stuff that makes it not possible yeah great question sure is kind of this factoring is kind of the special problem that doesn't have a lot of problems reduced it it's not like NP complete or something and it can well be that you know we figure out suddenly an algorithm

to classically solve factoring quickly so for example um for primality testing long for a long time we didn't know a deterministic algorithm to do primality testing and we thought this is an exponential um this is a super polynomial this request super polynomial number of steps and suddenly there are like I think two undergrads from India kind of figured out the logarithm to do deterministic primality testing so I think it's the same kind of might possibly happen to factoring that we kind of figure out an algorithm it will not collapse you know and P2P or collapse any complexity classes if you're asking about that but it it's

interesting though the the quantum algorithm that breaks factoring in fact underneath what it does it's there's an efficient way to find periods of periodic functions so any problem that can be reduced to finding periods will be able will be able to solve it using a Quantum appear in polynomial time so for example discrete log reduces the fighting periods and the factoring reduces defining periods um and there are other more generic problems that reduce to it as well but um I don't think there are many useful problems that we know of yet that will have will be able to use short so then the hope is that like finding uh

finding periods is not a real non-polynal problem so that there is like hiding somewhere like a classical solution uh you know so it's possible that we have a classical solution for this problem but so far when we know how to do it deficiently on the quantum computer cool thank you hey Brandon uh thanks for the talk that was uh really really cool and futuristic so I appreciate it um it seems like the framework we're using here is that in a post Quantum world we have an adversary with a with a Quantum capability and the network doesn't have Quantum capabilities and so we're trying to like defend information using time with more advanced uh signature algorithms are there any

thoughts around like what about if the the good guys also have quantum computers are there like physics properties that we can use aside from information and secrets to make things Quantum safe yeah that's a great question I didn't touch on that field that's a completely people are trying to design cryptography specifically for Quantum Computing it's very exciting there are lots of new developments there um you know it's very it's even more futuristic of course there but it's definitely possible to design cryptography new cryptography there well if we're in there in the settings that I was describing where quantum computers is cloud-based and we have classical machines connecting to it we still will probably need classical cryptography so

it's going to be it's going to stay with us in the sports Quantum signatures we're going to still be using but indeed the quantum computers to talk to each other they might use some more fancy stuff I think it's very premature kind of to see the algorithms there but there's definitely some academic work there oh yeah thank you so much yeah sure I understand this might be a bit more science fiction but uh is as faster than light content and entangled communication um I'm curious if if there's any efforts developments in that direction yeah yeah this China experiment that I was talking about briefly that they established the secure connection between Beijing and Vienna I think uh was the way it works is the satellite was producing entangled

photons that they it was shooting those two two locations to Unearthed locations and they were measured there and that's how you know you get the same um well it's more complicated than that but that's roughly that's that's really kind of was was done in an entanglement in general uh was demonstrated already quite a few years ago um but the challenge right now is to grow the number of qubits that can be entangled and maintain them in the entangled State because this Quantum systems they are super Fragile the moment you touch it classically it kind of collapses to a classical State and the entanglement is gone so it's really

the challenge of maintaining entanglement of a large group of photos of qubits so would you say like quantum teleportation is something that might be possible then quantum teleportation or uh you can actually direct it have directed data yeah yeah yeah I think it was it was demonstrated definitely as well so um it's not that you're communicating with a speed of um light larger than the speed of light but the way it it works is that I can transfer my qubit to you uh if we have also a classical channel of communication so um without physically sending you the qubit you will be able to get the same qubit as I have so

not the same but I will destroy my qubit and recreate it kind of on your end uh using a classical Communication channel so you need still this classical Communication channel to just talk to each other but Quantum States can be teleported they cannot be copied yeah but they can be moved around and they can also there are some interesting transitive properties like you can teleport to another guy if we if I teleport with you and you teleport with him you know you can teleport your key with sorry some transitive properties you can do as well but yeah that's definitely very interesting um thank you very much really fascinating um hi there my name is Marat fascinating talk thank you very much

um I have a question about this kind of the cold zero Kelvin requirement of quantum computers would it be feasible to have you know quantum computers in space that compute things and then maybe we interact with them um through Earth and you know they they maintain them I guess a more manageable environment over there and it's de facto zero Kelvin yeah I agree that might well be our future indeed because yeah you're right the we have cooling for free in space and there are no vibrations so indeed I'm not aware of experiments in that direction so but I bet there are some trying to to study Quantum effects in space

um but that's true the more satellites are being launched the more likely we have more compute power in the sky and maybe those satellites can talk to each other using these Quantum channels um establishing secure Links of communication that's I think that yeah that might likely so then we can imagine a future where maybe we don't have chips in our phones or they have very lightweight chips but you know it's kind of a Mainframe type of architecture where things are kind of in space and we're able to you know use quantum computation for that yeah exactly yeah thanks for validating the feasibility if my startup here for some reason does work I might pursue something in space like this thanks for the question

hey um it seems like there have been some issues with the post Quantum algorithms and the nist competition um are there further concerns that attack vectors might be found is is there anything in particular about post Quantum algorithms that makes them more susceptible to attacks yeah the main great question the main problem of course that this cryptography is newer and there's less started it's really nice that it's a collaborative effort and it's very massive so it gets a lot of eyes of people trying to break it analyze it I would say that those three signatures that nice has chosen are very conservative choices two are based on

lattices and we know this is a very well established long-standing assumption as well so we have good security good good confidence and it's security it's unlikely that we're gonna see any problems with those schemes and the other ones things plus is a hash based it's super well studied it's only based on hashing nothing else there are no other mathematical assumptions so that's the most conservative variant unfortunately it's the less deformant if everything is much slower with things but I have good confidence in the schemes that nist has chosen I I bet nist will choose more because just the signature sizes are not satisfactory in fact it's opening another call for

proposals I think this summer to encourage people to think of more signature schemes with shorter signatures so we'll see what goes in there maybe some more fancy assumptions have to be introduced that will be less confident about thank you Lira I have one more question if there's no more from the group um so you had a slide on like the physical design of quantum computers so it's actually just like a chip and the rest of it is the cooling infrastructure yeah um and because of that that you don't expect that we'll ever have you know Quantum chips within laptops or even phones um is that like a physical limitation and a certainty going forward or do you think that it's possible that you know similar to the way that other computers have gotten smaller and smaller over

time that the same thing could happen with these Quantum chips yeah good question maybe possibly um that we have a small tiny cooler inside our phones that will be able to maintain this pristine environment the vibrations are also a problem you know I think probably technologically there is no like physical limit to why we have to have a cloud-based quantum computer maybe it's just going to be that way for a long while until we kind of figure out how to miniaturize everything but that's true possibly at the end of the day we're gonna have quantum computers on our phones that's right no I am not aware of any physical limitations but thank you Laura it was great thank you [Applause]

[Music] foreign