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.