Okay so - Hi, I'm Scott Aaronson. I'm a computer science professor at the

University of Texas at Austin and my main interest is the capabilities and

limits of quantum computers, and more broadly what computer science and

physics have to tell each other. And I got interested in it I guess because it

was hard not to be - because you know as a teenager it just seemed clear to me that

the universe is a giant video game and it just obeys certain rules, and so if I

really wanted to understand the universe you know maybe I could ignore the

details of physics and just think about computation. But then with the birth of

quantum computing and the dramatic discoveries in the mid-1990s

(like Shor's algorithm for factoring huge numbers) it became clear that physics

actually changes the basic rules of computation. So that was something that I

felt like I had to understand and 20 years later we're still trying to

understand it and we may also be able to build some devices that can outperform

classical computers you know namely quantum computers and use them to do

some interesting things. But to me that's that's really just icing on the cake

really I just want to understand how things fit together. Well to tell you the

truth when I first heard about quantum computing (I think from reading some

popular article in the mid 90s about a Shor's algorithm which had only recently

been discovered) you know my first reaction was this sounds like obvious

hogwash - you know this sounds like some physicists who just do not understand

the first thing about computation - and they're just you know inventing some

physics proposal that sounds like it just tries every possible solution in

parallel. But you know none of these things are going to scale right and in

computer science you know there's been decades of experience

of that; of people saying well why don't you build a computer you know using a

bunch of mirrors, or using soap bubbles, or using a folding proteins right.

And there's all kinds of ideas that on paper look like they could you know evaluate

an exponential number of solutions at only a linear amount of time, but they're

always kind of idealizing something right so it's always when you examine

them carefully enough you find that the amount of energy or you know scales

explose up on you exponentially, or the precision with which you would need to

measure you know becomes exponentially precise, or something becomes totally

unrealistic - and I thought the same must be true of quantum computing. But you

know in order to be sure I had to read something about it so I while I was

working over a summer at Bell Labs doing work that had nothing to do with quantum

computing, well my boss was nice enough to let me spend some time learning about

reading up on the basics of quantum computing - and that was really a

revelation for me because I accepted [that] you know quantum mechanics is this real

thing. It is a thing of comparable enormity to the you know the print basic

principles of computation you can say you know the principles of Turing - and

you know it is it is exactly the kind of thing that could modify some of those

principles. But the biggest surprise of all I think was that I despite not being

a physicist you know not not you know having any skill that partial

differential equations or the others tools of the physicists that I could

actually understand something about quantum mechanics so I like to say that

quantum mechanics is much much simpler than most people imagined it could be

after you take the physics out of it - it's a certain generalization of the

rules of probability. And ultimately you know to learn the basic rules of how a

quantum computer would mark and start thinking about you know what they would

be good for - quantum algorithms and things like that -

it's enough to be conversant with vectors and matrices right? So you need

to know a little bit of math but but not that much right? You need to be able to

know linear algebra okay and that's about it. And I feel like this is a kind

of a secret that gets buried in almost all the popular articles; they make it

sound like quantum mechanics is just this endless profusion of

counterintuitive things right? That it's: particles can be in two places at once,

and a cat can be both dead and alive until you look at it you know, and then

you know why is that not just a fancy way of saying well either the cat's

alive or dead and you don't know which one until you look well they they never

quite explained that part right, and particles can have spooky action at a

distance and affect each other you know instantaneously, and particles can tunnel

through walls! You know it all sounds like hopelessly obscure and like you

know there's no hope for anyone who's not a PhD in physics to understand any

of it. But the truth of the matter is you know there's this one counterintuitive

hump that you have to get over which is the certain change to or generalization

of the rules of probability - and once you've gotten that then all the other

things are just different ways of talking about or different

manifestations of that one change right? And you know a quantum computer in

particular is just a computer that tries to take advantage of this one change to

the rules of probability that the physicists discovered in the 1920s was

needed to account for our world. And so that was really a revelation for me that

well you know even you know you're computer scientists are math people

people who are not physicists can actually learn this and start

contributing to it - yeah! [Adam]: So it's interesting like often and when you

try to pursue an idea, the practical gets in the way. Have you noticed that some people try and get

to the ideal without actually considering the practical - and you know

they feel like enemies - is it like that you should be letting the ideal be the

enemy of the practical? [Scott]: Well I think that you know there's

- from the very beginning it was clear that there is a theoretical

branch of quantum computing which is where you just assume you have as many

of these quantum bits (qubits) as you could possibly need, and they're perfect

they stay perfectly isolated from their environment, and you can do you know

whatever local operations on them you might like, and then you know you just

study well how many operations would you need to factor a number? Or you know

solve some other problem of practical importance? And you know and the

theoretical branch is really you know the branch where I started out in this

field and where I've mostly been ever since you know. And then there's the

practical branch which asks well what will it take to actually build a device

that instantiates this theory right - where we have to have qubits you know

that are actually the energy levels of an electron, or the spin States of an

atomic nucleus, or are otherwise somehow you know instantiated in the physical

world. And you know they will be noisy, they will be interacting with their

environment - we will have to take heroic efforts to keep them sufficiently

isolated from their environments you know - which is needed in order to

maintain their superposition state right? How do we do that? Well we're gonna need

some kind of fancy error correcting codes to do that right, and then you know

there are there are theoretical questions there as well but how do you

design those our correcting codes right? But there's also practical questions: how

do you engineer a system you know where the error rates are low enough that

these codes can even be used at all; that they won't you know that if you try to

apply them you won't simply be creating even more error than you're fixing. So

you know and what should be the physical basis for qubits? Should it be

superconducting coils? Should it be ions trapped in a magnetic field?

Should it be photons? Should it be some new topological

state of matter? Actually all four of those proposals and many others are all

being pursued right now! So I would say that until fairly until quite

recently in the field, like five years ago or so, the theoretical and the

practical branches we're pretty disjoint from each other right;

they were never enemies so to speak. I mean we might poke fun at each other you

know sometimes but you know I mean that you know we were we were never enemies I

mean you know the the field always sort of you know rose or fell you know as a

whole and we all knew that. But we just didn't have a whole lot to

scientifically to say to each other because you know the experimentalists

we're just trying to get one or two qubits to work well right, and they

couldn't even do that that much, and we theorists we're

thinking about well suppose you've got a billion cubits, or you know some

arbitrary number, what could you do? And even you know what would still be hard

to do even then right? A lot of my work was has actually been about the

limitations of quantum computers, but you know I also like to say the study of

what you can't do even with computers that you don't have. And only

recently the experimentalists have finally gotten the qubits to work pretty

well in isolation so that now it finally makes sense to start to scale things up -

not yet to a million qubits but maybe 50 qubits, maybe to 60, maybe to a

hundred. This as it happens is what Google and IBM and Intel and a bunch of

startup companies are trying to do right now. And some of them are hoping to have

devices within the next year or two, that you know might or might not do anything

useful but if all goes well we hope will at least be able to do something

interesting - in the sense of something that would be challenging for a

classical computer to simulate, and that at least proves the point that we can

you know do something this way that is you know beyond what classical computers

can do. And so as a result you know the most

nitty-gritty experimentalists are now actually talking to us theorists because

now they need to know not just as a matter of intellectual curiosity but as

a fairly pressing practical matter, well you know once we get 50 or 100 cubits

working what do we do with them? What do we do with them first of all that you

know is hard to simulate classically how sure are you that there's no fast

classical method to do the same thing, you know how do we verify that we've

really done it you know, and is it useful for anything right? And you know and

ideally they would like us to come up with proposals that actually fit the

constraints of the hardware that they're building right, where you could say you

know eventually none of this should matter right, eventually a quantum

programmer should be able to pay as little attention to the hardware as a

classical programmer has to worry about the details of the transistors today

right. But in the near future when we only have 50 or 100 cubits you know each

and every you know you're gonna have to make the maximum use of each and every

qubit that you've got, and the actual details of the hardware are going to

matter, and the result is that even you know we theorists have had to learn

about these details you know in a way that we didn't before. And so there's

been a sort of coming together of the theory and practical branches of the

field just in the last few years that to me has been pretty exciting. [Adam]: So you think we will have something equivalent to functional programming for quantum computing in the near future? [Scott]: Well there

actually has been a fair amount of work on the design of quantum programming

languages. There's actually a bunch of them out there now that you can download

and try out if you'd like there's one called Quipper, there's another one

called a Q# from Microsoft, there's you know and there are

several others. You know of course we don't yet have very good hardware to run

the programs on yet, mostly you can just run them in

classical simulation, which you know naturally only works well for up to

about 30 or 40 cubits, and then it becomes too slow. But if

you would like to get some experience with quantum programming you can try

these things out today, and many of them do try to provide higher level

functionalities, so that you're not just doing the quantum analog of

assembly language programming right, but you can think in higher-level modules, or

you can program functionally. I would say that in quantum algorithms you know

we're you know I mean we're you know mostly we've just been doing theory and

we haven't been implementing anything, but we have had to learn to think that

way right. If we had to think in terms of each individual qubit

each individual operation on one or two qubits well we would never get very far

right? And so we have to think in higher-level terms like there are

certain modules that we know can be done - like one of them is called the Quantum

Fourier Transform and that's actually the heart of Shor's famous algorithm for

factoring numbers (it has other applications as well). Another one is

called Amplitude Amplification that's the heart of Grover's famous algorithm

for searching long long lists of numbers in about the square root of the number

of steps that you would need classically, and that's also like a quantum algorithm

design primitive that we can just kind of plug in as a black box and it has

many applications. So we do think in these higher level terms, but you know

there's a different set of higher level abstractions than there would be for

classical computing - and so you have to you know you have to learn those. But the

basic idea of decomposing a complicated problem by breaking it down into its sub

components that's exactly the same in quantum computing as it is in classical

computing. [Adam]: Are you optimistic with regards to quantum computing in the medium to short term?

[Scott]: You're asking what am i optimistic about - so I am I mean like I feel like the the field

has made amazing progress: both on theory side and on the experimental side.

We're not there yet, but we know a lot more than we did a

decade ago right? Some of the what were my favorite open

problems as a theorist you know a decade ago have now been resolved - some of them

within the last year - actually and the you know the hardware you know the

qubits are not yet good enough to build a scalable quantum computer right - in

that sense you know the skeptics can you know clearly legitimately say well you

know well you know we're not there yet - well you know no duh we're not - okay

but: if you look at the coherence times of the qubits you look at what you can

do with them, and you compare that to where they were 10 years ago or 20 years

ago - you know there's been orders of magnitude type of progress. Right, so the

analogy that I like to make: you know Charles Babbage laid down the basic

principles of classical computing in the 1820s right? I mean not as not with as

much mathematical rigor as Turing would do later, but you know the basic ideas

were there. You know he had what today we would call a design for a universal

computer. So now imagine someone then saying 'well you know so when is this

analytical engine gonna get built? you know will it be in the 1830s or will it

take all the way until the 1840s?' Right well you know in this case you know it

took more than a hundred years for a technology to be invented - namely the

transistor - that really you know fully realized Babbage's vision. Right I mean

the vacuum tube came along earlier, and you could say partially realized that

but you know it was just not reliable enough to really be

scalable in the way that the transistor was, And we are now in

the (optimistically we're in the) very very early vacuum tube era of

quantum computing ok? We don't yet have the quantum computing analog of the

transistor as people don't even agree about which technology is the right one

to scale up yet. Is it superconducting? Is it trapped ion?Iis it photonics? is it a

topological matter? Right so you know so they're pursuing all these different

approaches in parallel. You know the partisans of each approach

have what sounds like compelling arguments why none of the other

approaches could possibly scale. I hope I hope that they're not all correct uh-huh

but you know but people are still just you know they've only just recently

gotten to the stage where one or two qubits work well in isolation, and where

it makes sense to try to scale up to 50 or 100 of them and see if you can get

them working well together you know at that kind of scale. And so so I think the

the big thing to watch for in the next five to ten years is what's been saddled

with the somewhat unfortunate name of Quantum Supremacy (and you know this was

coined before Trump I hasten to say). But so this is just a term to refer to

you know doing something with a quantum computer it's not necessarily useful but

that at least is classically hard. So you know that as I was saying earlier proves

the point that you can do something that would take a lot longer to simulate it

with a classical computer. And you know this is the thing that Google and some

others are going to take their best shot at within the next couple of years so

you know and and what puts that in the realm of possibility is that

you know just a mere 50 or 100 cubits you know if they work well enough should

already be enough to get us this. Right and you know you you in principle you

know you may be able to do this without needing error correction - once you need

error correction then that enormously multiplies the resources that you need

to do even the simplest what's called Fault-Tolerant Computing

might take many thousands of physical qubits, okay, even though you know

everyone agrees that ultimately if you want to scale to you know the realize

the true promise of quantum computing, or let's say to threaten our existing

methods of cryptography - then you're going to need this fault tolerance. But

that I expect we're not gonna see in the next five to ten years. If we do see

it I mean that will be a huge shock I mean but you know - as big a shock as it

would be if you told someone in 1939 that you know there was going to be a

nuclear weapon and in six years okay. You know in that case there was a world war

that sort of accelerated the timeline you could say from what it would

otherwise be you know. In this case I why I hope there won't be a world war that

accelerates this timeline. But you know my guess would

be that you know if all goes well then quantum supremacy might be achievable

within the next decade, and I hope that after that we could start to see some

initial applications of quantum computing which will probably be some

very very specialized ones; some things that we can already get with you know a

hundred or so non-error-corrected qubits okay. And you know by necessity these are

going to be very special things - they might mostly be physics simulations or

you know simulations of some simple chemistry problems. I actually

have a proposed application for near-term quantum computers which is to

generate cryptographically secure random numbers - those random numbers that you

could prove to a skeptic really were generated randomly - turns out that even

like a 50 or 60 qubit quantum computer should already be enough to give us that.

But you know true scalable quantum computing the

kind that could threaten cryptography and that could also speed up you know

optimization problems and things like that - that will probably require our

correction - and you know I could be pleasantly surprised you know. I'm not

optimistic about that part becoming real on the next five to ten years, but you

know I'm I you know since every everyone likes an optimist I guess I'll you know

I try to be optimistic that well you know we will you know take big steps in

that direction and maybe even get there within my lifetime.