Quantum supremacy is this very basic

scientific question people researching quantum computers have had over the past

few decades. Is basically can a quantum computer actually do something that a

classical computer cannot? Welcome to Hedera Hashgraph's Gossip About Gossip.

If you are a developer, an entrepreneur, crypto enthusiast or just trying to

learn more about how distributed ledger technology and Hedera Hashgraph will

impact your industry, then you'll love the episodes that we have coming up.

Bookmark us. Add us to your podcast app and stay tuned! Hey there and welcome to

Hedera Hashgraph, Gossip About Gossip. I'm Paul Madsen. So it's it's likely you

heard the recent announcement from Google last week about what they had

achieved namely something called quantum supremacy.

A term, I had never heard

before. Bitcoin immediately crashed and then you

know, just as illogically surged on another announcement from China. I'm

happy to welcome my colleague to help make sense of quantum supremacy and and

its potential impact on Hedera. Atul Luykx, welcome Atul, how

are you? Alright, thanks Paul I'm fine thank you.

So you're head of cryptography at Swirlds Hedera? Yes, that's correct.

Awesome, so you're perfectly positioned to help us understand

supremacy and I guess the broader possibilities risks and opportunities of quantum computing to both Hedera and DLTs in general. So before we dig into

that, what's your background? How did you come to Hedera? Yeah, I've been doing

research in cryptography for the past eight years or so. I did a PhD at the

University of live under supervision of pardon.

For those who aren't familiar

with the University of Leuven in Belgium. That's where the AES, advanced encryption

standard algorithm was developed. While I was there, I focused on the

design and analysis of cryptographic algorithms. Trying to prove that

they're secure and I've designed of a handful of my own cryptographic

algorithms. After completing my PhD, I did a post-doc at UC Davis with another

cryptographer named Phil Rogaway. Where I then focused more on protocols

aiming for anonymity. Then continued at Visa Research where I then

looked at cryptography as relevant to the conventional payments infrastructure.

Then I kind of stumbled upon Hedera, you know where basically you get

a much more exciting application of cryptography to a blockchain where cryptography becomes evermore relevant. And over here I've been

continuing my research into cryptography and also kind of working on a consulting

basis with various people throughout the company. Awesome great to hear so how does

one become a cryptographer? Were you a math kid? Yeah, I was basically as I've

always loved math. I've been programming since I was five years old.

Also,

I studied math at my undergrad and then cryptography it's a very

interesting intersection of math and computer science where you can actually

you know be busy with slightly more theoretical math but then stuff that has

a direct impact on the world actually. Which is definitely true of the

possibilities of quantum computing on on encryption in general or security in

general and and DLTs in particular so let's dig into that. Google announced

that they had achieved quantum supremacy. What does that mean?

What is the supremacy? So quantum supremacy is this very basic scientific

question people researching quantum computers have had over the past few

decades. It's basically can a quantum computer actually do something that a

classical computer cannot? So that that seems a very pretentious way of saying

that a quantum computer can do something presumably faster or better than

a conventional supercomputer perhaps? Exactly and so what the Google experiment set

out to do or what they claimed was that here we've designed a quantum computer.

Okay, which can run an algorithm which will only take our computer about you

know three minutes to complete.

Whereas if you were to run it on a classical

computer on a regular computer then it would take 10,000 years.

So this clearly demonstrates that quantum computers can definitely do

stuff that classical computers cannot. That's what the Google paper claimed.

Okay, so I understand IBM disagrees and contended that, that wasn't supremacy? Yes, exactly IBM's response was basically so they

went into this analysis that Google made. Google made a few assumptions about

classical computers in determining how long it would take a classical computer

to solve the problem. Right so this is how Google arrived at their number

10,000 years.

They obviously didn't run a computer for 10,000 years to figure that

out. So IBM then questioned their assumptions and actually pointed out, "hey

if you use these classical computers in this different way then you could

actually solve this problem in two and a half days instead of 10,000 years." Okay,

so it then doesn't become as clear that Google has Illustrated quantum supremacy. Right, where's with Google's estimate is okay blatantly clear ten thousand years

versus three minutes. With IBM you know two and a half days then it doesn't

become, it's not as clear-cut as an answer to the quantum supremacy problem.

Sure, it sounds like a bit of a nit from IBM though right? Because you're still acknowledging that Google did something cool but not that cool. Absolutely, yeah I

mean IBM might be a bit jealous right because they have their own 51 qubit

computer and they didn't come out with this first.

So yeah let's come back to qubits and the significance of 51, I think Google

had 53 so maybe there's competitiveness there? So whether or not it was two and a

half days or 10,000 years, Google's quantum computer was still

able to do something fast or some calculation faster than a traditional

computer.

How? What is the magic in quantum computing that allows it to be

that much faster? When analogy I've heard that, seems intuitive Atul, is

that you know classical computing is like heads or tails right. A given coin

can be heads or tails. But if you flip it while it's in the air it's impossible to

determine whether it's heads or tails. So in a sense, it's both. And quantum computing is acknowledging that superposition of heads and tails together at any one time and leveraging

