but um maybe what he's best known for is his work on you know he's he's the person who really started thinking about Quantum algorithms in the context of Lattis problems in a in a very deep way and and that led him to the to Define this lwe problem which which of course is the central character in postquantum crypto and so today it's um he he'll tell us about something that brings luses together with sh's factoring algorithms so or that's looking forward to your talk great thank youan yeah I sho
uld I should say that I owe you a lot to measure support when I was there in fact learning with errors I I remember walking in on campus and uh while I was there pooc with you and uh this is where it all started so uh I'll tell you today about uh this um efficient uh algorithm for factoring uh in ERS and uh as I was saying before feel free to interrupt and ask with um you know if you have any questions so let me start just by Define the problem which I assume you've you've seen before so we're t
rying to factor integers and if you have 15 it's okay 3 * 5 if you have 21 is 3 * 7 55 is 5 * 11 1843 is you know a bit a bit more difficult 97 * 19 and already gets more difficult so 1851 is a number that I use as a running example it's it's not not as easy to factorize and actually there's nice story that Carl pomerance uh shared and this is his experience from a high school math contest so he was asked to factorize 851 and he was sure he can just try divide you know you only have to go up to
square roots so it's up to about 90 and you know he sure he could do it but he thought let's try to be clever because surely there's a better way of doing it so he tried uh and he spent a couple of minutes trying to find this clever way but then kind of got worried that he's is wasting too much time and indeed he had wasted too much time and he missed the problem uh and this experience must have been quite kind of traumatic for him and later he went back and you know figur out the trick and the
trick is actually you can write 1851 as uh 8100 - 49 so it's a difference of two squares 90 squar - 7 square and this you can just write in this nice way it's 90 - 7 * 90 + 7 which is 83 * 97 so there's a very nice uh article he wrote about this in the notices of the AMS I highly recommend this uh and basically this led him to develop some of the fastest known algorithms classical algorithms for factoring ERS like quadratic seal so this idea was quite influential this high school math contest ex
perience was quite influential frame so we know factoring integers is a difficult problem current world record is 250 decimal digits it's like 800 something B binary digits maybe 40 and it took 2700 computer years so it's extremely difficult problem um you know and this this is really um uh just something that we don't know how to solve using classical algorithms the best known algorithm number field SE is actually surprisingly fast so it's a development of the quadratic C I mentioned before but
pance was involved in many of those things and and it's actually remarkable algorithm and it it is remarkably fast and yet it's not polinomial time it runs in this an exponential time in cube root of number of digits so you know so it's actually it's able to do do amazing things but you cannot factor numbers with 800 binary digits so it's not n hard I should say must have heard this before the problem is not NP hard you know it's a cryptographically hard problem and uh secure communication of c
ourse is is based on this so you know cryptography is typically based on this and uh you know we we assume we we conjecture that factoring is hard and and you know that's how we build uh all uh cryptograph this how you used to build all of cryptography until uh recently okay so this is where our story starts and 1994 Peter shw discovers factoring is easy for quantum computers and I think that's what uh why what what brought many of you to Quantum computation this is this a phenomenal result uh s
howing that quantum computers can break cryptographic all the cryptographic encryptions that uh that were used uh and and at the time um you know RSA and then the curve and whatnot so this is a huge uh huge breakthrough and and really worrisome because it's saying basically we cannot use cryptography anymore cannot encrypt our you know email and and and and bank and and so on uh but it's not really the end of the world okay so don't don't panic yet um well partly because this transition that sta
rted recently and some people here have been uh very involved in it uh this transition to postquantum cryptography started I would say in Earnest uh last summer um and slowly many protocols and and U you know instance messaging and and web uh https and so on story switching or maybe quickly switching to this kind of post Quantum encryption supposed to be uh based on other problems that are not uh factoring like problems and then presumably are not susceptible to this kind of algorithm like sh's
algorithm so so it's not the end of the of the world and maybe another reason why you would say let's not worry too much is because quantum computers don't uh exist uh but that's that's something that maybe more of a question mark because it seems like they're coming right it seems like every day now we hear about you know bigger and better quantum computers and there are issues but it's the seems Ty progress is being made and who knows maybe uh in a few years we really have big uh phot over in
the quantum computer so we know you you've seen some of those uh uh news releases and you know this is a one every basically every week these days uh with more bigger and better quantum computers that's this nice uh figure I stole from samjack uh and and um it shows where we are currently in terms of number of tuits and the error rate that's as of 2021 I think so things have you know keep changing there are more cubits you know better architectures and so on um there are a bunch of other things
happening here which I don't know much about and there's this is basically where shorts algorithm starts kicking in in terms of number of cubits we need uh the error rate so you know I don't know how up to date this is but basically just just to convey the idea the idea as we are trying today try to tell you about an attempt to bring this down right trying to find more efficient ways of factorizing integers okay so it's this kind of what we're trying to do hopefully maybe the two ends will match
or get close to being match and you know we can talk about this later during the panel okay so without further Ado this is the main result at this point you know again feel free to interrupt with any questions so let's go over it it's actually um basically saying there is the Quantum Factor ing algorithms but that's exactly what the all the the small print is saying so okay so there's there's an algorithm factoring n bit integers okay the way it works is that you know you need to have a Quantum
circuit okay the quantum circuit has a relatively small number of gates that's that's really the the claim to fame you know this is really the the novelty here the end to the three Hales end to the three halves instead of n squ gates in short algorithm okay so it's a smaller circuit uh and then you know it actually needs to apply the circuit multiple times it's not like you run the circuit you measure and that's it you actually have to run the circuit measure and then then run it again independ
ently you know and and measure and then run it again so you do it a bunch of times you can do it in parallel there's no dependency between them you just do it a bunch of times each time you get a measurement and you just have to then combine everything do some kind of classical post processing and and and you get the output you get theorization okay so this is kind of very briefly how how this thing works again if if you just look at this you think okay this is ridiculous because n n to the thre
e Hales Times Square Root n is also n squ so what did I gain um What I Gain Is that the quantum circuit itself doesn't need to be so big so in principle you don't need to keep it you know maybe coherent for so long or principle it might be easier you know all else being equal right in principle a circuit with fewer Gates should be easier to implement Okay so before you protest uh uh I'll discuss this more in the next slide but this is the idea we want to reduce a number of gates we have to run i
n the circuit running the circuit later Square times should be you know should be okay should be something that uh we can just we can just uh questions so far oh Ron I have a question well sorry okay even better what's the mild theoretic number theoretic assumtion yeah so there's okay let me two two small uh small print here right so there's um uh let me start again with Mish mild number theoretic assumption you'll see later where it shows up um and uh let me get back later to where it shows up
we need to assume something that Peter Shore doesn't have to assume later you will see where it shows up um I'm currently working with Igor palinski trying to prove this and I think we have maybe convinced ourself that it's probably true uh but we are still unable to prove it we can of know where the know what the what the reason is or we have some better sense of where the challenges are and actually proving it rigorously say based on something like gr so we unable to prove it not even based on
gr but you know we have more confidence that this makes sense it's something that I don't know maybe number theorists will tell you should obviously be true but certain things are kind of difficult to prove you see where it comes up later it's something about like small numbers generating the group of the multiplicative group so so if you're talking about the G I mean just by intuition does this mean that your algor you can prove that your algorithm works for some large fraction of the nbit int
egers so that would be enough I think I I would be happy with such a result like saying okay for not maybe not you cannot factorize all and be integers but you can do it for a large fraction but even that I don't quite know how to prove yeah this is good yeah it's a good point even that I don't quite know how to prove Ronald yeah so this is a question about parallelization you can think of your result as sort of partial parallelization of shes algorithm but there's a a much more extreme parallel
ization known due to Cleveland watus that says that you can do uh Quantum factoring in like order log and Quantum depth with polinomial time classical pre and post-processing so I wanted to ask how this compares right so that's a great point and and I think I'm actually specifically this point not mentioning depth uh I will maybe mention it in in the next slide um and I think in their approach they really care about depth right to make they make the the circuit very uh shallow the number of Gat
is actually much larger uh so yeah so it's a different different trade-off uh I would say if you care about number of gates it depends again depends on the quantum architecture if this is really what you want to optimize then maybe what I'm showing today maybe is the way to go but yeah this is highly relevant right if you care about dep this not a the figure of Merit that I'm really focusing on and I should should probably mentioned that other you there's other work on optimizing short algorithm
in different directions yes definitely depth if you really want to minimize that you can do it there there basically uh nice way of you know paralyzing multip apption and so on yeah very good point okay so uh I should also mention this was extended to the script logorithm so what I'm showing you today is for factorization but you can look at this uh uh I think still a preprint by aaran gerner showing how to do it for thisr log and also I should also say it's important this the numbers I'm showi
ng here uh this ENT to the three halves the N squar it just for convenience I'm assuming that you have fast integer multiplication so for those of you who care more about practical size like 2,000 bits that's probably not too relevant but you just have to scale everything up appropriately so this would become n to the 5 halfes so n to the 2.5 this would become n Cube so so everything proportionately scales up so there's still the same Advantage even if you don't like to use fast integer multipli
cation so for convenience today I'll assume that we have uh nearly linear time integer multiplication but the same thing happens the same uh Improvement U shows up also without that assumption more questions okay so now let's maybe say bit more about implications in practice and again I'm saying practice in quotes because I don't yet have a really quantum computer to test it on so you know it could could depend a lot on the architecture and if you have a super conductor in cubits uh if you have
uh you know trapped ions if you have neutral atoms if you have Optical if you have so it depends really on the architecture you have in mind and and it's it's really difficult question right so so it's not clear you I'll be fully honest it's not clear currently if it can improve on shes algorithm in practice because I don't know what practice is partly but also shes algorithm is just generally a meable to very nice very clever optimizations over the years some of them are applicable here but oth
ers might not so so there's also a question how much one can really optimize what I'll show you today uh and again chce algorithm is you know in that respect you know very good you know there you can really Save A Lot in many computation memory and so on so it remains to be seen how much of that really transfers the new algorithm and as will also say also this question of really seeing you know what is the what are the resource requirements from an algorithm this is a difficult problem and you c
an look at this work of gidney and EA that really T the force that they take into account many parameters like SpaceTime and noise and to really see how how much how many resources we need to implement shes algorithm you know in principle one might be able to do something like that here but it's it's not obvious um it it will take probably some time to understand all the optimizations one can do so yeah this is something I should say then that the one metric that's really important is actually m
emory usage and uh number of cubits you use in short algorithm it's pretty amazing actually I was surprised to learn this that you can you can Implement short algorithm with only like three end logical cubits maybe even below if you really if you really um squeeze for cubits but this is kind of amazing if you think about is that you almost don't need to store I mean to storing the number to factorize is n cubits and you can do you know almost almost with that three times that um so you know prig
GID is here can tell you more about this um there are some really remarkable optimizations you can do the way I'll present today the algorithm actually needs much more memory needs enter the three half cubits uh but um nice result of ragavan and vatan show that actually you can improve that and I don't know what the record is but last time checked it was 15 * n so it's it's also linear in N similar to sh algorithm the amount of memory is 15 * n um but uh it's you know it's it's still not quite
three times n so I don't know you know I don't know how much more this can be improved but at least the the the memory usage now currently seems reasonable any more question because there that's there's much more probably one can say and should say about implications in practice and we can discuss also some of that in the uh later in the panel but if there are any questions let me know otherwise I would go to the more technical part of the algorithm okay so okay you can you can still interrupt I
go back but okay so let's get down to business so this is sh's algorithm at this how how I think about it uh and you know sh's algorithms all about finding periodicity and and this is one way to visualize it actually I should say say that I'm doing it tiny bit differently so if you if you watch carefully you might see in the next slide I'm actually doing the algorithm a tiny bit differently because that's the way I want to extend it but you know it's not a big deal so basically short says okay
let's take a function exponentiation function so it Maps um Z to in this case a four for Simplicity you know I just some base of the exponents sh takes a random number um take for convenience take four to the Z and mod with the composite that we're trying to factor right 8051 okay so what you're seeing here is basically the if I'm using colors to denote the values of the function so kind of you seeing here like four to the^ zero which is one then four 16 uh know 64 to 56 and so on so basically y
ou're seeing all the evaluations of this function 4 to the power Z and goes on and and on at some point if you look carefully you might see there is uh period so at some point this thing uh you know we know this this must at some point there's the multiplicative order of four will show up so at some point we basically start repeating the same pattern and it kind of happens here you can see it happening here right you kind of see the same pattern here also showing up here okay so if you don't see
it let me show you some fancy animation so look carefully I'm going to move this thing all over here and taada you kind of see that things align so this is the period it's let's see again because it took forever to align this properly okay so this is the period of of four okay this is the the the multiplicative order so and from now on basically this is all standard right so the minute you find the period And I should say if you haven't seen this before you know the way you do that you compute
in superposition the function for to the Z right and you can do it with a quantum computer and then use some Quantum for transform to extract the period okay this is standard by now so the way the way once you have that period in this case it was 984 once you have the period you're just done it standard number Theory let me show you how to do that if you don't remember it's pretty standard so having figured this out so if the period is four is 9 84 you immediately know okay that so what does it
mean it means that 4 to the 984 = 4 to 0 equals 1 modu 851 okay this is what it means to have a period of this function but if you remember I chose four and I chose four to be a square um because I can then tell tell you that 2 to the^ 984 okay so I chose four to be a square of for no number so I know four is square of two so 2 ^ 984 is 116 63 mod 851 I just computed that but what's nice about this is I know that this has to be a square root of identity okay why because if I Square this what I g
et 4 to the 984 and 4 to 984 is one mod 18851 right this is this how we show how we found this is why we found 984 984 is by definition the per four so two to the 984 must be square root of one and moreover you can see can of got lucky it's not trib square root it's not one it's not minus one right it's 1163 right it's not one or minus one modle 851 which means that this is a non square root of one and once you have a non square root of one you're done this is again this is well known in in numb
er Theory and let me show you why because if you write down 1163 minus one um times 1163 + one right so now expand this is going back to C Pan's insight from that High School contest if you expand this you get 1163 squar minus one but I told you 1163 is square Ro of one so 1163 - 1 is z 1163 squ minus one is zero which means that 851 must divide this times that that's what it means to be zero modu 851 and it's all very basic number Theory so you know if you follow gr if not it's not very difficu
lt believe me and then we can just recover a factor of 1851 by Computing gcd okay and and the reason it's non trival is because because 1163 is not one or minus one so neither of this should be neither of this can be zero mod 851 neither of this is divisible by 851 so gcd must been nontrivial and we're done we got 83 using this gcp okay so I'll do it again in a few slides for the new uh for the variant for once we go to the new algorithm um one thing to emphasize here I should say you know I I u
se for just for convenience in this calculation but sure actually takes a random number that will come up in a minute okay so if you've seen sure you know you you take a random number okay uh so what's the running time uh what's the number of gates I should say okay what's the number of gates and the most expensive step is and this is well known is just a function evaluation Computing this exponentiation is the most uh painful most expensive thing here everything else is very easy the the quantu
m F transform it's super easy initialization is easy it's all very fast this is the only thing that really takes takes effort um this is a classical function right but we have to compute it in superposition how do you compute such a function how large Z needs to be this is important to understand Z the exponent needs to be high enough so we so we see period right we have to see the period and that means that if we're trying to factor as an end bit number if this 851 is think of it as a big end b
it number the exponent has to go to something like two to the N right just to be able to see the period so clearly we have to go to pretty high exponents like two to the end to be able to see periods and how do we do that well obviously we don't just do a * a * a * a like that two to the end times this will never end we use the trick of repeated squaring okay and using this repeated squaring trick which I'll show you in the next slide this requires n multiplications because we keep squaring the
number with itself so it's n uh multiplications of n bit numbers or if I again assume fast um fast integer multiplication we end up with something like n squ Gates okay so each multiplication is roughly n maybe n log n and there are n multiplication so I have n squ Gates and that's it that's is sh's algorithm um number of gates let me just show you what repe squaring U you know does you've seen this but it's it's good to see it again because I have to modify it a bit so if you want to compute ma
y maybe a to the 29 the way you do it first is square so you start with a you square you get a squ you multiply by a you get a cub you square you get a to the 6 you multiply by a a to the 7 you square A14 Square again a to 28 and multiply by a you get a29 so the sequence of operations is determined by the bit de composition by the binary de composition 29 that determines the order of operations here and the number of operations is basically the number of bits in 29 so it's it's n operations so a
ny multiplications okay so that's that's B for sh algorithm and now before moving on you might think okay here's an idea um let's try to make it faster you know let's try to make it faster by maybe not choosing a as a random integer like like sure does um not just a random element random and big number let's try to take a to be a small number like four like what I showed you before let's let's take a to be four that initially might sound like maybe it's useful but if you think about it for a sec
ond you see that doesn't really buy you much setting a to be a small number maybe makes the first operation here easy because you know squaring four is very easy I can you know just compute it with a piece of paper um and maybe the second squaring is also easy but very quickly here you just end up with like generic n bit numbers so if you think of it think about it for a second each time you square number of bits doubles so may be the first log end squarings you'll maybe be a bit faster but you
need to do end times squaring like you have to square end times so so very quickly after the first Logan steps it's basically a generic end bit number and it doesn't seem like you gain much okay so short takes a to be a random number you know we can try to take it to be small like four like what I showed you before but that doesn't really seem to help us much okay so let's see this is something we'll use in the next in the next slide but we have to introduce another idea so question before I mov
e on this in chat okay okay good so the main new idea is really this oh it's question so the menu idea is going to higher Dimension and I'm showing you here two dimensional picture it will be more than two Dimensions we'll talk about the right Dimension later but for this for this talk I'll just use two dimensions because otherwise very difficult to uh visualize so we have now a function that's a bit like the previous function it's kind of a multi exponent right previously we just had four to th
e Z and now I want to do four to the Z1 * 9 to the Z2 those four and nine numbers you know for now you can think of them as being just maybe some arbitary square numbers okay we'll talk about how to choose them later uh and I'm basically doing a very similar thing to what I did before and now we get this picture now it's two dimensional picture of evaluating this function this multi- exponentiation function mod 851 you see as before we have some kind of periodicity okay you kind of see the shape
here and this is this is what's nice about choosing small numbers it's very easy to see the periodicity because you have this region with the numbers that as small but this is just for convenience here so you see this region here and you kind of see it's repeating here and here and here and here so we have a periodicity in fact what we have here is like a two-dimensional periodicity you know it's it's what what you know it's called the latice so there a latice being formed here and again if you
don't believe me let me show you again some animation so let maybe let's focus on this period here and I'll show this animation like last time and see if it okay try again o oops no now it's being stubborn oh okay here we go not sure if you could see I'll try to do it again here so I'm okay so if you can see it the two things align quite nicely so this is really a period and the period is now two dimensional so what did I gain we try to see what what we G by the one of the hopes here maybe you
can appreciate it already from this picture is that the period at least kind of in terms of some kind of ukian distance is not so far like previously I had to go to like 900 or something I had to really go far if you look at this here it's not actually not not that far in terms of some kind of ukian distance right because I only have to go like 40 what it 47 here and whatever like 18 here so it seems like the perod in some sense got closer which is not too surprising because I have like two Dime
nsions to play with there many more options I can cover right but intuitively this could be useful because if I don't have to go too far it means I don't have to use very high exponents so intuitively it might be helpful because as you saw previously raising to high exponents is actually quite costly so maybe I can gain something you know by by by you know having this period much closer to the origin that's the idea it's kind of kind of works but we need still need to observe a few things you kn
ow it's not the full story yet okay okay so let's let's us summarize the idea and this is basically the same as what I showed you before it's basically just this kind of standard number Theory but let's see how it works again it's basically the same thing we found the period so it's 19 comma 47 okay so it was in the previous slide it was basically here 19 comma 47 everything repeats if you move by 19 on the x axis at 47 in the y- axis okay so what what does it tell me it tells me that 4 ^ 19 * 9
^ 47 because it's a period and it's the same as the origin 4 to the 0 * 9 to 0 which is just one mod 851 okay so what do I know just like last time I immediately get a square root of identity in this case again I chose 4 and9 to be square of the no number so I chose four to be square two 9 to be square 3 so I immediately know that 2 ^ 19 * 3 ^ 47 this number whatever it is 6 888 this number is a nonrival square root of one again why is nontrivial well just because it's not one you know it's not
minus one right you can see just because 6 888 it's a different number and it's therefore non trial square root of one why is a square root of one exactly by definition if you square it you get one right you get this this number here so we have a non square root of one and exactly as before once you have a non s Ro one you're done because you can just factorize so you know that 1851 divides 6888 minus 1 * 6888 + one and we can recover the factor by taking gcd say with the first one so we take 68
87 gcd with 8051 you get 97 and we're done you know we'll factorize 8051 so this is exactly basically as before um the only difference is now that we have this two- dimensional periodicity and really the kind of the million dollar question now is what did we gain what you know in terms of number of gates does it actually save you anything in terms of number of gates okay so let's try to go a bit look at it a bit more closely and I think to see this you have to understand how the how the calculat
ion actually works and and as before the only thing that really matters here is this classical computation which we have to apply in superposition so all the stuff happening later like qft is not really very expensive and you know I should have said maybe let me say now that just like in ches algorithm you know you also have apply some qft at the end and I'll get back to it later so this is the most expensive step in the in the quantum circuit and Computing this function evaluation okay so you h
ave DD the dimension in the example I had it was two but maybe we should choose higher Dimension later we'll see how to optimize D so I have Z1 up to ZD those are the exponents and I map them to this product you know I goes from one to D of AI to the Z modu my at51 or my nbit integer that's what we have to compute the question is you know how long does it take so you know we in dimension d right so as I told you before it seems like the exponents don't have to be so so high which is great right
if you just think about this for a minute you see that it seems like we only have to go up to Dimension up to sorry up to exponent 2 to the N /d okay so that that we only have to raise to power two to the n/ D and why if you think about this it's kind of easy to see by pigeon hall because if you let each of the zis go up to this number 2 to the n/ D the total number of combinations that you explore is 2 to the N / D to the power D so you actually end up exploring a volume in terms of number of p
ossible exponent combinations of 2 to the n and you know after exploring to to The End by pigon hole you will see a period you will see repetition okay this is basically proof that in exponent up to 2 to the N / D you will see periodicity so we know that there's a period with relatively small exponents not 2 to the N you know only 2 to the N over D that's that's sound the good news okay so everyone okay with this kind of pigeon hole like argument just because there you know so many possible inpu
ts there are you know B things to play with you'll just see a period because you're mapping to uh a range of of cardinality to to the end to little end okay so we'll see a period uh this sounds great but still how long does it take to compute this product so each exponentiation now only requires and of redem multiplications because I don't have to do repeated squaring you know n times only n/ D that sounds great well but I have to do it D times I have to do it for each of the eyes for one to D s
o in total it seems like I still need n multiplications so it seems like basically we gain nothing so again let me summarize it seemed first that maybe we gained a lot because the exponentiation doesn't have to go very high only up to 2 to the n/ D so when I do repeated squaring to compute this AI to the z i only have to do n overd multiplications but there are D of them so I'm still stuck at what we had before n multiplications like we had with SCH algorithm seems like we didn't gain anything b
ut we did gain something and for that you need another observation okay so here's the um here's the trick and this goes back to CH question the trick is that we actually need to choose the numbers A1 up to a a small numbers okay so short algorithm the numbers AIS were just chosen randomly the mod the composite the trick now is that contrary to short algorithm if here we choose those numbers those the base of the exponent if we choose it to be small we actually gain in terms of number of gates an
d you'll see in a minute why so for instance you know you can choose them to be maybe like squares of the first D primes you know you can choose them in multiple ways Maybe 4 9 25 49 you know we can talk about how exactly to choose them but first first let's see why it's so nice so once you choose those things as being small and we I say small I mean those are really small things because we're dealing with that n bit domain right we're dealing with numbers like you know in in the modules that's
n bit long and if I choose those and these is relatively small so you'll see in a minute how we choose D but D is maybe like we'll choose like Square Ro n okay let me spoil it we'll choose D to be like square root n so those the largest would be something like log and B those are very small numbers they'll be like log and bit so the trick the the observation is now we can actually compute the thing we need to compute right this this kind of multi exponent we can compute it using only n over D bi
g number multiplications so I'm emphasizing big number because we actually we need to multiply and numbers but most of them will be very very small and that's very easy very fast like multiply four time 9 I don't need you know end gates for that but the key will be to minimize the number of of number of big number multiplications okay so as you'll see in the next slide it turns out you can actually do that you can compute this multi exponent using only n/d big number multiplications each one if
we have as integer multiplication each one takes something like n Gates so we end up with n^2 over D so this is really where the Improvement come comes from the ideaa that we can use small a no small base of the exponent and compute this kind of multi exponent faster than the naive way and end up with this n s over D number of gates so at this point I'm sure you have questions you should have some questions you can interrupt me I can I will go back to it later some things probably don't make ful
l sense yet and can I ask a question okay so I assume you're ER you want to choose small numbers you don't know how many small numbers are there and so forth I mean you need some sort of assumption on the distribution uh I'm guessing that's where your assumption is coming in so my question yeah so my question is this so could you do things like and maybe you do it because I didn't read your papers I'm sorry I I it might be in the next slide could you do things like generating um integers in fact
ored form so that you can get the fact that you're uh these are random integers and they are INF facted form so they you me the A's the A's so not the N yeah so I I don't know I mean uh it doesn't mean it means again that they might be large factors uh but then you get rid of them I don't know let's I think I see where you're going let's maybe revisit this later yeah maybe you'll see where the issue comes up but it's it it could help yeah I think so maybe just to answer your previous question is
that really the minute you start insisting that those a should be small you end up into some number theoretic questions to whether things like that can actually you know see the period and so on so um we need to make sure that they actually generate in some sense the most of the multiplicative group and I can say more about this later but really this is this this this fact that I want them to be small numbers introduces some number theoretic you know complications or this mild assumption as I s
aid before I can say more about this assumption later but uh in chars algorithm it's not an issue because the base of the exponent is chosen randomly and then everything you can uh sure proved everything rigorously so that just a follow up to shafi's question so so maybe you don't need the AIS to be small but they could be smooth right I mean that's sort of what what Shafi saying but that might change the conjecture a little bit but it seems like that's still going to be a conjecture right uh th
at's why what you're saying right well yeah it could it could be could be helpful um right if they're smooth yeah yeah yeah I'm not sure I'm not sure it will help you but yeah I think I me trying to trying to get the ends to meet right what number theorist can prove and what algorithm need would be great yeah so it'sand if it's a Rand if it's an integer random integer in factored form you would expect that its largest factor even without assumptions I'm not looking for smooth numbers just random
numbers still uh the factorization pretty large square root or half you're saying yeah M def there's number of bits I don't think it buys that much I mean those are very small those are like Logan bits those are really the first primes so yeah maybe again maybe there's some Middle Ground yeah okay but me that's for for for the U sake of we kind of in the middle of the argument let me try to complete the argument and then we can uh revisit this okay so just to again um recap the idea is that we
want to this multi exponent uh function because the period is really interesting uh this period of the function and how do we do this so how do we actually do it with fewer multiplications it's really an exercise you know exercise kind of algorithm scores uh let me show you how how it's done uh it's similar idea have been before in the context of like multi exponentiation and but let me show you how it's done you know there nothing very mysterious here so how do we actually compute this so maybe
the first observation is that you know if we have small numbers like are you know four 9 25 the base of the exponent we can multiply those decimal numbers using only something like dgates so this is again just a basic observation that you know if you want to compute this you want to compute A1 A2 A3 up to to A8 you don't want to do it kind serially don't want to do A1 * A2 and then times A3 and then times A4 because if you're doing it this way the numbers kind of keep growing along with the com
putation you know like in in the in the halfway of the computation you'll have numbers that are D bits long already and each additional multiplication will take additional dgates so you end up with something like d squ because it's like you know like arithmetic like you know 1 plus 2 plus 3 plus four up to D so you end up with something like D squ Gates here but obviously this not the way to do it you know if you want to multiply numbers you want to do it in a kind of binary tree fashion right s
o so you do first A1 * A2 you know it's very fast Al a really small numbers like you know takes like log D gate you do A3 * A4 again log D gate and A5 * A6 and so on and then you kind of combine the results and it's you you get this kind of geometric series and and the the number of gates in total is only like the gates dominated um well it's actually the same I think in all layers so you get something like contribution of D in each layer and Only log the layers so it's kind standard calculation
and it's it's only like dgate okay so so again this is a basic observation and if you believe me that multiplying small integers is so fast okay it's only dgates U now you can basically complete the the argument again so this is maybe it's a bit confusing you have to really kind do the calculation but let me give you some intuition why this um this is Fast and the reason this is fast is because you were trying to do almost all the multiplications with small numbers right you're trying to minimi
ze to the extent possible calculations with big numbers because once you're dealing with big numbers that end bit numbers each operation is costly right each multiplication is or squaring is quite costly so the trick in this what I'll show you now is the trick is to really do almost everything everything you can you do it with a small number right remember those a are very small numbers four nine you know so and so on 25 so very very small numbers so let me show how it's done it's again some kin
d of repeated squaring nothing very deep and if I want to compute this for instance I want to compute A1 to the 13 A2 to the 9 A3 Cube A4 to the 6 I start with what basically one you all the exponents are just zero so I start with one and each time I kind of introduce or I inject you know the next sequence of bits based on the least um actually the most significant bits of of of what I I'm trying to achieve so I'll multiply by A1 A2 okay so this is the first step then I Square so what happens fi
rst I get like know exponents of one one 0 0 when I Square the exponents are 2 two 0 0 then I multiply by A1 A4 I get 3 2 0 1 these are the exponents a square so each time a square all the exponents magically double right that's the thing about squaring so 6402 I multiply by a384 I get 6413 I Square I get 12 8 2 six and I multiply finally by A1 A2 A3 I get 13 9 36 which is exactly what I wanted and again the important thing to realize here is this okay so so those those things I multiply by I ba
sically deduce them from the binary decomposition of the exponents okay this is where where those choices come from and Computing those things like A1 A2 A1 A4 or A1 A2 A3 is very fast it's only no this is really negligible here it's only V Gates each time and know the depth I have to do it is really just the size of the largest exponents so I only have to do it n over D and the height of this thing is only n over D so the total number of multiplications like big number multiplication like what'
s happening inside Square this multiply this is only n/d times that I have to do it leading to the total number of gates of n squ over D so that's a calculation again these things are actually very cheap Computing this A1 A2 A3 is I do it separately it's very easy you know not so many gates but dealing with those big numbers here is what's costly but you don't have the depth is not you know the number of squarings I have to do is only n/d so it's you know it's not so costly that's the idea so ag
ain you know it's it's it's really kind of an exercise it's a bit tricky you know you have you have to maybe write on the piece of paper if you can't immediately see that but trust me this this is what you get here okay so dead um quick question sorry if I um good good point Computing the partial products right I mean uh it's it's very cheap right I mean it's like n/ d * d rly right um but so so even if you did it the way the the sort of like the trivial way which you told us not to do would it
be problematic right I it's like n/ d * d^ s which is like n * D still seems yeah depends on what D is I mean yeah true for the choice of D eventually right I mean choice of D I eventually use square root and it's okay but we we'll talk about maybe using higher D later and and then maybe it will start it's wor yeah right yeah but good good point actually might be enough for this for this setting of parameters so at this point some of you might feel uncomfortable because in the previous uh slide
I told you that you this is the number of gates that we need and you might wonder you know based on this kind of asymptotics you should really take d as large as you can maybe like maybe n maybe D should be n and this this will give you n Gates so where is this end to the three halves where does that come from and this is because of something I did not tell you something very important so this is the very important missing detail there's something that you should have told me and should have int
errupted me me because when I told you that you know you compute this uh two- dimensional or D dimensional function you do qft one thing I should have said I did not say is how to actually extract a period after the qft this is actually an important step in shes algorithm um which is not trivial I mean if you think of what's happening in shes algorithm if you remember that you know you do the qft you then measure but it doesn't immediately give you the period you have to do some additional post
processing um if you remember continued fractions and turns out that in the dimensions you have to do some kind of D Dimension analog of that and what turns out to be the thing you need to do is is run ltis reduction so D Dimensions you need to apply some kind of Lattis reduction to extract the period from the measurements that you do and in some sense contined fractions like like in shorts algorithm is basically kind the one-dimensional you ltis reduction so it's it's actually the analogy is is
very uh striking here it's really you can really see um the the Contin fractions in what I'm going to show you next but in the language of you know latis reduction so more precisely if I want to extract the the period in the dimensions turns out that you actually need to solve a d dimensional latis problem but moreover this is also why we need to apply the quantum circuit D times so this kind of goes back to the main theorem unlike sh algorithm where you only have to apply it a few times even t
here you know at this inti at least naively it's not just once for similar reasons you need to apply it multiple times here because you want to get like a basis of the dimensional of a d dimensional ltis so you have to apply this Quantum circuit D times and you know if if you go through the the math what really ends up happening is that those this measurement of the quantum F transform it really gives you a vector in the Dual latis and then you need to use latis reduction to recover basis of the
original latis which you care about so there there's some non-trivial ltis stuff happening here but um it's you know something we have to do let me just mention it's it's not like something you haven't seen before in the sense that um or something like that if you go like to Simon's algorithm right one of the first Quantum algorithms we teach if you look at Simon's algorithm there's something similar happening there right you're trying to find this hidden like periodicity in in in in the hyper
Cube 01 to the N or 01 to the D and to recover that you have to apply like the Hadar transform and measure but you have to do it D times because you have to span the whole orthogonal Subspace and then recover the secret Vector so if you if you've seen re Simon algorithm or you taught it you might remember something um similar in the sense that you need multiple measurements to be able to recover um you know the secret you care about uh I I I don't know if it's really necessary but it feels like
it's kind of needed I maybe there's a better way to do it that doesn't require applying it the times but yeah so short long story short this can be done using the L algorithm but this introduces an important change in the calculation I showed you before lll is an approximation algorithm it doesn't solve lest problems exactly and the higher the dimension the more difficult is for L to approximate so the approximation Factor scales like something like 2 to the D okay so it scales exponentially wit
h the dimension so as a result we actually need to use exponents that are beyond what I was telling you before so before I told you look you just have to go up to 2 to the N over D and that's enough because you see the period but actually because you have this additional approximation Factor you actually have to go a bit beyond you actually have to use exponents that are 2 to the N / D plus d so you have to go a bit beyond and again something like that shows up in Shore if you remember sure also
has to take multiple periods um to be able to get a good enough approximation so you can use continued fractions so it's something very similar Happening Here uh and this is where this 2 to the D comes from and now you can finally see the tradeoff because if you look at this n/ D plus d okay and of is because we have to see the period and D is because of the approximation Factor but if you look at this tradeoff you see okay I should really choose D at least atically I should choose d as Square
Ro n and this leads to what I promised the end to the three Hales number of gates and also leads to us having to run the circuit square root n times because D is square root n okay so so this kind of this is the the most important detail here that I was owe you so this is um this is at this point I think summarize um the algorithm is basically this so you choose some kind of Base exponent base A1 up to a d and you can just really choose them to be four 9 25 49 like know squares of small primes t
hose are all very small numbers you apply the following Quantum circuit the times so you compute this multi exponent in superposition right over all those exponents ranging from zero to 2 to the n/ D plus d again I have to take this extra D for lll to account for the approximation Factor on the result I have this like big state I I apply qft I apply the quantum for transform I measure uh each time I get an approximation to a dual ltis Vector I have to apply D times to get a basis and then we can
use l to recover really a period or actually all the periodicity I recover a basis of the Primal lce that I really care about this is the picture I showed you with this period in two Dimension that's what you recover the periodicity there and use this period to factorize and like like we saw before this is standard number Theory that's it so open questions there are many open questions so reduce the number of cubits or the space requirements further um uh the current is around 15n um this is th
e work of um um ravan and vut and number of gates um trying to actually get an estimate like an honest estimate of number of gates really physical cubits I don't know this is this could be quite interesting but probably not easy to do this calculation uh in detail how exactly you know how exactly this compares to sh's algorithm for something like say you know 20 48 um trade of the classical lce algorithms um that's something I think quite potentially quite interesting because you can spend more
time on on on doing the classical post processing you know if you want to factorize a number like 2048 many people uh many governments would be happy to spend more time doing classical post processing so potentially you can play with this trade-off do more calculations better lce algorithms not just L but more sophisticated lce algorithms like bkz or even fancier things that that exist today uh and you know as a result maybe uh offload some of the quantum computation to the classic post processi
ng this could be quite interesting to see how this plays off um maybe another more technical thing I could say um this is okay it's really kind of technical point the way I describe the algorithm now it uses a uniform superposition over the exponents um and you know it's it's probably probably works but analyzing uniform superposition like that is a bit annoying um actually even sh algorithm has this Cal potion there and it's gets even more annoying in the dimensions it's probably doable uh but
at least currently in the in the paper the proof actually uses a gaussian superposition it's much nicer to analyze it this way but you know I'm pretty sure it should also work with uniform superposition but I don't know for sure at least in practice I think it would be much easier to implement it with the uniform superposition um so that's something maybe to look into like in terms of uh analyzing what happens when you just you know take exponents in some box not in a gan but in some box there's
some nice questions about circuits failing uh you know how to do it more robustly and there's some work recently maybe we'll discuss some of that during the panel um because we're actually applying a circuit here Square 10 times and what happens if a few of those things fail you know how robust this is and there's some recent work of that um that maybe we mention later in the panel uh and something that we already brought up before the number Theory IC assumption you know I think it would be ve
ry nice to prove it or show that it follows from gr or anything like that but you know you know I still don't know how exactly to do that and this would be very fantastic if something else can be said about that okay I'll stop there thank you oh great thanks uh thanks for that that was great um let see any questions um going over the not the chats there were already some very good comments there I see H you are unmuted feel free to ask your question you raise your hand uh yeah sorry I think that
was by mistake where is that an did you want to no that was my mistake I think he said okay um okay so um so very quickly um I think you mentioned this but um but um continued fractions or I guess it's like gcd or or lce reduction into two two Dimensions or something or is it so so here here also um what you're doing is um using it to to recover exactly right the you're you're going uh F out and recovering exactly a basis for the for the period again yeah actually you get right you get maybe I
go back to this two dimensional picture you really get a basis for is that for the whole uh lce you get um and even though I actually only need one period yeah I actually get a basis in this case you'll get maybe two vectors like this is one vector and this is the other Vector you get really a basis generating this whole lce of periodicity um and yeah maybe I can say say one more thing about this um you might have noticed I chose in in my uh example before I chose this one here this period here
and Noti this one here even though this one looks closer uh and the reason being is that this one here if you actually just calculate whatever that gives you this actually gives you a trivial uh square root this would give you like I think either one or minus one um so uh you know some of those periods might be you know will be actually uh trivial square roots so I think um what we need basically the number theoretic assumption is really kind of trying to is telling us that we will uh we will be
able to find um some nontrial square roots if you know if we look if we look at this lates there will be some you know not too far away uh nont square root that's one way to understand the number theoretic conjecture and then and then you know if there if there's one uh not too far a non-trivial square root then there are many that's not the hard part is it um actually I only need one it say there yeah there's something interesting Happening Here in the sense that yeah in you only need one and
um the minute there's one because you find the basis of all those things you you will find it so it's you know the minute I have one and three Square I'm done I have a factorization of of my then then there would be one in the basis is what you're saying yeah exactly exactly so there there's exactly there there's argument that says I think I think exactly what you have in mind that if there's one one uh short Vector of nearby non-trivial Vector in this lat it will have to be also in my basis bec
ause the basis generates all of them so yeah so there's just there's an argument in the proof that says something like that exactly yeah Andrew yeah yeah thanks thank you for the very nice two Andrew oh which Andrew had his hand raised first so if you want to first the other Andrew that's fine um okay sure um so I I guess one one thing that I was curious about is could these ideas also be used to give faster classical algorithms for factoring like I it seemed a bit reminiscent to me of polar row
where you're also trying to find sort of the period of something like X2 + one what honestly I I doubt it I mean because so many people tried and and I think those ideas are feel to me like they quite specific to the quantum setting I really I would love that um but uh yeah I think it's yeah I would I would think it's exactly the other way around so all these algorithms come from the row method and the and and the pomerans and I think it's actually right absolutely right I would say can we actu
ally use like say number Fields see they Amazing Ideas there you know this and and actually if you look at the number of fields see if there are some like laes showing up and maybe some of that could be but I was unable to use to do any of it but um yeah okay thanks I guess the Andre Andrew we I'll be the other Andrew here yeah I really appreciate the pedagogical uh quality of talk especially using P's example of 851 from his high school math contest uh that he you know was inspired by you know
in your uh talk I thought that was a very nice touch um my my question was you know you you've shown that by looking thinking about things in this lace way uh you can succeed more efficiently but it seems like it might also be useful in failing more efficiently as well you know you might um sometimes when you get a trivial uh route you can use that with pre-processing postprocessing things like this to think more cleverly about how you choose your next number and I was thinking with this multi-d
imensional search maybe you can get more information about how to choose your next uh trial more wisely uh if you happen to you know accidentally choose a uh a trivial route I was wondering if you thought about this at all I see no I haven't thought about this I'm trying to see so basically what might happen um is that you know you run the whole thing you know you you you you get a basis of the Dual you you get all those dual vectors you buy ltis reduction and you end up with a bunch of basicall
y trivial square roots um yeah I wonder I mean I'm not sure how to learn really anything I don't know how to learn anything from that I mean probably I would just try to change my uh my my exponent the base of the exponents not to be those particular prime numbers maybe take different uh Prime square numbers um yeah I don't know if you could actually learn something from that that's it's a good point yeah um yeah I'm just s you know putting my Bas and hat on I feel like there should be some info
rmation there I don't know if it's completely useless or completely information free I yeah I don't know it's yeah it's a good point I don't yeah I mean I have to think about what exp points would be but it could be that it doesn't give you anything but yeah mean I I would have to think about it's a good one maybe you can salvage something despite not yeah thanks centry I guess there's one more question Dan maybe can you can you talk uh yes uh I can post it I I already printed uh in the Q&A but
I can read it again uh can you hear me please yeah yeah something is popping up on the screen so I thought maybe you're don't hear me okay EA and Gartner extended o algorithm for district log problem but for the multiplicative group of uh zp but not in general as it was the case for the sh algorithm why because Nam there is no extension of this notion of small group elements that audit is using to the elliptic curve groups uh so any comments any ideas how how actually this can be extended to the
small group elements of the elliptic curve groups maybe otherwise the elliptical curve people would say okay we are maybe still safe um from this extension or Improvement yeah excellent point so I I think your summary is currently probably uh correct in the sense that I don't think uh it's known how to use this for lipti cures um I mean uh of course you have sh algorithm but to to use if you want to use something like like this algorithm you would need a notion of a small element and actually I
think they discuss it here if you go to this uh PR print on the archive from AA and gner they uh they do mention and and is an issue right because it's you know as long as uh but could it could be that there's a notion of small element that I'm not familiar with that um you know would make something like that work but um currently I don't know if something like that existed you know something that would allow you to do faster operations um yeah it's so it's a it's a great Point currently this d
oes not apply ASD is to elliptic cves because we don't have this kind of small numbers that are very easy to multiply right yeah thank you thank you thank you great Point great uh okay so I guess let's let's move on to the panel now so but that if you stop sharing we can set set this up uh um so while the uh you know while the panel is being set up uh let me just introduce the panelists so first of all it's a it's a great panel so first of all we have Peter sha here um which is very very appropr
iate uh he's obviously a giant in the field uh not only responsible for algorithms for factoring and discrete log but also also um uh uh Quantum ER correction and fault tolerance so Peter welcome um then we have venod vatan who is from MIT he's also uh he's one of my favorite cryptographers um so we know it works on luses lwe homomorphic encryption but also he's increasingly working at the at the intersection of crypto and Quantum so welcome with and um our last panelist is Greg gney from from G
oogle um he's he's a team lead for the development of cir and he's also I think one of the world's leaders on resource estimates for Quantum practical Quantum computations so CG um so uh I I thought we'd first get get the views of the panelists about the talk you know any reactions Etc so start with you Peter okay so I w't I don't really have that much to say first thing is that I was really amazed when this um when I saw other's result because you know my view was that lce reduction was really
a very expensive operation and it didn't get very close to Optimal so how could you possibly use it to do better but I mean the idea is that you trade off and you don't you you only need to red the reduce the um the I guess I don't think it's Dimension by square root of n using lce reduction and that gives you enough time to account for the inici Aus reduction but still gives you a speed up over you know the plain factoring algorithm so that was a really nice thing and the second thing is um I w
ant to say what does this mean for discoveries of other new Quantum algorithms I mean that an improvement to this I guess nearly 30-year-old algorithm didn't come around until this year is um really pretty amazing I think it shows the difficulty of finding one algorithms so the fact that um nobody has found any other nice Quantum algs for useful problems may be due just to the difficulty of finding Quantum algorithms or it may be because there aren't Quantum algorithms for other nice problems an
d I don't know which one the answer is I really would like to know we not we um yeah the second time I'm hearing the talk it's just as as if it's the first time it's an amazing talk um uh so so I guess one comment I wanted to make was uh about the noise uh about the noise tolerance in a sense of uh of a Dead's algorithm um so uh it turns out several of us observed including odad Martin aera his student uh my student and I observed that if you uh even if a fraction or constant fraction of the of
a Dead's algorithm is corrupt in a in a certain sense let's say it produces sort of random junk uh certain noce model uh you can still uh Factor you can still sort of error detect and correct and factor and so forth um so it's sort of a the following kind of consequence that I found striking which is you know if you don't do any error correction at all uh to let's say Peter's algorithm it can tolerate error rate of one in N squ just trivially because it's n squ size circuit um and and and for aa
d it turns out that you can actually tolerate an error of error rate of one and enter the three halves again because you know you you you in total you run you you you you run n Square Gates uh but a fraction of the runs can be corrupted and I can tolerate it um so it's a qualitatively quantitatively sort of better error correction property is something that comes out of his algorithm I wonder how much more you can do um you know um maybe this sounds Preposterous but uh what if uh you know um a f
raction of U gates in either Peter circuit or ret circuit is corrupted what is the worst that can happen I mean you know um um does a factor still fall out uh magically U or maybe we can do slight bits of error correction without going to General fa tolerant computation and still recover um a useful facturing algorithm um I that that's that's that's open but I found this noise tolerance angle U interesting sorry sorry not I didn't quite catch that so are you saying that each time you you run it
you're you're recovering something you know a a dual vector and if a constant fraction of those are not correct you still you can that's right that's right exactly and can you say a word more about why why that's okay um because somehow um you know um that's Al for post-processing it sort of finds sort of linear combinations of uh of uh of dual lce vectors that um um sort of that that that do something right um if you have one like random Vector very noisy uh uh Vector um the the chance that it
it it participates in such a nice linear combination is pretty small so you can use that to design a filtering algorithm that sort of you know uh filters out all the noise noisy uh vectors this is assuming that the noise has a certain form you know that it is sort of a uniformly distributed so either you get a vector that's close to the Dual lce or you get a uniformly random Vector in the parel pipid um so that's the Assumption you can relax this assumption a little bit um but yeah I see and S s
orry before can can you also comment a little bit about the space efficiency and how that uh works right so so so let me sort of comment about it in connection to I think Ronald who asked about the depth of the circuit right uh um these these two seem connected to me right so in particular uh the way you get depth efficiency for Peter's circuit is to say you know um the the base is fixed right I pick a base a that is fixed it's classical so I can post Pro I can pre-process all powers of to a a s
qu a to the four Etc that takes a lot of depth it's sequential but it's classical so I can do it on the side and then all I need to do is uh is multiply I can do it in a multiplication tree so so that that um contributes to the depth efficiency uh right and then you have to make the qft low depth and that was cand butus uh yeah they did that right um uh and copper Smith with approximate qft so that that's a separate story um it also contributes to space efficiency because you don't need to do sq
uaring in coherently uh to run Peter's algorithm and if you were to if you were forced into that situation you'd be in trouble because squaring is not a you know not a reversible operation so I have to write it sort of in in separate registers um right so the fact that um you can pick the base once and for all and classically and you can post pre-process seems to contribute to both the space efficiency and the depth efficiency of Peter um both those go down the drain you know uh with um with ode
t algorithm Asis as it stands uh it turns out that you can recover the space efficiency um in the sense that um uh you can get an algorithm you can get a circuit with n to the three halfes gates and N logn cubits uh um um of uh yeah of extra space of Nels um or you can get n to the five halves uh and uh s of that's at 15 n cubits uh it's now 10.32 n cubits and uh and if my student uh what he said is correct uh couple of days ago it's 9 N cubits um and so so the idea there is instead of doing squ
aring which is not reversible so I have to write the values in a separate register you you do exponentiation slightly differently uh using the Fibonacci representation of uh numbers the so-called Z and off representation of numbers um so so you have a um um right so so so a squ you write it in a separate register but I don't want to square that further to a to the four because I have to write it in a separate register I do a squ time a so I get that's multiplication so that's 8 a to the 3 I can
do a to the 3 * a s which is a to the 5 this is all multiplication I don't do squaring and if you look at the numbers they are Fibonacci so all I need to do is to write my exponent as a sum of Fibonacci numbers and voila that's that um uh this is this is an old trick um discovered in the reversible computational literature but we sort of like repurposed it uh um here yeah that's very nice thanks not so Craig would you sure um I mean I agree with vard that the extra fault tolerance is very import
ant like this property where not all the shot to succeed is actually needed for what odad was hoping for in his talk where he says you know it's easier to run a smaller circuit if you have to run many small circuits but they all have to work like for example if you're taking statistics for chemistry and you don't know which shots are good and which are bad then you need all of them to be as reliable as if you've done them all at once otherwise you it just doesn't work um so like that that additi
on to the work from VOD and his student I think is like very important for this algorithm working like that is what would allow you to reduce the C- distance of the logical Cupids without that you can't um uh I don't know if I have anything else specific to say without being prompted I mean I'm happy to take questions and such do you do you do you have any any thoughts on whether you know whether this would provide um some improvement what sorts of architectures or you know what yeah yeah so so
there in general in Quantum computation there are an enormous number of ways to trade space for time um but often they are sort of a like onetoone trade-off and they have a sort of character where they I don't the thing that's interesting about this algorithm it's a very different kind of SpaceTime trade-off it's a very highle SpaceTime tradeoff instead of a low-level one which is maybe what I'm more familiar with um where you use for example gate teleportation to do things in parallel so that y
ou need more space but use less time um so I kind of hope that this different SpaceTime trade-off then you you can then use other SpaceTime trade-offs to sort of move to where you want to go so uh in particular I often think in terms of uh what's called area time or Hardware time or SpaceTime volume which is the amount of space you need times the amount of time you need it for so you can think of this as a proxy for the energy consumption of the computation and it turns out that a pretty good pr
oxy for making a computation better is just to reduce the hardware time and then worry about packing it into space um so this algorithm actually technically doesn't really reduce the hardware time if you only look at it in the abstract circuit model because it does it saves per shot but then adds that same number of shots back but because of this fault tolerance property it could be you know 30 times noisier and rule of thumb if you're using surface codes for example is uh a d byd patch if you i
ncrease d by one you get about 3 DB more suppression of noise so about a factor of three less noise so 30 times more noise tolerance means you can reduce d by one three times so if you were using distance 26 then you in had use distance 23 and so your the amount of space that you would need assuming everything else is equal would improve by a factor of 23 26 squared and this would also improve the time a little bit because your distance is also timeline any anything else um there's a Craig there
's a question I believe for you from on the in the on the Q Q&A uh maybe also for odad uh um OD V can I comment on whether odad improvements can be done in an iterative manner at least on the control cubits uh so I don't know the answer to that question um actually I have a question on the quantum Stock Exchange which has part of this question in it that if anyone wants to answer they can go to do it in particular um when we do phase estimation and sh's algorithm is doing phase estimation um we'
re typically doing it with you know phase oracles or phase operations that are powers of two of the thing we want to estimate whereas in this modification that vade has we're using Fibonacci powers so instead of getting the phase and twice the phase and four times the phase and eight times the phase we're getting the phase and two times the phase and three times and five times Fibonacci multiples or sorry uh I should have said Powers um this breaks the normal Cubit recycling circuit but it doesn
't it doesn't seem like you shouldn't be able to do it anymore like it seems like it should still work and someone just has to you know figure out the details um I don't know how to do it personally but I feel like if the right person looks at it they'll just know the trick and like someone who's familiar with doing adaptive qfts or something will just know some basic theorum that makes it work um so well I should also say there are multiple obstacles here so the algorithm sort of runs in three
phases first you generate the exponents with these gaussian distributions then you perform these like it multiplications in order to get the product and then you do the qft in order to estimate the f the problem I was just describing refers to the last part so can we do that part iteratively there's also the first part can we do that part iteratively and odad and his talk mentioned can we use uniform superpositions instead of gausian superpositions that would be a very useful property because a
uniform superposition can be generated one cubit at a time with plus States instead of needing them to depend on each other and then in the middle um I don't know the exact details of your implementation but if you're using two accumulators and multiplying back and forth and multiplying into one of uh one or the other as you go um then you end up with too much information at the end where how the bits are spread between the two accumulators could in principle allow you to decohere in a way you'r
e not supposed to so you have to measure their product and then uncomp compute them but this means you have to do two passes over the exponent cubits one to compute one to uncomp compute so you need some sort of oblivious obliviousness property where you don't know which one you're multiplying into or it doesn't matter which one you're multiplying into um so uh for example the coet representation of integers that Zula introduced which makes this big superposition um with a bunch of offsets by n
in order to to do arithmetic modu n that's introducing an obliv an obliviousness property such that additions don't reveal how many factors of n they've moved over and we would need I think you would need something like that in the middle so there's three separate problems there's this initial State problem this obliviousness problem in the middle and this iterative uh CU recycling problem at the end and if all three of those were solved then you could probably stream it instead of having to kee
p the exponent registers around the whole time oh great thanks Craig um what do you have any any thoughts now on the comments um nothing very specific uh I would say yeah I think it would be interesting to see how much this can be pushed further and and um one thing maybe to to consider that you know I've been discussing with others uh um you know imagine you just want to show know that that you can know get some non sh information uh from this could could this be you know kind of some not for a
ctually factoring big integers but you just want to show that um you know for know medium siiz numbers you I know like 200 uh 200 bits uh you want to show that the algorithm is doing something you want to show that you get some signal after the qft so if if it makes sense you know you don't you know like doing some near-term quantum computer demonstration ation would this actually give you any advantage over say sh algorithm because if you think of the extreme you know maybe you don't even have
to do any exponentiations here you just have to multiply a bunch of small numbers modular exponentiation and it's not maybe enough to really factorize because like you know if you think of what you get in the measurement of the qft is very noisy but maybe this is like in a very minimum that you can still see some signal after you measure the uh the qft so I'm trying to think if this actually can lower the the boundary of where we can see some interesting Quantum phenomena that points at somethin
g actually factoring so if it makes some I can try to make it more precise but I haven't really thought about this um did you mean try to make it more precise now please do yeah maybe I should not volunteer that because I should really think about this more um I mean yeah I mean you one can try to write down similar analysis but really take things to the extreme where you know don't exponentiate or take very very small exponents and you know try to see if there's anything you can recover from th
e qft um I mean the thing here is that you C you need to see the period you know just likeing shortes algorithm you need to you need to make sure that the period but here in some sense the period actually shows up very early right you don't have to you don't have to exponentiate much to see the period it's only about multiplying the small numbers and if you have like you know n of them very small numbers Lo and bit numbers just start multiplying them you start seeing some period but it won't be
as nicely structured as you know as we need to apply L and get good good good accuracy measurements of of the Dual vector and so on but maybe it's enough to tell us okay something is going on you we see something here that the quantum computer is actually doing so yeah so that's just just an idea there's a question from Ike hi it happens my questions right along the line you were just describing OD which is um in in your work uh one of the great things you have done is to show the power of purif
ications for understanding a lot of properties of luses and proofs and it occurs to me that uh in your algorithm and construction there's one big part you could purify to try to maybe understand the factoring problem better which is the post-processing what would happen if you had a coherent postprocessing algorithm a coherent llll a Quantum llll and and imagine you have a really big quantum computer with lots of them all running different versions of your latus and then coherent ly postprocesse
d do you think that might give us some understanding of the factoring problem see So currently the the post processing is separate which allows you to break the quantum computation into separate circuits and then bring them together if everything is done coherently at least in terms of in terms of number of gates you actually don't gain much absolutely not you're right I'm not interested in anything practical I would be interested in understanding the nature of the problem because because I woul
d want to understand what llll or any kind of lce reduction is accomplishing in a coherent manner what is it throwing away what is it keeping how is it compressing some entropy in some places I don't think we actually understand that and then therefore we can't actually move far intellectually maybe on that last line of thought you were giving where are these small periods going how are we throwing away some of that information uh totally impractical but just a great deal of fun to think about y
eah you know as as you know I really like I really love this connection between laes and Quantum so it's if L can be used somehow this would be fantastic but so so I I the just to understand your question right uh you you know if if you run n algorithm once right I mean you get a super position over the Dual l or close to the Dual lce right so it sort of the state has and you're really kind of sampling many times uh from the from the state right so you're saying run it once somehow and then some
thing right uh sort of like an lll like uh um run an L like algorithm coherently yes on that's right uh it it might need multiple instances of this run because there is some classical sampling you're doing also but I'm not sure and and it would be wonderful to find out if there is a Quantum version of the post-processing that could run just once yeah right okay uh that that's even more speculative than what I'm asking for but basically I'm wondering have any of you thought about what it would me
an to have a coherent lattice reduction algorithm conceptually I haven't Haven I mean I was thinking about this Peter when I was reading your recent paper uh with uh Roger Lynn I think from Harvard uh because you you have a a new latus reduction algorithm for specific kinds of luses constructed from codes and it's based on UK's algorithm and we can make a Quantum version of that ukl algorithm it's much simpler in nature than llll perhaps yeah well thinking about doing I guess the lce reduction o
r the continued fractions coherently really scrambles my brain right now so I can't give you an answer maybe an anecdote on the notion of running ukids algorithm coherently which is there's this result where the gcd algorithm is one of the few things we don't know how to parallelize at all um and you know you think about it if I can do period finding then I could like do period finding on the gcd and you like work through all the steps you work through all the steps and you get to the end and yo
u measure it and you're like oh wait now I have to do the gcd in order to get the to do the least denominator estimate and all falls apart but but wait potentially of gcd of randomish numbers right uh um uh yes that's true it might be a different gcd in that sense um uh because of that anecdote uh I've long thought of the this continued fractions as a SE secret extraction algorithm so I I've thought about it as almost an adversarial scenario and maybe that's what the quantum can do here find thi
s certain kind of secret that's encoded the two integers a secret being the gcd the secret being which integers are closest to the given uh uh floating Point num so so right is there something specific about the gcd that makes you think about it that way as opposed to like thinking of a sorting algorithm is finding the secret sorted order of the inputs or something mostly the connection of the generalization to latus reduction because there we explicitly think about Secrets okay and I don't know
why there shouldn't be a physical process which allows us to accomplish this there there should be a hamiltonian for llll maybe we can we can think about this offline Ike yes yes thank you right thanks thanks Ike so um maybe um I I'll just see if there if there any final thoughts from the panel on the question or in general in general yeah just test some um on Vin's comment about maybe we can have errors within the algorithm itself I would be very surprised if you could survive P type errors li
ke you have a phase Flip or a bit flip halfway through the algorithm if you just you know try examples of that and see what they do to the qft output it tends to be very bad um on the other hand we actually intentionally approximate the algorithm a lot already so for example in the qft there are all of these extremely tiny phase angles and I think people's initial inclination upon seeing them is that they must be very important if we're writing them out but you know very quickly because each of
those angles is twice as small they get to the point where by linearity they don't matter anymore and so we don't do any of those and that's probably a good example of where the errors don't matter right right right um um so so I guess the qft seems a tolerant in that sense right we but we have already squeezed enough I mean the other thing is this this point made by Zula that you know that we've used where because we're in this enormous superposition of many many many different integers if you
have an arithmetic circuit and the arithmetic circuit has some small proportion of inputs that it gives the wrong answer to as long you can show that proportion is small as opposed to a bit flip where the proportion is 50% or wrong or 100% or wrong y um then basically it'll still work so if you only mess up one out of every trillion trillion cases unless those somehow correlate with the ones that are actually dominant in the super position then it's just fine so like for example if you increment
the register there's 2,000 bits to C propagate the carryover but after 50 bits it's almost definitely not still propagating and so you can just stop and it turns out that this sort of thing is okay as long as you're not going to do it you know to the 50 times so people should be looking for approximate arithmetic yep exact arithmetic and see if that reduces the number of operations dramatically yeah in fact we we do that um and the question is like can we do it better and or are there other pla
ces where we can approximate or where something is preventing us from approximating and we could fix that and then approximate more um actually you don't even really need to know the quantum part in order to kind of do this problem you can think of it as um I need to compute this value on a secure chip and I have the ability to remove values from the secure chip by my measuring them and as long as an adversary that learns all those measurements can't figure out what I was computing then it's pro
bably safe to do it quantumly as well coherently so if you can bound the adversaries of probability of learning the value below you know one and two to 50 then the algorithm will probably work fine coherently greaty had a question so my question is about the elliptic uh discret log if El the curve discret log if there was anything any work that has been done on it or in the context of quantum I guess and and and in your improvement you did yes so beyond what I mentioned uh I don't think much so
yeah so so basically there there's been an extension to discret log uh but not for elliptic cves because you're really missing this notion of a small element something that's very easy to apply group operations to um but if such an otion exists I know that there's no reason why you know something like that should not work but I I don't know if the notion really exists so if you know if doing discr log in modu in multiplicative modu Prime you this this is this is easy uh I mean I mean this was sh
own to be possible um but for elliptic cves I just don't know yet great um anything else um any any other thoughts otherwise um maybe I'll the question that Ronald asked in the very beginning right about the depth of uh you know dead circuit can you can you sort of compress it I mean it's it's a problem that's begging for a you know for someone to put it out of it mystery you know should be possible but we don't know how to U yeah I just want to make comment so uh the reason I was asking about c
urves is related to the question I asked in the beginning of your talk about whether you can uh do your analysis for random numbers rather than worst case and get better results maybe without an assumption and maybe for elliptic curves it's all intuition I mean that would be more likely um that you could do a an analysis like you could talk about the order of the curve like the number of solutions and that soort of it's distribute nicely and then maybe you can argue through that that the algorit
hm an algorithm could work for some on the average not in the worst case I don't know I thought we have more freedom with the order being a random number you know this in terms of it its factorization [Music] um maybe um on the other on the other question that the remark of Ronald and that V not just talked about um you can actually make the circuit constant depth if you have a fan outgate so you can even make it even less uh use less time than the log depth um but there seems to be somehow a ti
me space trade-off here under the hoood that I'm not sure we understand exactly how it goes and OD that is somehow odit result seems to be in somehow another region of this time space tradeoff and and in order to make it constant depth you have to do actually some classical computation in the middle of your of your circuit which you sort of don't don't count were and well there's some a parallel because OD that is doing some some some classical calculation at the end of the of the computation so
so it's sort of the interplay between classical computation and class and Quantum computation and somehow minimizing the Quantum Resources right that's the game that we want to play yeah so so Harry can you can you remind us about the best time space trade-off known for this uh well I know that the best I mean so I've been looking recently at making these circuits constant depth sort of sort of having sort of in my mind minimizing that because that minimizes the amount of time that your circuit
runs and that should be beneficial for the buildup of errors but yeah unfortunately you need more cubits for that um and I think um I think I don't know actually what the number of cubits are but they're getting Beyond quadratic um I'm afraid at at the cost of but at the at the gain of making your your circuit constant depth so properties of Shores algorithm is that it has so much flexibility in the depth because it's just doing a modular exponentiation right like you just do all the multiplica
tions in parallel and within the multiplications you do all the additions in parallel and it gets down to polylog depth where we use currently you know quadratic or cubic depth and like essentially the more cubits you can throw at this problem the faster it will go and essentially it's almost a onetoone like linear relationship where if you throw twice as many cubits you get about twice as much speed for a very very long time until your like computer covers a city or something depending on the i
nitial size scale although I guess you probably start running into decoding issues where the classical computer has to communicate quick enough to to share the information that's being teleported all over the place and whatnot exactly yes that's sort of the the limiting point I think the limiting point is actually building the city-sized computer but yeah the service code does have these great properties and ating codes in general where you can very quickly get um entangle copies of information
in very many places if you physically had the ability to do oper between them by establishing entanglement and doing swapping right but unrealistically large so Harry just to understand what you said a little better so uh the the sort of the Improvement to constant depth you were talking about refers to uh Peter Short Circuit right I mean uh that you're saying you can absolutely yes yes it is that yeah it's not not at all out that work no it's old I mean it's it's not not my results but it comes
from the fact when you look at F Hoyer and spalik looked at this early on when you have fan outgate you can really reduce the depth from logarithmic even to constant um and then then there's a realization that this fan out Gates you can get it actually by having sort of intermediate measurements and doing teleportation tricks and so on thanks um on the topic constant depth um there's a lot we don't know about Quantum circuit construction and I think a really good example is classically there's
a thing called the carry save Adder which does uh uses a special representation of a number where you can perform addition in linear space and constant depth uh basically you just don't propagate the carries and you treat them as a second integer and instead of doing addition that takes two and integers and produces one you take three and produce two yeah um we don't we don't know if quantumly there is an equivalent thing where you have some special representation that has constant depth in line
ar space to do addition um we know an N Times log of log of n Spa uh version We the issue is with using the carry save Adder just directly is if you keep adding zero into it the carries propagate away which means it's not reversible so you have to fix this amount anyways this this kind of knowledge is the sort of thing that you could I mean I don't know if you'd actually end up using this in factoring but this kind of knowledge is the sort of thing that we need in order to improve the implementa
tion of these algorithms like I think most of the improvements to them are from realizing there are better ways to do arithmetic like the reason odad algorithm works is because of this uh reordering what your Square wearing things so you keep adding in small multiples instead of big multiples that's not a Quantum specific idea that's a very classical sort of idea um but it applies in this Quantum context and I think a lot of the big optimizations are like that well um on that uh on that note sha
ll weal well well could I I'd like to ask one last question related to this comment about representations to odad you know uh residue number system representations do have this feature that you can do Ari certain kinds of arithmetic very quickly I was wondering if you thought about that at all in the context of this lce based formulation maybe it would allow for further optimizations yeah I haven't I think you you could add and subtract and multiply numbers in this representation without having
to carry you you just store the number mod a bunch of moduli and then you just have to add them digit wise or multiply them digit wise so it makes the arithmetic very quick uh the cost of course is that you can't do division quickly and it's hard to which numberers which other number there's there's a paper that just came out recently that tries to use this idea um yeah you do run into this issue where you can't really do the modulus operation so and because you don't know the factors of the num
ber you can't make pick the primes you'd want you so you need to pick enough primes to store the result with without modding by n where each individual product you're multiplying in has been modded by n so it's not like it's getting incredibly huge um anyways in this paper what they do is they compute these Prime mod things one by one and like kind of add up their contributions to a particular place in the output in order to try to get one bit of it instead of getting the whole thing and I don't
know if the paper is correct or not I don't really I haven't really read it closely enough um but that's I don't know that's a very interesting idea they they have the downside that they have to keep the whole exponent register coherent instead of so they they've made the accumulator register much smaller because they only have this small Prime at any one time and this small bit that they're accumulating but they're doing many many passes over the exponent cubits so they have to keep all those
coherent and there's usually more of those than there are in the accumulator um but it kind of moves the space cost around and I don't know maybe someone could find some interesting combination of this and OD or some other things where you know you get square root of space or something great so there well there is there are questions in the Q&A um yeah is there is there anything burning because let's see uh one of them that I think is interesting is um are there any barriers to getting the size
of the quantum circuit to be o of n instead of O of n the 3es that maybe that's directed at you right so maybe I don't have an answer but I can say that if you're willing to spend more than polinomial time classical post processing then you can actually reduce it a bit further I don't know if I mentioned this before but uh but to truly get it to linear is we would be fantastic it yeah it could be maybe understanding what's really happening in the tus problem might uh allow us to improve things u
m I don't know maybe maybe V know thought about this more than me no um somebody actually asked uh you know the same question I think in uh in the chat uh and you you can do the obvious thing like you know uh say if you want if you wanted uh uh you know the classical post processing to run in time slightly better than number field save then you can you can reduce the quantum circuit size but um yeah I I don't I don't have anything else to say or if you if you believe that um ltis based cryptogra
phy is is broken and actually it's very easy to compute ltis problems then then you do get time Quantum factoring algorithms that's interesting is that's called um like lose lose situation basically you you both lose latis based cryptography and you also lose well you lose even more you lose factoring based cryptography because you can break it in qu in Quantum linear time so have to lose loose situation great uh okay so um but that thanks for for great talk and um thanks uh Peter venod and grei
g for a fascinating panel so um and of course um uh great questions from the audience as well and um I guess see you next time we'll we'll announce the next next collum soon bye everyone bye bye Peter
Comments
interesting, thanks!