Okay. So, now let's try to understand a
little more what, what quantum algorithms
and quantum circuits look like. Okay. So
what's our basic model of, of computing?
Well, our basic model looks like this now.
So we have N qubits, here which are
initially, let's say in this state zero.
These we think of as the inputs to the
circuit. And what I draw here these, these
lines, these are wires and each wire
carries a qubit of information. Okay? So,
so, let's think of each of these wires as
our electron in the hydrogen atom. You
know, whether it's in the ground or
excited state, or in a superposition of
the two. And of course, as we go along,
these wires will get entangled. The qubits
get entangled, right? Okay. Now, now what
do we actually do? Well, a quantum circuit
is a sequence of gates. So it consists of
a sequence of gates so you might have,
have some kind of quantum gate that acts
on these two qubits, and outputs two
qubits. They could be also single qubit
gates. So, so this might be the Hadamard,
this might be z. Okay. Whatever, right? So
there are, there are some sort of gates.
This might be a controlled naught, we
don't know. Okay. But, but a quantum
circuit is, is just a sequence of gates.
Maybe this one just goes right through.
Perhaps there's another gate here, etc.
So, so quantum circuit is consists of
these n wires that just go through left to
right all the way to the end and then
maybe there are other gates back here.
This whole thing is called a quantum
circuit. These are the outputs of the, of
the quantum circuit. And now what we might
want to do is, we might want to measure
these, these bits. We, we either you know,
it could be that we only measure some of
these, these qubits. So, so we, we select,
some of these qubits, maybe, maybe these
ones and we put in a measuring apparatus.
And then, as output we get a classical
string. Okay? So that's, that's a quantum
circuit. Now, there's a question. What
kind of gates should be allowed in this
quantum circuit? Well so, let's look at,
look at the corresponding question on the
classical side. So if you have a classical
circuit, what kind of gates should one
allow? Well, there are many kinds of gates
one can, one can come up with nands, ors,
nor, etc., etc. But, but there's, there's
a you know, there's this very simple but
very, very beautiful fact about classical
circuits which is that, you don't have to
allow for, for a very rich set of gates.
In fact, all you need is a Nand gate. A
nand gate takes as input two, two bits and
outputs one bit and it's the naught of the
and, right? So, so the output is, is one
unless x equal to y, equal to one, in
which case the output is zero. So, so the
claim is that no matter how complicated
the circuit you are trying to create, you
can always assume that your building
blocks are. You have only one kind of
building block which is a Nand gate. Okay.
So, so the way one, one says this is by
you know, expresses this fact is by saying
that the Nand gate is universal for
classical computation. So now we can ask,
is something like this true also for
quantum computing? Is there a universal
family of quantum gates? And it turns out
that there is, so there are various
families of quantum gates that are, that
are universal but for our purposes, the,
the gates that we saw CNOT, Hadamard, X, Z
together with the pi by eight rotation. So
if you have, if you have just these five
types of gates, then they claim that you
can implement any quantum circuit that you
want. Okay. Let me say just a couple of
more words about it to make this a little
more precise for those of you who are
interested. So what does it mean that this
gate set is universal? So, what we'd like
it to mean is that, if you have any, let's
say that, that somebody came along and
they said, you know, there's this
particular unitary transformation, you
know, there's this particular gate that I
have in mind you know, I'm going to, it,
it, it's really quite magical. This gate
has the property that it will simplify
every quantum computation. You know, you
only have t o implement this gate, and
then you know, everything is going to be
so much faster you won't even believe it.
Okay. And what does this gate look like?
Maybe, maybe it takes as input four
qubits, outputs four cubits and implements
some unitary u on these four qubits. So
it's, it's represented by a sixteen by
sixteen matrix, complex matrix. Okay so,
so now the fact that these five gates are
universal allows us to say, you know, it
cannot be the case that your, your, your,
your gate, your favorite gate u is, could
be that powerful because it can't be more
powerful than these because what we show
you is how to implement u using these five
gates. And moreover, to implement u, we'll
do it pretty efficiently. Okay, now there
is one problem we cannot of course
implement u with, with perfect precision
because, because u after all is, is, is
represented by a sixteen by sixteen
complex matrix and you need, you need
infinitely many digits to specify this to
perfect precision. So, instead what we
will do is, for any given epsilon, we'll
implement an approximation use of epsilon,
which epsilon close to you. And it turns
out that if the, if u is given by d by d
matrix and you want to be epsilon close to
the answer, the, the number of these
elementary gates that we need scales
roughly like well it you know, it has to
scale like you know, it might be some
polynomial in d, lets say order d squared
times in polynomial in one over epsilon,
log one over epsilon. So, certainly log
cubed works and maybe even well, well,
let's, let's say log cubed just to be on
the safe side. So the dependence on d and
epsilon is mild. Now a claim that, that
something like this dependence on d, d
squared is really necessary because,
because just by counting argument there
are lots of, lots of unitary
transformations which are, which are d by
d and, and these are only five gates, so
how can you express all of them unless you
pay such an, such an overhead. So, okay.
So what's, what's the upshot of all these?
The upshot of all these is what we are
claiming is, we are going to be
implementing this, this circuit use of
epsilon where if you look inside, what it
consists of is, CNOT gates and Hadamards,
and, and X gates, and Z gates, and so on.
And moreover, this, this circuit use of
epsilon behaves almost the same as you in
the sense that if you look at these two
transformations u and u epsilon, they are
epsilon close in operator norm. So u minus
u epsilon in operator norm is at most
epsilon, okay? Which means that, this is
another way of saying that if you apply
both of these, these, these circuits to,
to the same quantum state, the state that
results in the two cases, these two states
are going to be epsilon close to each
other in Euclidian norm.