that that blurriness of the state of that coin.

Yes exactly. Without going into too much detail so what quantum computers are

able to do is they're able to take their state and then go into what's called

quantum superposition. Okay, of that state.

This then allows quantum computers to do

many many different computations in parallel ok while they're in quantum

superposition. Okay so that they can explore many different possibilities of

how the computation would result. So the trick with quantum computers then is

that if you actually want a final result? You're gonna have to collapse

the superposition down to one. Okay and somehow reduce that uncertainty into

certainty and it's basically through this power of being able to do many

different computations at once that you can actually achieve a lot more with

quantum computers. Okay, so I saw an analogy if you think about Google Maps or any of

the map algorithms the mechanism by which they determine the best route from

A to B is effectively try them all and one after another see is this better

than the next one? And a quantum map algorithm would in a sense try them all

at the same time and then filter out the answers that weren't good.

Is that fair?

Roughly yeah yeah. Roughly that's that's awesome. Okay so we achieved roughly. So that's in general why quantum computers can be fast, they

parallel processing to a certain extent with some cleaning up at the end. And

they were able to apply this or Google was able to apply this sort of generic

functionality to solve presumably some obscure math problem that isn't

immediately relevant. But quantum computers are also being perceived as

presenting a real risk to internet authentication, HTTPS, SSL, etc and crypto

like crypto in the 'cool' sense. Cryptocurrencies like hbar and others.

Why? What problem will quantum computers be able to address that isn't feasible

with a traditional computer? So in this respect there's actually two types of

attacks that quantum computers will be able to do once they're around. One of

them which is you know relegated to the far-future let's say. It's where maybe

people are using quantum computers on a daily basis and they're actually running

cryptography on those quantum computers.

If you have a situation like that and

someone wants to attack you? Then they actually have a new avenue they can try

and entangle their computer with your computer and actually recover your keys

much faster. Actually attack your cryptography much faster. But that's

like a really futuristic type of attack where you know we're running desktop

computers which are quantum or something like that okay. But just to give you an

idea, people are even doing research into these types of attacks okay.

Now then there's

the second more serious problem where in the current world we're running

classical computers and we're running cryptography on the classical computers.

Then all of a sudden maybe some large nation-states or who knows some

criminal organization they're able to build a quantum computer and what they

do is they then you know maybe they'll collect our Internet traffic or maybe

they'll have a look at the Bitcoin or Hedera ledgers and take that

information, feed it into their quantum computer and they'll actually be able to

recover the keys in the cryptography using all that communication okay. So

this is a much more serious problem though, one that people are much more

concerned about. There's two very well-known attacks in that situation

that people are most concerned about. One is called Shor's attack and the other is

called Grover's. So what Shor's attack allows you to do is you've got your

quantum computer, you've collected all this internet communication you know for

example TLS communication bring in a new computer you perform Shor's algorithm

that allows you to factor the RSA public keys to be able to

determine the secret keys okay so that you could actually then recover all the

keys using it in a communication.

Then there is Grover's algorithm which allows

you to perform a key search much faster. There's all kinds of cryptographic

algorithms out there. There's already mentioned one which is based on

factorization there are ones which aren't based on those like the advanced

encryption standard what Grover's algorithm allows you to do is to brute

force search keys much faster you know it allows basically a quadratic speed-up

in how fast you can search for keys on quantum computers. Basically it's good to

say long story short if you have a big quantum computer out there yeah you're

gonna be able to factor numbers and a lot of the deployed crypto out there is

broken okay. Thanks basically due to Shor's

algorithm. There's Grover's algorithm which also

severely impacts a lot of different cryptography out there as well but the

effect of that to avoid that one you can just make your keys larger okay because

all that Grover's does is just does a big brute-force search. If you make it

keys larger then it's gonna take a lot longer for them to search for the keys.

Okay so so both those attacks if I understood correctly are because of

quantum computing speed or in a sense just optimization of solving the

difficult problems on which modern crypto non quantum modern crypto relies

right just whether it's factoring a prime or you know brute forcing as you

described and a quantum computer can just go through that search space

quicker.

Is that fair? Yeah exactly. Okay so and

then the the first scenario you described is when it's not modern crypto

RSA elliptic curve or otherwise but some future quantum cryptography

and then then entanglement and that gets that gets even weirder I would think. That gets much weirder yeah the only reason I bring it up is because I've

been starting to see much more research happening about that.

You get much

more devastating attacks okay but again your attacker would somehow to

entangle their computer with yours and who knows it's a kind of a wait

situation. Right so even with respect to the you know the feasibility

of the second attack using quantum against modern crypto. Vitalik Buterin drew the analogy you know we've had fusion we have at nuclear fusion for

years physicists say it's possible but we're still burning coal. How far away is

that scenario that you described? Yeah so let's talk about Shor's algorithm. That's

the factorization algorithm so right now the best computers best quantum

computers that we have are somewhere between 50 and 100 qubits.

The best

estimates to be able to feasibly run Shor's Algorithm is you'd need several

thousand qubits ok and this is assuming those several thousand qubits assuming

