Okay, so in this video we will talk about
Quantum Complexity Theory.
Now, Quantum Complexity Theory is a, is a
vast subject and you shouldn't expect to
learn a lot about it in a, in a 15-,
20-minute video.
So, I think of this video as a taste of
quantum complexity theory.
It'll try to give you a picture of what,
you know, what the basic quantum
complexity class s-, I-, classes, class
is, and how it relates to classical
complexity classes.
Now, of necessity, this is, you know, this
is, not a lecture that I expect you to
understand in detail, so, just, just think
of this as something that'll give you,
that will whet your appetite, give you a
picture of what Quantum Complexity theory
is all about, and, and if you, if you
don't follow it don't worry too much about
it.
Okay.
So, let's start by, by a, a brief
introduction to classical complexity
theory.
So, let's first talk about what a
computation problem is.
So a computational problem is, is
something like, make, you know, you, you,
you, you specified some input-output
relationship.
And you want to try to achieve this
input-out relationship via a suitable
algorithm.
Okay.
So, here, here are examples.
So you might want to ma, multiply two
matrices, M and N, which I've given to
you.
You might want to test whether given
input, given number is a prime.
You might want to solve the related
problem of actually producing a prime
factorization of a given input number n.
Or you might want to test whether given
boolean formula f is satisfiable by
actually producing a satisfying assignment
x.
Okay, now we say that.
A given computational problem is solvable
in polynomial time.
If there's a, if there's a algorithm,
which on inputs of size n, holds in time,
or n to the k for some constant k.
Meaning in time, it holds in time some
bounded by some polynomial n, and it
outputs the correct answer.
Now, in this course so far, we've been
talking about circuits.
So, the corresponding statement for
circuits would be that on inputs of size
N, you know, you have a circuit C, which
takes inputs of size N and outputs C of X.
Which is the correct answer to this
problem.
And the running time, instead of running
time.
We'll talk about the size of C.
So we'll say you know, saying that there's
a polynomial timed algorithm.
Corresponds to saying that there's a
family of circuits C sub N, one for each
length N such that on inputs of, of, of
length N, C sub N outputs the correct
answer.
And moreover the size of C sub N, C sub N,
the number of gates in C sub N, is bound
by some polynomial in N.
There's also a, you know, some sort of
uniformity condition which says that the
circuit C can be, C sub N can be
efficiently computed given N as input.
But that's, we, we won't get into the, the
details of these definitions.
Okay, so.
So now, the class P or polomial time, is a
class of all computational problems, with
polomial time algorithms.
So, in our, in our, in our example, Matrix
multiplication as polynomial time,
solvable.
It's in the class P.
But we don't think factoring is, and we
certainly don't think satisfiability is.
What about primality testing?
Well primality testing is sort of.
It's, it's very, it comes very close to
being in the class P.
What it isn't is the class VPP, which
corresponds to polynomial time on a, for a
randomized algorithm.
See here's what we mean by that, what we
mean is that there's some circuit which
takes as input X, but it also takes as
input some random bits R.
And now, what we, what we want is that c
of xr, is the correct answer, with high
probability.
So we might say, well, it's correct, say,
with probability, at least, three
quarters.
But now if we want to boost the chance of
success, all we have to do is run the, run
the circuit many times with, independent
random bits, and take the majority answer.
And we can boost the success probability
from three quarters to, something
arbitrarily close to one.
Okay.
So, our mantra is that polynomial time is
good, exponential time is bad.
Why is exponential time bad?
Well, we've seen this already.
Exponential time grows so quickly if the
exponential function grows so quickly,
that already for even small values of n,
exponential in n is larger than, number of
particles in the universe, or age of the
universe.
And that, that cannot be a good time
bound.
Okay.
So that's our basic distinction between
polynomial and exponential.
Now, there's a, there's a question that we
beg, which is, how did we decide our model
of computation?
Why was it circuits or Turing machines or
algorithms?
How did we decide, what, you know, what
model we are going to run our algorithms
on?
And this is a very important
consideration.
This, the you know, this is what the,
foundations of complexity theory are built
on, and it's called the extended Church
Turing thesis.
What this thesis asserts is that it
doesn't much matter what your model of
computation is.
Your running times will work out to being.
Essentially the same to within polynomial
factors.
So, if you're talking about polynomial
time competition.
It's robust against changes in models, the
model of computation.
So this another reason we like polynomial
time.
Because it's a robust notion of, running
time.
So what the extended Church-Turing thesis
actually says is that, any reasonable
model of computation can be simulated on a
probabilistic Turing machine with, at
most, polynomial simulation overhead.
What does this mean?
It means, for example, that if you have,
if you have a running time of T steps on
some model of computation that you've,
that you invented, which you think is
reasonable, reasonable meaning you can
implement it in principle.
Physically implementable in principle,
then you can also run this algorithm.
Say, in order, t squared steps, or some
polynomial and t steps on a Turing
machine, on the simplest model of them
all.
Now, where does this Extended
Church-Turing thesis come from?
What, how do you interpret it?
Well, one interpretation for this Extended
Church-Turing Thesis was.
That a touring machine describes the set
of all functions, that are computable by a
mathematician.
So you think of the touring tape, as being
an infinite supply of paper..
And you think of the finite state control
as your mathematician, and the read-write
head as a pencil.
So you, so you have a mathematician armed
with infinite supply of pencils, infinite
supply of paper.
And you want to know, what can this
mathematician compute?
What are the functions?
What are the problems that this
mathematician can solve in a reasonable
amount of time?
Well, that's what polynomial time
describes in this one interpretation.
The second interpretation of, of this
thesis is that the class polynomial time
represents what can be physically computed
in this, in this universe in a reasonable
amount of time.
And the rationale for this, is that Turing
machines can simulate cellular automata
with, with polynomial overhead.
Right there polynomially equivalent to
cellular automata.
And some of the arguments is that cellular
automata represents everything that you
can compute in the, in the, in the
classical universe.
Okay.
Remember we are talking about classical
complexity theory so far.
So why is it, that, that a cellular
automaton.
By the way this is, this is a cellular
automaton that's, that's simulating what's
called The Game of Life.
Like Conway's Game of Life.
Okay, so, so what is it about a cellular
automaton that it makes it such a
convincing model for anything that can be
computed in the, in the classical
universe?
So, so, in a cellular automaton, each cell
looks at its, its small neighborhood, the
cells around it and its new state, you
know.
It's in one of a finite number of states.
And its new state is a function of its,
you know?
The states of all the cells in a small
neigh-, you know, its, its neighbors.
Okay.
Now, this is directly analogous to
something in, in physics.
It says that, so classical physics is
described by local differential equations.
Which means that, what you're saying is
that, you know?
If you want to know how some quantity
changes over time, electricity, magnetism,
whatever.
Then, you, wh-, what you, what you have to
say is that, you know?
The, the value of that, that physical
quantity at, at a certain point.
At, you know, at t plus delta t is
determined by, sort of, you know, that,
that point just looks at an infinitesimal
neighborhood around it.
And, based on the value at time t in this
infinitesimal neighborhood, you can
determine the value of, at, at this
particular point at time t plus delta t.
Okay, but now so you can see that, that
cellular automaton, These are, these are
discreet discretizations of local
differential equations.
And you can argue that if you want to
compute.
Then your, you, your computer has to be
fault tolerant.
That, you know, it cannot be that, that
you assume infinite precision in your
model.
And so you have to discretize it.
You have to have a digital abstraction.
And once you take your local differential
equations and you, and you subject them to
a digital abstraction you, you get
cellular automata.
So that's the argument that polynomial
time is the limit of what you can compute
in the physical world classically.
And so.
Quantum computation is the only model of
computation that violates this extended
Church-Turing thesis.
It's the only reasonable, model of
computation.
Which cannot be simulated in polynomial
time on, on a Turing machine, on your
classical Turing machine.
So what's our evidence for this?
Well, we have two kinds of evidence that
it violates the extended Church-Turing
thesis.
One is a black box sep-, separations.
So we already saw these examples of, of
algorithms.
You know, such as the recursive Fourier
sampling problem or Simon's problem, where
we said there is no polynomial time.
You, you know, you, you can solve these
problems in polynomial time on a quantum
Turing machine or with a quantum circuit,
but there is no corresponding polynomial
time solution to these problems.
Classically, is in the classical
algorithm.
We also saw that, that there are problems
that we strongly believe to be difficult
classically.
In fact, we believe that are, we believe
this so strongly that we base cryptography
on it.
These are problems like factoring and
discrete logarithms.
And for these problems we know that there
is a polynomial time quantum algorithm but
we strongly believe that it takes
exponential time to.
To solve them classically or at least.
All the algorithms that we know of so far
take exponential time.
So these are the two kinds of evidence
that we have that quantum computers
violate this extended Church-Turing
thesis.
Now, you could ask, why are we messing
around with this kind of evidence?
Why don't we just flat out prove that
quantum computers violate this extended
Church-Turing thesis?
Well the answer has to do with, with this.
Okay, let's, let's first define this class
BQB, Bounded Error Probabilistic Bonham
Milton.
Bounded Error, Sorry.
Quantum polynomial time.
Right it's, it's the class of
computational problems which have
polynomial time quantum algorithms that
I'll put the correct answer with high
probability.
So for example factoring belongs to BQP.
Now Okay, so.
The, you, you can show this inclusion
that, that P, polynomial time is in BPP,
probabilistic polynomial time, which is
contained in BQP.
So BQP is, is this class that we are
interested in showing is so much larger
than P or BPP.
But then you can also show further
containments.
You can also show that this is contained
in something called P to the sharp P,
which is contained in P space.
P space.
Is a class of problems that you can solve
using not a polynomial amount of time but
polynomial amount of space.
So you can, you can, you know, if you have
only a polynomial, polynomial amount of
memory in your algorithm, but you can keep
using this memory, well then that's p
space.
Now the interesting here is that.
P versus P space whether or not P equal to
P space this is one of the major open
questions in complexity theory.
So, this is an open question in complexity
theory.
We strongly believe that P is not equal to
P space.
But we don't know for sure.
We don't know how to prove it.
So now you can see, if we could show that
BQP is strictly larger than P and BPP.
Then we'd have shown that P is not equal
to P space.
Thus, solving this major open question.
And this is why we have to deal with this
sort of evidence, that BQP really, that
quantum polynomial time is larger.
That quantum computers violate this
[inaudible] thesis.
And's what's B, what's sharp B?
Well sharp B.
This is so called counting clause.
It's a complexity class having to do with
counting.
So let's say you have a, you have a
circuit.
See here we have some function'f, ' which
maps'x' in'y' to'f' of'xy'.
Okay.
Now we can, we can define accounting
problem associated with this.
We can say, the count of X, is the sum
over all Y.
Of F of XY.
You see so.
So, what, what, what this is saying is, if
you were given x and y, you could of
course compute f of xy quickly because f
is implemented by a polynomial size
circuit.
But now what you want to do is you want to
sum up f of xy over exponentially many
different y's and this is now much more
complicated problem.
It turns out that if you could solve this
problem than you can actu, actually solve,
you know, then you can, then you can
simulate any quantum computation that you
want.
And the way you reduce a quantum
computation to this sort of counting
problem is.
It's reminiscent of Feynman's path
integrals.
So, in fact, in some sense, what Feynman
came up with was a way of showing that BQP
is in P to the sharp P.
It's actually not a very difficult proof,
it's, it's a simple proof.
But I really don't want to get into this
now.
It's, you know, we don't really have the
time.
And, or, or, you know, it's, it's, it
wouldn't be appropriate.
We couldn't really do it justice in this,
in this [inaudible] setting.
Okay, so now.
We could try to understand, you know, our
complexity classes A little bit better.
So, here we have P of polynomial time.
And then remember there was this class NP.
It contained many of the problems that
we'd like to solve.
Like satisfiability.
Now if you take a problem which is in MP
like satisfiability.
You could also look at the compliment of
it.
And you get, get this class, co NP, which
contains problems like, not satisfiable.
Is this formula not satisfiable?
And then, it turns out there's a, that
there's a high, you know, so, so, there's
an, there's an infinite hierarchy of such
classes.
Mp, Co-MP, what's called.
Sigma 2P, etc.
Pi to P, etc.
And these, You know this, this entire
class of problems.
Sort of forms what's called the polynomial
hierarchy.
And all this, you know, this entire
structure sits in inside.
P to the sharp P.
And which finally sits inside P space.
So now you could ask.
Well, you know, we've already said that we
believe that BQP, the, that you cannot
solve the NP-complete problems.
So the problems right here, we, we cannot
solve them in polynomial time.
I-, so in, in polynomial time on so, so
this is, let's say, the NP-complete
problems.
And, we believe that this cannot be solved
in polynomial time on a quantum computer.
Right?
So.
What does this class BQP look like in this
picture?
So, is it contained inside of MP?
Well, we already have a hint.
What, the, the, the hint that we have is
that this, this, this problem recursive
Fourier sampling, we can show that in the,
in the black-box model, this does not
belong to MA, Merlin-Arthur, which is the
probabilistic generalization of NP.
So it lies outside of this NP but, not
only does it lie outside of NP, but it
even lies outside the probabilistic
generalization of NP.
We can show this, you know, like, like all
of these results, we can show this
unconditionally.
This is in a black-box model.
Or, also called an oracle model or
setting.
Okay.
So, so now, what should we think about,
about, BQP?
So, the idea is that BQP somehow, it
doesn't contain the MP complete problems.
It, instead, is some sort of complexity
clause which, which heads out like this.
And it contains recursive Fourier
sampling.
And how far it heads out into this whole
thing we, we don't quite, you know, we
don't yet understand.
So we could ask, how, how far outside of
MP are these problems that BQP might
contain?
And could it be that in fact it even
extends outside of the polynomial
hierarchy and contains some problems out
here.
And the conjecture, which is very long
standing.
It goes back almost twenty years.
Says that in fact the foray sampling
problem should be one such example, which
is not in the [inaudible] hierarchy.
This has proved to be remarkably, to, you
know to, to resolve.
And a few years ago, Scott Erinson came up
with a, with a simplified problem which,
which, Which he conjected is also not in
the polomial hierarchy, but with which can
be solved, in polomial time on a quantum
computer.
And this is called, the Fourier checking
problem.
So here's a, here's a, here's a, a pointer
to the, to a paper that discusses this
problem.
But it's actually a very simple problem.
It's, it's very simply stated and very
elegant.
So, let's say BMW are random unit vectors
in real n-dimensional vectors where, where
capital n is two to the little n.
So it's, these are exponential dimensional
real vectors.
And now given such a real vector, you can,
you can.
Think of it as defining.
A boulion function.
Okay.
So its a, its a function which, you know,
for.
So, so in other words, you have this, you
have this exponential dimensional vector
where, each entry is a real number.
So this, this, this real number, let's say
is R sub K.
And now you could think of this as
defining a bullion function for you, where
maps K to the, sign of K.
Right?
So it, it, it maps an N bit number to +one
or -one.
Okay, so, so now, since you have two such,
such, such vectors that define two
different functions.
F and G, which are bullion functions on
little N bits.
So what we want to do is distinguish.
So we are given two, two, two such
functions.
Either we are given F equal to sine of V,
and G equal to sine of W.
You know, the, these, the sine functions
defined by these two random vectors.
Or, we are given F is equal to sine of V.
And g equal to sine of h Dove..
So, so, instead of wv, now you use the
same vector v.
Once as it is, and once having applied the
Hadamard transform to it.
And we want to be able to distinguish
these two situations from each other.
And the, the, the point is that there's a
very simple quantum algorithm that will
distinguish this situ-, the first
situation from the second one.
But the conjecture is.
That you cannot do this distinction
anywhere in the program with hierarchy.
Okay.
So, I should mention that this is one of
the central open questions in quantum
complexity theory.
Understanding the power of BQP, Quantum
Polynomial Time.
And this is completely wide open as, as we
speak.