Are Quantum Computers Really A Threat To Cryptography?
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Subtitle |
| |
| Title of Series | ||
| Number of Parts | 335 | |
| Author | ||
| License | CC Attribution 3.0 Unported: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor. | |
| Identifiers | 10.5446/48433 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
00:00
Quantum computerBitQuantum cryptographyRoundness (object)View (database)InternetworkingAlgorithmInformation securityPoint (geometry)Multiplication signGoodness of fitMetropolitan area network
01:06
MalwareCryptographyQuantum computerCryptosystemMessage passingEncryptionVorwärtsfehlerkorrekturRSA (algorithm)TheoryInformationRecursive languageProof theoryClassical physicsDivisorAlgorithmOperations researchComputerRSA (algorithm)Symmetric matrixCryptosystemType theoryTerm (mathematics)SpacetimeAlgorithmSymmetric-key algorithmEncryptionControl flowComputer fileRight angleForm (programming)Different (Kate Ryan album)CryptographyPublic-key infrastructureQuantum computerKey (cryptography)ComputerPublic-key cryptographyMessage passingInformation securityData managementUsabilityMassTheoryInformationSpeech synthesisComputer animation
03:06
Quantum computerCryptosystemSymmetric matrixEncryptionAdvanced Encryption StandardRSA (algorithm)Focus (optics)BerechnungskomplexitätAlgorithmTransport Layer SecurityDigital signalQuantum computerRevision controlForcing (mathematics)RootUltraviolet photoelectron spectroscopyMereologyAsymmetryType theoryDifferent (Kate Ryan album)CryptosystemComputerAlgorithmKey (cryptography)Combinational logicComputer animation
04:06
RSA (algorithm)CalculationPrime idealNumberMessage passingCiphertextEncryptionIntegerNumbering schemeExponential functionAlgorithmKolmogorov complexitySieve of EratosthenesField (computer science)DivisorPolynomialLogical constantComputerTask (computing)Classical physicsQuantum computerOperations researchQubitKey (cryptography)EncryptionNumberFunctional (mathematics)Quantum computerPublic-key cryptographyBitRSA (algorithm)Numerical analysisComputational complexity theoryAlgorithmMereologyComplex (psychology)Task (computing)Numbering schemeDigitizingPrime factorLambda calculusBinary multiplierElectric generatorPower (physics)Inverse elementGraphics tabletCase moddingElliptic curveFrequencyPrime numberSchlüsselverteilungDifferent (Kate Ryan album)PhysicistElectronic signatureInternetworkingTransport Layer SecurityClique-widthRevision controlParameter (computer programming)CryptosystemPolynomialPotenz <Mathematik>ComputerMultiplication sign2 (number)Operator (mathematics)Prime idealAsymmetryEllipseComputer animation
10:04
Type theoryQuantum computerLogic gateIntelWaveQuantum computerComputerAlgorithmUniverse (mathematics)Logic gateType theoryBitDifferent (Kate Ryan album)Simulated annealingComputer clusterClassical physicsComputer animation
11:04
Type theoryLogic gateQuantum computerWavePhysical systemoutputLogicSequenceClassical physicsFunction (mathematics)System programmingFood energyState of matterDifferent (Kate Ryan album)Physical systemFood energyQuantum computerOptimization problemQuicksortPoint (geometry)Universe (mathematics)Logic gateEnergy levelFunctional (mathematics)CalculationMathematical optimizationPhysicalismResultantBitImage resolutionTheoremComputer architectureQubitFunction (mathematics)outputComputerComputer animation
13:08
Quantum computerFactorizationLogic gateSimulated annealingAlgorithmMathematical optimizationTheoremHamiltonian (quantum mechanics)Superposition principleComputerQuantum entanglementRevision controlBuildingQubitBlock (periodic table)Classical physicsPhysical systemMeasurementFactorizationLogic gateAlgorithmPhysical systemProcess (computing)State of matterBlock (periodic table)Slide ruleVariable (mathematics)Quantum computerBitBuildingMultiplication signSuperposition principlePotenz <Mathematik>Simulated annealingQuantum mechanicsOptimization problemEquivalence relationInteractive televisionQubitImage resolutionComputer animation
15:05
NumberQubitMeasurementRepresentation (politics)OrthogonalityStandard deviationBasis <Mathematik>Quantum entanglementQuantum computerComplex systemExponential functionSuperposition principleCategory of beingState of matterClassical physicsSystem programmingEquals signCross-correlationProcess (computing)outputComputerSpacetimePhysical systemAlgorithmDivisorSequenceFrequencyRead-only memoryEntire functionExponentialabbildungComputational complexity theoryFactorizationModulo (jargon)IntegerSeries (mathematics)Function (mathematics)Prime idealQuantum computerSuperposition principlePhysical systemMultiplication signState of matterBeta functionAlpha (investment)Potenz <Mathematik>AlgorithmQubitQuantum mechanicsRandom number generationComplex numberSequenceNumberInformationCross-correlationMilitary baseMeasurementRepresentation (politics)Numerical analysisSquare numberBitCategory of beingQuantum entanglementMereologyPrincipal idealMultiplicationMathematicsTelecommunicationDifferent (Kate Ryan album)Number theoryPoint (geometry)Prime number1 (number)Positional notationLevel (video gaming)CalculationPower (physics)CASE <Informatik>Case moddingResultantWaveExploit (computer security)Computer animation
22:37
FrequencyComputational complexity theoryAlgorithmFactorizationIntegerSequenceModulo (jargon)Series (mathematics)Function (mathematics)Prime idealDivisorNumberLinear algebraSlide ruleQuantum computerNumerical analysisAlgorithmLevel (video gaming)MathematicsFrequencyFiber bundleComputer animation
23:16
FrequencyComputational complexity theoryAlgorithmFactorizationModulo (jargon)SequenceIntegerSeries (mathematics)Function (mathematics)Prime idealPhase transitionCode refactoringFourier transformQuantum computerFaktorenanalyseComputerAlgorithmQuantum computerLevel (video gaming)Complex (psychology)FactorizationNumber theoryDivisorComputerFourier transformPower (physics)Category of beingCase moddingComputational complexity theoryPhase transitionFrequencyFunctional (mathematics)NumberComputer animation
24:23
FrequencySlide ruleLinear algebraFrequencyPower (physics)Equaliser (mathematics)Case moddingForm (programming)Numerical analysisMultiplicationFunctional (mathematics)Computer animation
25:12
FrequencyFactorizationDivisorPrime idealFaktorenanalyseAverageSystem callVirtual machineNumerical analysisMultiplicationCase moddingDivisorProduct (business)IntegerNumberDisk read-and-write headPower (physics)AlgorithmGreatest common divisorMereologyCASE <Informatik>FrequencyComplex (psychology)Prime numberCalculationComputerGroup actionComputer animation
27:12
Quantum computerFrequencySuperposition principleEquals signQubitPotenz <Mathematik>Fourier transformMeasurementPhysical systemQuantum computerFrequencyAlgorithmBitNumberResultantFourier seriesMultiplication signIterationSuperposition principleRepresentation (politics)Principal idealComputer animation
28:15
CoroutineFrequencyDivisorQuantum computerQuantum computerGreatest common divisorFrequencyCASE <Informatik>Random number generationTerm (mathematics)Real numberDivisorNumberCalculationComputer animation
29:04
Fourier transformQuantum computerSoftware frameworkSource codeQuantensimulatorComputer hardwarePhysical systemSuperposition principleSimulationOpen sourceQuantum computerDifferent (Kate Ryan album)Computing platformLibrary (computing)Computer programmingResultantComputerAlgorithmComputer simulationComputer hardwareQuantum statePrime numberReal numberComputer animation
30:19
Physical systemSuperposition principleSimulationQubitCoprocessorQuantum computerSpacetimeQuantum computerComputerRepresentation (politics)CASE <Informatik>Error messageFront and back endsQubitMultiplication signReal numberPhysical systemAlgorithmComputer simulationPower (physics)Resultant1 (number)Normal (geometry)Computer programmingComputer animation
31:41
QubitQuantum computerCoprocessorAlgorithmFaktorenanalyseLetterpress printingFile formatInstance (computer science)DivisorComputerLogicFreewareError messageRSA (algorithm)PolynomialCASE <Informatik>AlgorithmQuantum mechanicsQuantum computerComputerNoise (electronics)Library (computing)Multiplication signComputer simulationCountingRSA (algorithm)SoftwareFront and back endsReal numberQubitNumberComputer hardwareComputational complexity theoryOrder (biology)Instance (computer science)Numerical analysisControl flowSystem callComputer animation
33:59
IntegerRSA (algorithm)DivisorSurfaceComputerCodierung <Programmierung>NumberError messageQubitBit rateAlgorithmError messageQuantum computerComputer hardwareQubitBit rateLogic gateCodeSurfaceOverhead (computing)Term (mathematics)NumberComputer animation
34:53
RSA (algorithm)DivisorQubitIntegerConnectivity (graph theory)EstimationStrategy gameQuantum computerCode refactoringLogarithmClassical physicsFrequencySimilarity (geometry)Reduction of orderMultiplicationProcess (computing)Personal digital assistantExponentiationAlgorithmQubitMultiplication signComputer hardwareConnected spaceMathematical optimizationUniverse (mathematics)Term (mathematics)Computer animation
36:09
DivisorAlgorithmRSA (algorithm)Nichtlineares GleichungssystemData recoveryQuadratic equationRootMultiplicationVariable (mathematics)MereologyNumberDiscrete groupQuantum computerAlgorithmFactorizationOrder (biology)Numerical analysisAdditionNichtlineares GleichungssystemComputer animation
36:53
Similarity (geometry)Quantum computerMereologyLengthFrequencyFunction (mathematics)QubitExponentiationReduction of orderIntegerMathematical optimizationSpacetimeRippingCuboidLogarithmVolumeRSA (algorithm)Code refactoringReduction of orderQubitMathematical optimizationAlgorithmMultiplication signQuantum computerComputer animation
37:31
Quantum computerSimulated annealingProcess (computing)Maxima and minimaPhysical systemMathematical optimizationZielfunktionFood energyBitType theoryProcess (computing)Simulated annealingQuantum computerPresentation of a groupFactorizationTerm (mathematics)2 (number)CryptographyImage resolutionAlgorithmComputerState of matterOptimization problemMaxima and minimaComputer animation
38:23
Quantum computerSimulated annealingState of matterSpacetimeFood energyMaxima and minimaPhysical systemInformation securityHamiltonian (quantum mechanics)Time evolutionTheoremMathematical optimizationProcess (computing)Code refactoringFundamental theorem of algebraTheoremPhysical systemPoint (geometry)Quantum computerCASE <Informatik>Maxima and minimaQuantum mechanicsCalculationLevel (video gaming)State of matterProof theoryFunctional (mathematics)Arithmetic meanHamiltonian (quantum mechanics)Optimization problemNichtlineares GleichungssystemMultiplication signPhysicalismComputational complexity theoryComputer animation
40:31
Mathematical optimizationRepresentation (politics)Binary fileFunction (mathematics)NumberQuantum computerWaveTask (computing)Sign (mathematics)Representation (politics)Binary codeQuadratic equationFunctional (mathematics)Optimization problemQuantum computerSimulated annealingBitMatrix (mathematics)Positional notationPrime numberMultiplication signComputer animation
41:13
Mathematical optimizationEquals signCode refactoringIntegerQubitQuantum computerNetwork topologyWaveFreewareSource codeSoftware development kitFunction (mathematics)Mathematical optimizationDivisorComputerFunctional (mathematics)Maxima and minimaQuantum computerLibrary (computing)Product (business)Link (knot theory)Prime numberWaveNumberQubitNumerical analysisComputer animation
42:11
WaveCode refactoringAlgorithmQuantum computerMultiplicationMatrix (mathematics)Representation (politics)Binary fileHamiltonian (quantum mechanics)Process (computing)DivisorQubitCoprocessorPhysical systemAlgorithmPrime numberMultiplication signResultantWaveQuantum computerQubitMathematical optimizationDegree (graph theory)Universe (mathematics)MultiplicationNumerical analysisFunctional (mathematics)Matrix (mathematics)Right anglePhysical systemNumberSimulated annealingOrder (biology)PurchasingComputer animation
44:11
James Waddell Alexander IIQuantum computerWaveIntegerQubitFactorizationParameter (computer programming)Simulated annealingCode refactoringAlgorithmHamiltonian (quantum mechanics)Error messageNumberPrime numberExecution unitQubitBitLevel (video gaming)Multiplication tableMathematical optimizationTuring-MaschineDivisorComputerSimulated annealingQuantum computerAlgorithmMultiplicationWaveUniverse (mathematics)Lecture/Conference
45:29
MultiplicationSimilarity (geometry)Term (mathematics)Computer hardwareDivisorRSA (algorithm)Classical physicsQuantum computerAlgorithmQubitComputerElectric currentFactorizationWaveSystem programmingBitNumerical analysisGoodness of fitQuantum computerComputerAlgorithmPoint (geometry)Simulated annealingEndliche ModelltheorieComputer hardwareUniverse (mathematics)Right angleTerm (mathematics)Computer animation
46:16
AlgorithmSystem programmingWaveComputer hardwareQuiltCryptographyQubitIntegerDivisorDerivation (linguistics)Military operationNumberBitAlgorithmMultiplication signQubitCurveComputer hardwarePredictabilityQuantum computerCASE <Informatik>Public-key cryptographyDerivation (linguistics)EncryptionComputerPoint (geometry)RSA (algorithm)Right angleComputer animationMeeting/Interview
47:54
Symmetric matrixAlgorithmCryptosystemRSA (algorithm)Quantum computerAdditionEncryptionSimulationHash functionQuantum cryptographyOrder of magnitudeMultiplication signStatement (computer science)Symmetric-key algorithmQuantum computerAlgorithmSimulated annealingWordComputer animation
Transcript: English(auto-generated)
00:00
How many people know about quantum physics? Yeah? Yeah? So I was looking at this, I was looking at this, this talk synopsis and I'm like, maybe this is going to be a good talk. Maybe not. Maybe it won't. I guess I won't really know until I take a look at the talk. Yeah? Learned that from my baby book. Yeah, awesome. Alright, so, let's give
00:26
Andreas a big round of applause for coming all the way to Vegas from Sydney, Australia to talk to us about quantum cryptography. Have a good time, man. Thanks so much. Alright, welcome everybody. Um, yeah, after that introduction, hopefully you walk away and
00:43
learn something in this talk. So, um, quantum computing, if you read whatever is in the press, you either think we are completely doomed and, you know, the internet's going to end or, uh, nothing's going to happen because they will never exist. So I thought I want to explore this topic a little bit more from an algorithmic point of view and really see
01:00
where we are. Not so much on the hype, but more really what are the algorithms that we talk about right now. So, um, I started various companies in the security space, you know, starting in 2002, which, um, makes me feel slightly out right now. Um, but first I'm speaking at DEFCON, very happy about this, you know, long term F and D but never spoke here, so let's get right into this. So when you talk about
01:24
cryptography, we mainly, you know, look into two different, um, types of cryptography. One is a symmetric cryptosystem, which is a symmetric shared key. Uh, you know, kind of like AES for example, both sides encrypt and talk to each other with the same key. And
01:41
we have asymmetric, uh, cryptosystems which use public key infrastructure, where basically I use a public key to encrypt a message and a private key to decrypt it. Um, there's various forms of this, uh, obviously for digital signatures as well. And, um, in, in this realm, um, virtually every cryptosystem right now that is deployed, uh, anywhere is
02:02
what we call computationally secure. That is secure in the sense that there are known algorithms that can break them, but all of the algorithms that can break them are not easy to do in the sense that, you know, uh, if I want to break an, uh, you know, 2048 RSA key with a normal computer takes me a couple of trillion years, which means I'm
02:25
secure even though there's a known algorithms, uh, that can break them. Uh, there are information theoretic algorithms out there, most notably an algorithm called, um, a one-time pad or vernum ciphers, but they're really tricky and not really practically
02:40
usable. For example, with one-time pad, you do need to use the same amount of keys as you want to transmit. So if you want to transmit the one megabyte file, you need to have a one megabyte key. Basically for every byte you need a different, um, uh, for every byte data you need a one byte key. So you would have to manage massive amount of key material which is not really, uh, practically, but I mean, they do exist. But outside of
03:03
this, virtually every, uh, cryptosystem is just computationally secure. And, um, when you look at this, uh, quantum realm, and I'm going to quite some detail about this, uh, for those two different types of algorithms, it is, uh, much more interesting to look at the asymmetric part of the, uh, of the cryptosystems. Because in the symmetric
03:23
part, there is a quantum algorithm as well called Grover, which basically looks into, um, a, or provides a quadratic speed up to the classical, um, version. Basically in the classical world, if I want to look for the shared key, I need to basically brute force every different combination, which obviously takes forever. Uh, I get a squared
03:43
root up, um, a squared speed up in the quantum version, which is a fantastic speed up. You know, if I can speed up 150 trillion years, it's, you know, a lot of years, but it's still obviously 150 trillion years, uh, to break it. So that's not really too interesting. So we want to focus here on the asymmetric part where, um, the, uh,
04:01
speed ups that quantum computers can provide are massive. And, uh, we want to go into quite some detail, uh, why, uh, their speed up is so big as it is, and, uh, how they work. So let's revisit just a little bit of how RSA encryption works, and it's really just a basic, uh, introduction so we can use them, uh, to understand how the, uh,
04:21
quantum versions of these algorithm works. Basically, I choose two prime numbers, P and Q, and, um, uh, with those, I, I just multiply them, get the number N. Now with the number N, I can calculate this lambda N function, which is a Carmichael function, which is just a function, I can easily calculate this. And once I have this, I just choose another
04:42
parameter E, which is smaller than the, uh, lambda N, uh, uh, value, and then this N, together with the number E, is my public key. I can give this to everybody out there who I want to choose to do, um, uh, the asymmetric encryption. And I basically retain my private key, which is this, uh, uh, number D here, which is just the modular
05:04
inverse of the number E, which is the, the public key. Obviously, mod, mod lambda N, is always mod lambda N, kind of, uh, in, in this, uh, uh, scenario, which is the private key that I retain. And with this private key now, with this scenario, I can now
05:21
look into, hey, I can now encrypt something and send something, um, from Alice to Bob, and, as everybody knows, with asymmetric encryption, I can only encrypt something that is smaller than my key, so if I have a 2, 4, uh, 2048 bit key, I can only encrypt something that is smaller than, uh, 2048. Um, so I need to pad my plaintext into, um, uh, a number N, so I
05:47
turn this big M into a small number M. Um, uh, there's various ways for this, ways for this, I don't go into too much detail, but this is where the padding scheme, uh, comes in, and then I basically end up with this number, uh, uh, small M. And my ciphertext, my
06:01
encrypted version is really, I just take, uh, this number M to the power of E, mod N, and that's basically my ciphertext. And this is what I encrypt with a public key, and I can now send this, uh, number C to, uh, um, to Bob, uh, or receive this, and if you
06:21
have the private key, you can easily decrypt this as well on the other side. And, uh, you can easily see how this works, it's really very straightforward. If someone has the C and the ciphertext and the D, the private key, by definition C is M to the power of E, so you see, um, uh, but the definition of D was, that is actually the inverse of E, so this E
06:42
to the power of D just, uh, equals out, so I end up with M mod N, so, uh, if I have the private key, I can easily recover, um, uh, the, uh, the small M, and obviously by just reversing the padding scheme, I have now my, uh, my message again. So this is basically how RSA encryption works into some detail. So, my task is now, I do have a
07:06
public key, because it's public, everybody knows what the public key is, how do I turn this into a private key? Now, from the definition, from the definitions, it's really pretty, uh, straightforward and simple, um, I need to find those prime numbers that make up
07:21
this number N, the number N is known, it's part of the public key, and if I can do this, I can easily calculate lambda N, which is really just the, uh, least common, uh, multiplier of, uh, lambda P and lambda Q, and from that I can easily derive the private key D, um, uh, and I'm done. So all I need to do to basically go from a
07:44
public key to a private key is to find those two prime factors P and Q, um, that I chose in the very beginning when I set up my key, um, and then I have everything I need to do to basically derive a private key from a public key. Um, while that sounds pretty easy and
08:03
straightforward, actually to do this and to factor this number N into the two prime parts P and Q is, um, uh, is really, really hard, and all of the classically known algorithms are all from exponential complexity, which means they're really, really hard, uh, to solve, even, you know, the, uh, GNFS algorithm is, uh, slightly sub-exponential but still
08:26
massive in scale, so that gives you those assurance that if you have, if you use any of the asymmetric algorithms, uh, people would need trillions of years to decrypt them, so they're fairly secure for generations to come. But in 1994, a guy called Peter Shaw, he
08:41
was a, um, theoretical physicist, came up with this algorithm, if we were to use quantum computers, obviously in 1984 there was all just a theory, quantum computers didn't exist, and they hardly exist today, but, um, but the theory says he came up with an algorithm of how to factor those numbers in just polynomial time, and in just polynomial time really
09:04
is a difference that is, that is almost incomprehensible, because it really means instead of taking a trillion years on a classic computer with a trillion operations per second, let's suppose I have a quantum computer which just does a million operations per second, I
09:21
can actually do the same thing in just 10 seconds. So the difference between exponential complexity and polynomial complexity is just out of this world, and that obviously, if we could run this algorithm, would pose a big threat to, uh, basically the whole, um, uh, crypto systems as it is deployed, because the base of this,
09:40
whether it is, um, you know, for RSA, or elliptic curves, or for digital signatures, ECDSA, which is used in Bitcoin, or for a key exchange like Diffie-Hellman, which is mainly used in everywhere you go, uh, on SSL, TLS exchanges, so the base foundation of this is used virtually everywhere in today's internet, so that would be a big threat. So let's
10:03
explore a little bit, um, how Peter Shaw could come up with his algorithms, what is actually needed, and how they work in, uh, in reality. So, now we need to do a little bit of an introduction into quantum computing, and, uh, it gets only as deep as I thought we
10:21
need to go to understand how Shaw's algorithm works, and, uh, what we need to understand, um, uh, so hopefully it, it's not, it's not too bad. So basically there are two big types of quantum computers that we look at right now. One is called gate-based quantum computers. That's a big chunk of what everybody's working on. All the big guys, IBM,
10:41
Intel, Microsoft, Alibaba, they're all working on gate-based quantum computing, which is called universal quantum computing, because I can solve virtually any problem similar to a classical computing, uh, on this computer. There's a different computer, um, uh, called quantum annealers, or adiabatic, uh, quantum computing, which is, was the first
11:01
quantum computer that was available was from D-Wave. And D-Wave's computer, this adiabatic quantum computer, is not a general quantum computer. You cannot solve every problem on this quantum computer. It is very specialized to only solve a particular optimization problem. So it's very much, um, you can look at this basically as a
11:21
physical system, and physical systems tend to always end up in the lowest energy state, which we call the ground state of this physical system. So if I can now define a function that I wanna solve, and I basically define those functions in a way that the lowest energy state is basically the same as the solution to this optimization problem, I can
11:46
use this physical system to solve the problem that I have, because I know the physical system will end up in the lowest, uh, energy state, in the ground state, and I know then, this also tends, this also represents in the state where my optimization problem
12:01
reached the lowest point. And that's a really cool, um, theorem, um, which actually guarantees to me that I end up in the lowest state that there is. You can really think of this as kind of like mountains and valleys, and you could end up in a valley that is just halfway through and you're not really in the lowest state. But there's a theorem, um, we're gonna explore this a little bit, which guarantees, which gives me
12:23
way, how I can really be at the lowest state so I can solve, or I can find the optimal solution to this optimization problem. But it's really just solving optimization problems. The gate based quantum computing, uh, is really a general quantum, is a general computing, um, uh, architecture, where you start with an input, you apply all
12:42
sorts of different calculations to it, technically those are all gate based, uh, calculations, you do an AND gate, you take two qubits, do something to it, you get a result, but essentially you have an input, you calculate something and you have an output, and it's basically, uh, you can calculate every, uh, everything you want to calculate, uh,
13:00
with these, uh, universal quantum computers, uh, while quantum computers like device can really only solve, um, optimization problems. But actually as it turns out, both approaches can be used to solve the factorization problem. And, uh, we have Shor's algorithm from 1994, which, uh, um, uses gates to, um, uh, solve this problem. And in
13:24
quantum annealing, we have various approaches since 2002 and I want to explore those a little bit in the, uh, next couple of slides as well, how they work to actually, um, uh, solve the factoring problem as an optimization problem. So, let's dive a little bit into quantum computing and what I need to understand to, to explore a little bit Shor's
13:44
algorithm and really with the idea of giving you an understanding of how can someone derive an algorithm that gives me now such a dramatic improvement over a classical algorithm which takes, uh, exponential time, uh, to solve. So, the basic building blocks for, uh,
14:04
quantum computers are what we call qubits. Qubits is the equivalent of a classical bit. A classical bit is either 0 or 1. A qubit is now a, you can almost think of it as a quantum mechanical system, which can be in any state you want it to be and you don't
14:20
actually really know what state it is. But once you measure this quantum mechanical system, it is either gonna be 0 or 1. And this is an, uh, this is something that we're gonna exploit later on, that why, before we measure this system, we don't know which state it is, but it can be actually in a superposition, it can be in a state where all of
14:41
these, um, qubits can, um, interact with each other and only at the very end of my processing step I will measure the system and all of those superposition state will, uh, basically terminate and I know it's either 0 or 1. But it's really a quantum mechanical system, you don't really know what it is, it's neither 0, it's neither 1, it is
15:01
something in between, uh, quite often we then, uh, assign, um, uh, variables to it and here you can see a representation of one of those qubits. We have this, uh, two bases, 0 and 1, which basically represent this, uh, 0 means if I measure this particular qubit in 100% of the cases, I will get the, the measurement outcome of 0. The 1 means in 100% of
15:26
the case of measurement it will give me the measurement outcome of 1. And now a qubit is in the superposition of those two with the alpha and beta. Those are two complex numbers, I can represent those and, uh, that can now define, uh, the state of this
15:41
particular qubit. Now, we call alpha and beta probability amplitudes because if I measure this particular, um, uh, qubit I will now get the probability of the measurement outcome for, uh, to get the measurement outcome 0, the probability is gonna be alpha squared and
16:01
the probability of getting the measurement outcome of 1 is gonna be beta squared. Remember when I measure this particular thing, even though I have two complex numbers associated with it, when I measure it, it's gonna be either 0 or 1 with a certain probability associated with it and the probabilities are really defined by those two numbers, uh, and basically to the squared, um, uh, for alpha and beta, uh, we know I
16:26
know it's gonna end up in 0 and with those two numbers I can represent those qubits. It's basically a mathematical representation of the quantum mechanical system, uh, that the, uh, quantum computers operate in. But remember all of these measurements and everything we do
16:41
in the quantum world is probabilistic. Everything is just a probability. I can put a quantum in a state where I can tell you in exactly half of my measurement it's gonna be 0, in half of my measurement it's gonna be 1, which is perfect for random numbers for example because I can tell you, hey, you don't really know whether it's 0 or 1, it's exactly equal probability of getting 0 and 1, so I just take one qubit, measure it 5
17:04
trillion times and I get 5 trillion, uh, random bits. But obviously I don't really know whether I get 0 or 1, it's all defined by probabilities, which has a big implication on the algorithms because the algorithms will also only give me probabilities. There's no algorithm that can give me, I run through this algorithm
17:22
once and it will give me the answer, yes it is this answer. It will always only give me, yeah, I think with 83% probability it's gonna be this answer for example. So quite often you run these algorithms multiple times to really see, um, uh, uh, where you end up with. The second, um, uh, principle that we need for Shor's algorithm is the
17:43
concept of entanglement. And, uh, that gets slightly philosophical, um, I wanna focus a little bit more on the mathematical part of this. Entanglement is basically a property where I can have two qubits and I know that there's some correlation between those two qubits. In the classical world I have two bits and the two bits are completely
18:01
independent of each other, neither of those bits will interact with the other and if I, if this qubit, if this bit is 1, doesn't matter what this is. In the quantum world I can have a, a relationship, a correlation between those two qubits. And a simple example is Bell's state of two qubits. So this state is here a state where you can set, wave two qubits.
18:23
In those funny notations the first 0 is the value of the first qubit, the second 0 is the value of the second qubit. But if I would measure this qubit here, and let's suppose I measure the first qubit as being 0, it cannot be the second one because, you know, the first 0, the first qubit was 0. So the second qubit has to be 0 as well. I know that
18:45
the second qubit is going to be 0 simply because I measure the first qubit and there's no way because I don't have 0 ones or 1 0 in there that the second qubit could something different than 0. So I take basically two qubits, give them into this quantum
19:01
mechanical system, prepare this Bell state and now I have two qubits that are separate from each other but in this quantum mechanical system those qubits are now correlated or what we call entangled. And now I could give one qubit to Alice and send her to the moon and one qubit to Bob and send him to Mars and I know that if Alice looks at her qubit
19:23
and Alice says oh I got a 0, I know Bob has a 0 as well. Even though there's no communication between those simply because there's this correlation in those properties now I need obviously those two qubits, I need to prepare them together and then I can send
19:41
them anywhere I want uh and they are correlated without any communication in between those two. Um there's lots of philosophical implications because I could give, I could put those two qubits light years away from each other and uh did I really find a way of communicating faster than light? Uh no I didn't because if Alice measures it's gonna be
20:03
0, if she wants to tell Bob hey I measured 0, she needs to communicate this information uh to Bob which obviously uh she needs uh a few light years to do so. But it's an important principle that we're gonna use in Shor's algorithm as well. And the main thing for you to understand is the um exponential large size I can look into when dealing
20:24
with those quantum systems. Let's suppose I take two classical bits, I can uh represent four possible states with two classical bits. But only one of them at a time so you know if uh I mean you see the four states there, my system with those two bits is in one of those states at any one point at any point in time. In a quantum world I can take two
20:45
qubits and basically at the end when I measure this system, it's also gonna be in one of those four states. But before I measure this system, the because of superposition, those qubits can be in all four states at the same time. And only when I measure the
21:02
system, the system will collapse one of those uh four states. And this is exactly now um a situation we're gonna exploit. We have n qubits, I can represent two to the power of n states. While I do calculations, I still at the end of the day need to know what the result is of my calculation. So I need to measure at some stage and then it will collapse
21:23
obviously to um uh those n states. But during calculation I have two to the power of n states which is a massive amount of uh um uh states that I can represent with just a few amount of uh of qubits. So now I now have everything kind of to look into Shor's
21:41
algorithm and uh and how it works. Um uh and we're gonna look into this. So the main idea for that Shor had was actually if I wanna look into how to factor uh n into p and q into those prime two prime numbers, I don't actually need to solve that problem. That problem is equivalent to a different problem. And basically he looked into number
22:00
sequences and he realized from number theory that you have a number sequence. For example, uh you look at a number sequence here um you multiply the previous number by two. So one, two, four, eight, sixteen, thirty two. If you now do, if you now use this number sequence and do this mod fifteen for example in this example. You end up with a number
22:24
sequence one, two, four, eight. One, two, four, eight. One, two, four, eight. This is what we call a periodic um uh sequence. So it's always gonna be the same uh kind of uh sequence of one, two, four, eight. And we can now define a um uh uh a number which is called the period. Which is four which is basically the number of the the amount of
22:45
numbers before it repeats itself. And um uh the underlying algorithm from Shor is that if I want to find out the factors for this number n, if I wanna find out this p and q, I can actually transform this into a problem of finding the period r. And that turns out
23:03
for that problem I can run it very easily on a quantum computer. So basically um uh if I look into this and the cool thing is and I wanna show you this on the next slide. The mathematics behind this is actually fairly trivial. Basic level of linear algebra gives you everything to understand how this works. So the only thing you need to accept is
23:23
that out of number theory there's a theory which basically says this number this function uh f f a x to the power of a mod n is a periodic function. Um if x has uh particular properties and now I only need to find uh the number uh the uh period r. And with
23:41
this I have my algorithm Shor which we run through in quite some detail actually but essentially it's comprised of three phases. First is I turn this factoring problem into a period finding problem and that's actually trivial. Then I use a quantum computer to actually give me this period r to solve this period r on a classic computer is again
24:02
really really hard. Actually on a classic computer still of exponential um uh complexity which mean that this algorithm on a classic computer does not give me any advantage whatsoever. But I can use a quantum Fourier transform and that gives me the speed up and then basically once I have the period r I can really very trivially um uh use this to
24:23
find the factor. So stage one or step one and step three are really trivial. Step two is where all the magic happens and that's where the um uh that's where the main speed up comes. Now I don't wanna go into too much detail but it's actually really simple so I think you can uh download the slides and you can look through this. I know that f a is
24:43
periodic. I know that x to the power of zero is one. I mean everything to the power of zero is one. And if r is now my period I know because the function is periodic that x to the power of r mod n equals one two equals the same what it was before because it is period. And really with basic linear algebra I can now use the x to the power of r
25:03
equals x to the uh power of r half to the power of two and I can uh um just write this in a different form which gives me this um uh multiplication of two numbers that will give zero mod n. So if I can use this if I have this r I have these two numbers so but if those
25:27
two numbers um uh mod n is an those are an integer and multiple of n because their product is zero mod n so that means they're an integer and multiple of n. So either
25:40
those are directly factors or if they're not directly factors each one of those has a factor in common with a number I want to look at. So the greatest common divisor which is actually um not too hard to compute uh classically it's just an n squared complexity so
26:00
by computing the greatest common divisor for each of those numbers with n I have my factors uh for uh uh for n. And uh that is really simple but to get to this r is really really hard. But I can put this together in a really uh quick example let's suppose I have n equals 15 now everybody can calculate in their head that the prime numbers are 3 and 5.
26:23
Basically I choose any integer between 1 and 15 and let's really use for the sake of simplicity let's use x equals 2. So you can see my period here mod 15 is 1 to 4 8 so I have a period 4 I can see this that's a really hard part to uh calculate. But with a period 4
26:43
the greatest common divisor of x to the power of uh uh r half is r is 4 so r half is 2 uh x is 2 so that's 2 to the power of 2 which is 4. So the greatest common divisor of 3 and 15 and 5 and 15 so so uh 4 minus 1 and 4 plus 1 is obviously 3 and 5. And when you
27:04
calculate this through actually in every case you come up with uh 3 and 5. So that's exactly what Shor's algorithm is all about. But the really hard part is uh figuring out uh what is this period r. And this is kind of where the quantum uh compu- uh quantum algorithm comes in. And those quantum computers or those quantum algorithms always work
27:23
in the same principle. You basically you you initialize basically the result that you want to see and say let's think of we want to get a 256 bit number or two 2048 bit number and basically every bit every bit of this bit representation is going to be either 0 or 1. So
27:42
you basically put this in an equal superposition. So every bit you basically put at 50% 0 and 50% 1 because you don't really know what it is. So it's really kind of like uh at 50%. Then you run through this um quantum Fourier transform which will use amplitude amplification. So with every iteration of this algorithm those amplitudes will now go
28:04
towards 1 or to 0 which is going to be the final result. And you run this through um a number of times and then you measure it at the end and you will see when you end up with. I gonna have an example of this uh um when we run this uh through on a on a real
28:21
quantum computer. But just to um summarize Shor's algorithm all together is uh fairly simple. You choose any random number a which is uh smaller than n. You compute the greatest common divisor. If this is not 1 actually you found a you found a fact and you're done. Uh but that's uh obviously not the most likely not the case. I use my quantum
28:41
computer to find this period r and once I have r I just need to find the greatest common divisor of those uh two um uh two terms and I'm done. So um uh another example I choose randomly uh number 7 calculate period r r equals 4. I have this greatest common divisor 48 and 15 and 15 and 15 gives me uh 3 and 5. So it all works fine. I
29:06
can now use this and use a um a library a toolkit called kiskit which is an open source toolkit. There's now at least 5 or 6 different open source platforms how you can use quantum computers and how you can program quantum computers um either on quantum
29:23
simulators or on real quantum hardware. And I gave you some references here you can look up those it's actually kind of fairly easy um uh to go through. But they all start the same and here you see an example of this amplitude amplification. Basically in the end you see all of the possibilities what the my prime numbers could be. They're all in the
29:43
same probability what they could be. That's my starting point. And once I run through this algorithm and I ran through this uh short algorithm on from these references the amplitude of the correct results have now been amplified. And the amplitudes of the wrong results have now been kind of like gone down to 0. And I actually see that there's
30:04
2 results r equals 0 and r equals 4. r equals 0 is obviously a trivial um uh um probability so I discard this. And I end up with r equals 4. So this was now executed on a quantum simulator. Quantum simulator I can simulate a quantum state on my normal
30:20
computer. But remember in quantum computing we're exploiting this fact that I have this massive large space of 2 to the power of n. So I'm gonna have really trouble simulating more than whatever 100 qubits or so on a normal computer. And um uh but for smaller ones for illustration it's actually quite cool. So the cool thing is IBM has a quantum computer
30:41
that you can publicly access. You can write a quantum computer program, execute it towards their cloud. It's very simple you just change hey my backend is a simulator you change your backend to uh IBM's quantum computer. Um and if you execute this against a real quantum computer it's just a 5 qubit quantum computer um uh right now. I still get r
31:03
equals 4 with the highest probability. But you see there's lots of other probabilities. And those probabilities are representative of all the errors you have in the system simply because those quantum computers that we have right now are really pretty bad. What they are what we call noisy. They don't produce the correct results because they're
31:24
noisy. They produce lots of wrong results. Now by repeat repeating my algorithm lots of times I can still get around this fact and obviously in this case I still have r equals 4 the highest probability. But obviously that has big implication on performance because I need to now repeat these uh my algorithms much more. And
31:43
obviously I will end up in uh dead cases because uh obviously the noise will basically um reduce the speed up in the quantum effects uh to 0 and it basically collapses to um uh a um a classical computation that I have. But the cool thing is actually with uh
32:01
Qiskit as well there is uh libraries for every quantum algorithm that you know that people know and they kind of uh provide easy libraries. If you want to run Shor's algorithm to factor prime uh to factor any numbers you just import Shor's algorithm from uh Qiskit aqua which is uh which is a library. You just say alright I want to factor this number n
32:21
equals 15. I use a simulator. I do this uh 1,000 times and off I run this instance and I get a result. How cool is that that you can run this against uh against a quantum computer and the only thing you need to do in this example is if you run this against a real quantum computer is to change this backend from the simulator to a different
32:41
backend and now there's a call out to IBM's uh quantum computer to run this uh on their backend. It's actually really really cool and this feeling when you run a quantum computing uh software for the first time is actually it's actually quite cool. So I encourage everybody to look at Qiskit or various quantum computing uh libraries um uh and to play around with this. So the problem obviously is um uh and you guessed it that in
33:05
order to do anything meaningful I need lots of qubits. So in order to use Shor's algorithm to um uh break RSA 2048 I need 4,000 qubits and I need 4,000 proper qubits meaning without any noise I need for the time of the computation there can't be any noise
33:24
on the computation as well. And it's not really a surprise because when Shor came up with this in 1984 there were no quantum computers. He didn't have to worry about hey can I really implement my algorithm or not? He really just came up with a system and method. So um it was never really meant to run on a quantum computer. And uh right now
33:43
lots of people look at Shor's algorithm and then see alright kind of right now we have 70 qubit so it's every the qubit count doubles every year whatever so it's gonna be another 10 years before we have uh Shor's algorithm. Nobody's gonna run Shor's algorithm because it was just a theory. So let's look at some of the the uh
34:01
researchers where people took people took Shor's algorithm and modified them and optimized them to run on real quantum uh quantum hardware. So the first one was Fowler in uh 2012. Basically the the first approach was really kind of I need to tweak this algorithm so it can be so it can sustain errors. Because Shor's algorithm really was
34:22
an assumption there's no errors all the qubits are fantastic uh no errors. So basically they used what's called the surface codes to allow for errors to occur and the error rate is 0.1 per side of the uh of the gate error rate. And um uh Fowler came up, I can run Shor's algorithm and I can factor 2048 bit number but I need 1 billion qubits uh
34:45
to do so. Which is obviously a massive amount uh in terms of overhead um uh to run this. So that was in 2012 not not too long not too long ago. And then in 2017 with first optimizations from McGorman we suddenly kind of like uh had an uh had an algorithm where we
35:03
reduces 1 billion qubits to just 230 million qubits uh in 2017. And those are really optimization the physical connectivity of those qubits. And uh then Georgiou kind of reduces further to 170 million qubits. So you can see there's algorithmic improvements without any hardware improvements obviously that's happening at the same time as
35:25
well. But obviously I get down from 1 billion qubits to right now uh 170 million qubits. And the biggest um uh contribution was from Gidney and Akira from uh um uh Google and uh University in Stockholm where they uh provided paper just not long ago earlier this year
35:41
where they uh looked into how they could do the same thing what everybody else is doing with just 20 million qubits. Now we went in 2012 from 1 billion qubits to 2019 to 20 million qubits. And we are far from the end of the research there in terms of optimization uh to this problem. Now I won't go into too much detail of this uh of what
36:05
they do. But basically they also look into lots of optimization of how things work. And they basically also choose similar to show not really look into factoring the numbers directly. So they basically convert this factoring problem into short discrete algorithm
36:21
problem. And um uh they have a part that is computed classically and a part that is computed um uh quantumly on a quantum computer. And they can show that in order to find P and Q they can uh come up with obviously they know what N is which is the
36:41
multiplication of those two. They can come up with a number where they know the addition of those numbers are D so D is known. So they have two um two equations for two variables which they can fairly easily solve fairly easily. It's obviously an overstatement because they still need uh 20 million qubits uh to do so. Um uh but obviously the um the
37:02
reduction from 1 billion qubits to 20 million qubits is massive. And uh I expect in the next couple of years there's gonna be lots of optimization to Shor's algorithm and especially to Gidney and Nakara's um uh uh algorithm uh where this is gonna be uh reduced uh further on. Obviously 20 million qubits is still a long way away from uh
37:22
quantum computers that are accessible today um uh where we are in a realm of you know slowly below 100 qubits um uh at this point in time. So I wanna spend the next you know or the last 10 minutes of my presentation on approaching quantum annealing. Those is the second type of quantum computer and uh that is actually what's quite surprising to
37:43
me even though everybody's talking about Shor and the implication of cryptography. Actually quantum annealing right now is much much further ahead in terms of solving this factorization problem and we're gonna look into a little bit how uh these algorithms work. So as mentioned before quantum annealing those computers are really
38:01
computers where it can solve an optimization problem. I need to I need to define my problem as an optimization problem and then basically quantum annealing computer can take this problem and find the minimum of this uh problem because it represents a physical side and I know the physical side will always end up in the ground side and uh I can
38:20
read them this ground side and I have this solution to my problem. And there's really a cool a cool theorem um uh where you wanna find you wanna go into the lowest point you wanna find this lowest point on the right hand side. So how do we end up in this lowest point and not get caught up in those uh minimas uh in between and there's lots of ways how you can do this from the uh from the physical system. And that's a really
38:45
cool case on this quantum annealing case where there is a theorem that says if I start in a really in a very easy quantum mechanical system in this really easy quantum mechanical system I know the ground state. So this is my problem I wanna solve is here.
39:04
I am starting here and I really know where I am. I can now slowly evolve and adiabatic means slowly evolving the state from this here to the state where I really wanna be and now this theorem gives me a guarantee or a physical proof that I will end
39:20
up in the in the maximum or in the optimal minima of the problem I wanna solve. And it's really cool so I have Hamiltonians are functions that define a physical system but basically if you look at the first function if you put in S equals zero you end up in this H zero which is my easy to understand system where I know the local minima and in my
39:43
calculation I slowly move S from zero to one and if I'm at one I'm in the stage H one which is the problem that I really wanna solve but this uh adiabatic theorem guarantees to me that I will end up in the maximum uh minima uh for the problem that I really
40:01
wanna solve which is really really cool because it gives me I'm I know I'm not gonna be caught into some local minima but still essentially I wanna solve a optimization problem. How do I do this? And the first research came from Burgess in 2002 from Microsoft where you know he provide a foundation of hey I wanna solve basically if I wanna look into the problem N equals P times Q I'm looking for P and Q um uh so that this
40:26
equation is true so I just need to solve this I need to write this as an optimization problem and basically re re rewrote this as N minus P Q squared and this is a positive function this is always greater than zero and this obviously only zero if N equals P Q and
40:43
if you write it this way you have what's called a QBO a quadratic unconstrained binary uh um optimization problem which you can happily run on any quantum annealer that is out there and you basically use binary representation and it's really just a fancy way up here of writing P I and Q I are just the I's you know bit it's either zero or one and uh you
41:05
basically now uh write this down and it's a very simple example my example fifteen is five times three now I'm uh in binary notation P equals X one one the the last bit always has to be one because the prime number can't be an even number and I just you know N
41:22
minus P Q squared I just write this through and kind of by hand and see oh this is a function I need to minimize now and I can run this against D waves quantum computer and if I find the minimum I know N equals P Q because that's by definition a positive function so I
41:40
can use quantum uh a D waves quantum computer they provide a library as well and um you see the link here you can download it it's basically the same thing I just call factor P P is my um uh product and I can run this on this uh D waves quantum computer the problem is if I just use this without any optimization I need N squared qubits for this so I
42:03
mean my number of qubits that I need really kind of like grow quite heavily and for larger numbers that is not sustainable um uh to do but I wanted to show you it's all probabilistic so if I run this one time I end up with um my four fifteen uh for the
42:20
P and Q for my two prime numbers is one and seven which is obviously wrong so I ran this once and I didn't really end up in the uh in the right spot but I ran this five times now I already have five and three it's already sixty percent um uh you know probabilities and if I ran this fifty times you know I know my prime numbers are uh three and five so I now I need to run those quantum algorithms more and more often to make
42:44
sure I end up in the same results um I'm gonna skip over some of those things because virtually all optimizations of now this base you know of of purchase work where he basically looked into hey my multiplication matrix that you write out as a function to be
43:00
minimized there can be lots of optimizations virtually all of the uh work that I will present here now is based on optimizations of how you do the multiplications down below here if you've ever done uh multiplications by hand you know you start on the right and you kind of multiply the lowest numbers and then you have carryovers to the
43:20
and virtually all of those optimizations um uh go through this uh how I can you do this multiplications much easier 3D and Agassi did some work in 2016 where they used some of these uh optimizations to remove some of the order of the degrees so they were already able to factor a number greater than two hundred thousand with almost nine hundred qubits
43:44
now D waves qubits on quantum annealing are not as don't have to be as good as universal quantum computer qubits so D wave announced a system with uh I think around five thousand qubits for next year so nine hundred qubits what was was what available then then uh back then on universal quantum computers the biggest prime number is less than
44:06
one hundred and they these guys in 2016 could already now factor a number that was over two hundred thousand the big breakthrough was from Jung et and uh in uh Indiana uh in April 2018 and it's really kind of mind blowing uh you see the next one which was really
44:22
just uh two months after really around optimization of this uh multiplication map and they've now raised they could factor a number which is greater than three hundred and fifty thousand with just ninety four qubits remember D wave comes up with five thousand qubit quantum computer uh next week uh next year um uh and it's all based on this
44:44
optimization uh problem that we solve for factoring and with the optimization to the multiplication table and then paying in two thousand uh in uh earlier this year really um uh and you can see this uh submission was received in July while the previous
45:00
submission was I think uh submitted in April or something like this just months after optimizes even further and they've been able to factor a number that is greater one million with just ninety qubits so that's already twenty bit number so right now when we look into the problem of hey can I use a quantum computer to uh factor prime numbers universal quantum computers and Shor's algorithms are nowhere compared to uh quantum
45:25
annealers and with quantum annealers I can already um uh um do this with uh twenty bit uh twenty bit numbers so um there's uh three things really interesting so they they could run this on already existing hardware today and all of those
45:40
algorithms and that's a really big takeaway um uh that you have to do this I don't have just one quantum problem that I want to solve it's always a hybrid model of some classical com- computation and some quantum computation I really use a classic computer what he's good at and a quantum computer what a quantum computer is uh um is good at so um my point is quantum annealers are a thousand fold better right now
46:07
than uh Shor's algorithm on universal quantum computers but because they are too noisy right now we are far away from breaking anything that is uh in used in practical terms right now the biggest number is a twenty bit number but obviously we we know uh those two uh
46:25
kind of like converging curves here the algorithms are getting better and better at the same time the quantum hardware gives me more and more qubits as well so both of them will actually have a big impact I can't just rely on my prediction saying hey the number of qubits grow by fifty percent every year so I'm going to be fine for the next fifty
46:42
years you're neglecting the improvements that the algorithms will make over the next uh over the next couple of years or two so a couple of uh myths and reality Shor nobody's going to implement Shor on any quantum computer whatsoever um uh Shor was a theoretical work there are practical work um uh you know derivations of this work that
47:03
will be implemented um at some point obviously on the on the base of Shor's algorithms people will break um uh the uh RSI encryption it is a matter of time now we can argue whether it's ten years, twenty years, fifty years but we are only arguing about the time we are not arguing about that it will happen and obviously there's lots of cases
47:24
where this is already has an impact right now if I have bitcoins right now and if my public key is known I don't care whether it takes me twenty years to uh get the private key to those uh to those bitcoins forgetting twenty years there's you know one and a half million bitcoins from Satoshi flying around which is around twelve billion dollars right
47:43
now hey if someone comes to me and says hey Andreas you know can you can you build me quantum computer I say hey it's really hard it takes me twelve billion dollars you know hey here's twelve billion dollars right there so um um so anyway uh it takes it will be quite a while but I want to provide overview of the algorithms I started this talk
48:01
talking about hey just the asymmetric world of the RSA world but there's plenty of work and this is uh kind of you know from this Chinese paper in the very very end that's the that's the uh the end statement there's plenty of work underway right now to use quantum anneals also to look into symmetric encryption so if you say hey I just use
48:21
symmetric encryption I'm fine that may not be holding up for too long and I thank you very much I'm out of time thank you very much for your time we have time for questions we don't have time for questions you can find me anywhere if you have some questions happy to engage with you thanks so much
Recommendations
Series of 13 media