that they work perfectly ok. There's this problem with a lot of quantum computers

nowadays is that they there's a lot of error in the computation. We're all used

to classical computers where if you compute a function ok you if you do 1+1

and you do it a million times you always get two.

It's not the case with quanmtum

computers you actually could get errors in your results so you need to rerun

your computations many times. They have all this process called error correction

basically. If your qubits work perfectly you'd need several thousand cubits to

run Shor's algorithm. If you need to use error correction then you'd need a few

million qubits to be able to run Shor's algorithm. So just to put that in

perspective our best estimates is you need a few million qubits to run Shor's

algorithm. We are currently at 50 to 100 qubits. Unless we find a way to

significantly it's very quickly scale the size of our quantum computers it for

the foreseeable future isn't we shouldn't really be concerned about

Shor's algorithm. Is it just engineering? Like that the physics is known and now

it's just a matter of resolving the technical challenges? So that's yeah

so that's what these papers now from Google and IBM so they're

kind of solving these scientific problems the initial problems showing

that hey look this is all feasible and we're able

to scale somewhat.

Now getting to really wide scale quantum computers

there gonna be some significant engineering challenges. Okay well that's

good to hear right! Yeah no absolutely we've got we've got a ways

away. We've got time right. Yeah so Hedera

specifically if the opportunity for a hacker with quantum computing even

acknowledging it's not immediate it's in the future. If the opportunity is to hack

private keys so Hedera uses private keys both for no signing of events, for

clients submitting transactions. Which parts of Hedera's algorithm or

infrastructure cryptographic infrastructure are safe or quantum safe?

So if we very narrowly look at it okay so there's the there's the hashgraph

itself okay there's the history of events that have happened and then the

hashes being built on top of hashes okay and so I say the history is

protected it'll be very difficult for people to go back in time and change

events. But if the hashing function is is a one-way function is that not vulnerable to optimization? You're you're right it's vulnerable to Grover's attack okay

yeah that's why I brought up Grover's attack as well it wouldn't be more

vulnerable but we're using sha 384 okay which is a rather large

hash function so even if you have a huge quantum computer and you want to invert

this hash function it's still going to take a significant amount of time.

Just

because Grover's algorithm doesn't provide as you know such a significant speed

up. Leeman often makes the point that not specifically the hashing function that

we're using 384 but in some sense we're using overkill, throughout the

cryptographic choices that he's made and that gives us a certain future

proof. Yeah that is the case although our signature algorithms are vulnerable

meaning that's the signing functionality for transactions for nodes.

That would all be vulnerable. Like everybody else.

Yeah and that's the point. Right is that we're not the only ones

out there right so there's all of internet banking becomes vulnerable like

you know all apps all enterprise security okay so it's basically it's a

much much larger problem than just for Hedera.

That's why there's also the

significant amount of interest across the industry. So we talked about the

risks that that quantum computing present to DLTs in general or crypto in

general DLT specifically. I've also seen arguments that quantum computing could

provide an opportunity for crypto in generating I think what they called

certified randomness. Randomness is great in DLTs particularly if you're trying

to elect a leader any thoughts there? mm-hmm

Yeah you could potentially use it to as a very good source of randomness okay

and the fact that it's verifiable this is this is very new research right

things Scott Aaronson is also looking into this. I mean the question is would

you be able to practice make use of it in a practical way that's it's hard to

say right now but it definitely looks like, I mean a promising research area

let's put it that way.

Okay fair enough and of course hashgraph we

argue that you don't want a leader in the first place where do you pick them

verifiably randomly or otherwise. So I understand there are quantum resistant

alternative cryptographic algorithms. Is it the case that they're less

efficient particularly in the early days perhaps? Yes yes there's been over the

past two decades a lot of research into designing either either called

Quantum resistance or post quantum cryptographic algorithms and what tends

to happen is is it's one of two things either if we take something like

signature algorithms right and algorithms which sign one thing that

happens is the size of the signature becomes huge okay which then will

significantly increase your communication costs. Even if the

computation is not so much. On the flip side there are signature post quantum

signature algorithms where the signatures aren't so big but then all of

a sudden you need to do a lot of computation to be able to

verify or sign.

Still you know I think factor 10 a hundred times slower

than existing signature algorithms and this is very much still a research area.

But on the flip side if all of a sudden someone were to say oh we've developed a

quantum computer you could in the worst case switch to these slower algorithms

for your most sensitive operations. That's interesting, fascinating. Atul

thank you very much for this I think beforehand my my state was maybe

fifty-fifty on understanding and knowledge and you've moved me to the

right I'd say a superposition of 30 and 70 perhaps. But we'll only find out

once we measure your knowledge. That's true I'll have to quiz you'll have to quiz me and collapse

the the wavefunction. Yes awesome! Atul thanks again. Thank you, Paul.

Thank you for listening to Hedera Hashgraph's Gossip About Gossip. If you liked

the episode please subscribe rate and review and also share and tell your

friends. Or connect with us on social media like Twitter Instagram etc at Hashgraph.

Particularly if you want to leave us feedback on the podcast. We look

forward to hearing from you.