Scott Aaronson – Fundamental Limits of Quantum Computing
Articles,  Blog

Scott Aaronson – Fundamental Limits of Quantum Computing

I’m interested in quantum computing and
in computational complexity theory in general I’m interested in the
limits of quantum computers like the study of what we can’t do with computers
that we don’t have you know and just what are the
fundamental limits on computation and the physical world for example when the idea of quantum
computing was first proposed radio a lot of people thought that maybe
this is a panacea that will just let us do absolutely everything you know for example maybe it will let us
solve these famously hard problems called NP-complete problems by just trying every possibility in
parallel, okay today we actually have a lot of evidence
though not a proof that even quantum computers would
have a hard time with these NP-complete problems okay and so the difficulty of NP-complete problems
may well just be you know a fundamental limit imposed by
the laws of our universe but it would mean if P=NP would
mean would be that anytime you could program your computer to
quickly verify the solution to a problem you know you could also program your
computer to quickly find the solution a computer scientists have
a definition of efficiency that we work with right, what do we mean by a reasonable
amount of time right we’re really interested in the scaling we
could solve all sorts of practical problems you know
like maybe a drug design you know baby like all sorts of optimization problems
that we didn’t know how to solve before I think it would be a net benefit now
yes it would you know break most of the cryptography
that we currently use on the Internet but I see that as you know sort of
a more minor thing by comparison right what it would mean would be that we would
you know have to switch to other methods of encryption such as the one-time pad or quantum key
distribution which would not be affected at all
even P equalled NP


Leave a Reply

Your email address will not be published. Required fields are marked *