Tip:
Highlight text to annotate it
X
Hello, my name's Dominic Berry and I'm a Future Fellow at Macquarie University doing
research into quantum algorithms among other things.
In this video I'll give a simple introduction to quantum computing and quantum algorithms.
This talk is based on some lectures I gave at the Calgary summer school, which was earlier this year in 2013,
except this is intended to be an easier introduction to the subject.
If you'd like the more complicated version, that's available at my website, dominicberry.org.
So if you go there and click on presentations, you'll find the presentations that I gave at the Calgary summer school.
Now before I go into explaining quantum computers,
I'll explain a bit about the usual sort of computers, which we now call classical computers.
So first is a really classical computer.
This is what's known as the Antikythera mechanism, which is from Greece and around 100 BC.
Of course this isn't the original, it's a modern reconstruction.
It's what's known as an analog computer.
It doesn't use a digital representation of numbers, it just uses the positions of gears.
The next is Pascal's calculator, from about 1645.
This can actually do arithmetic with decimal numbers, much like a modern calculator - that is, it is a digital one.
The next one is Babbage's difference engine. The idea of the difference engine was not just to do arithmetic,
but to calculate tables of logarithms, which was important to people in the 19th century.
It was designed by Charles Babbage in the 19th century from about 1823 to 1849, but never actually built.
What's shown here is a modern construction.
The last one is the current fastest supercomputer as of 2013, which is in China.
It does 33 petaflops, which is 33 thousand trillion operations per second.
These computers span over 2000 years, and have an enormous range of capabilities,
but in one sense they are all the same, in that they're based on the laws of classical physics.
When it comes to quantum systems, the situation is far more difficult.
If we want to know how systems work at the atomic scale,
to properly understand atoms and molecules, we need to be able to simulate quantum mechanics.
As Dirac pointed out as long ago as 1929, we know how to do this in principle,
it's just that the calculations are too difficult in many cases.
The reason for this is because of exponential growth.
To help explain this, there's a tale, probably apocryphal, about the person who invented chess.
The story is that the king offered him a reward for inventing chess,
so he asked for a grain of rice on the first square of a chessboard,
and two on the second, four on the third, and so forth, up to the 64th square.
This seemed reasonable to the king, so he agreed.
But when you work out the total amount of rice,
it works out to around 4 hundred billion tons,
which is probably more rice than has ever been produced in the entire history of the world.
In much the same way, if you want to simulate one quantum system,
it's easy, if you put two together it's twice as hard, and so forth.
If you want to simulate just 64, it's going to need around a million times
the memory of the world's biggest supercomputer just to store the state.
So this problem led Feynman to the idea that, if you want to simulate a quantum system,
you're going to need to build a computer that takes advantage of the laws of quantum mechanics.
This was the original motivation for building quantum computers
- to be able to make predictions of the properties of quantum systems.
But what if you want to do something else? Are quantum computers only going to be useful
for simulating other quantum systems, or can they be used more generally for other types of problems?
Peter Shor gave a very definitive yes to this question.
What he found is that, if you could build a quantum computer,
you would be able to break the most commonly used type of cryptography.
Now whenever you go online and type your password in,
or enter your credit card number to buy something,
you're relying on what's called public key cryptography.
This relies on the difficulty of factoring large numbers
- if you have two numbers then it's easy to multiply them together,
but if you don't know what the original factors were it's very difficult to find them from the product.
What Shor found is that if you could build a quantum computer,
then you could essentially break all the encryption that's used online.
Now of course intelligence agencies were very interested in this.
They build huge data centres to store all the communications they intercept, but what they really want
to know is encrypted and they just aren't able to decrypt it.
Next I'll explain a bit about how public key cryptography works.
The idea is that you have a public key which you give out to everyone.
Then if someone wants to send a message to you, they encrypt their message using the public key.
The thing about the public key is that it only works one way.
You can use it to encrypt the message, but you can't use it to decrypt again.
This means that it doesn't matter who knows the public key
- if they intercept the encrypted message, they can't work out the original message.
But you have an advantage, because you have another key that you haven't told to anyone, called the private key.
That means that you can decrypt the message, but nobody else can, because you never told them your private key.
So what are these public and private keys?
Well the private keys are two large prime numbers, and the public key is just the product of them.
What this means is that the message is secure unless someone has a powerful
enough computer to factorise that public key and work out the private key.
Now there are two basic principles involved in quantum computing. These are superposition and interference.
The idea of superposition is that a quantum system can essentially be doing two different things at the same time.
This is something that goes against people's usual intuition about how the world works,
which is nicely illustrated by the Schrödinger's cat experiment.
The idea here is that you have a cat in a sealed box,
and there is a radioactive atom that has a 50/50 chance of decaying in a given period of time.
Because it is a quantum system, we expect it to be in a superposition.
And then if the detector detects the decay, then it will release a hammer,
which breaks a bottle of poison which kills the cat.
If you take quantum mechanics seriously, everything has to be in
a superposition and the cat should be both alive and dead.
Now this might seem a bit cruel to cats, but no-one is really doing this,
this is just a thought experiment to illustrate the idea.
The idea of a quantum computer is a bit like this, except you're not
killing the cat, you ask it to do one of two calculations.
Well you can't do that with a real cat, but when it comes to carefully controlled quantum systems you can.
Now superposition on its own just isn't enough, because there is the
question of how you are going to tell if something is in a superposition.
If you just open the box you are only ever going to see the cat as alive or dead.
This is where interference comes in.
The idea of interference is just like ripples in a pond.
If you have two objects making ripples in a pond,
then you're going to find that in some places the peaks coincide,
so the water is higher, and you have constructive interference.
In other places the peak from one set of ripples is going to coincide with
a trough from the other and cancel out - this is called destructive interference.
You get basically exactly the same thing with quantum systems.
In this example we have a laser down the bottom, which sends a beam of light through a beam splitter.
The beam splitter sends half the beam one way and half the beam the other way.
Then the two halves of the beam are combined at a second beam splitter.
In one of the outputs of the beam splitter you get destructive interference, so you get nothing,
and in the other output you get constructive interference, so that's where the entire beam comes out.
Now you don't have to send a bright beam of light through here,
instead you can send the individual particles of light, known as photons, one at a time.
When you send the photon through the first beam splitter you only
have one particle of light there, so you can't actually split it in half.
Instead what you find is that the photon is in a superposition of going through each arm at the same time.
Essentially the photon is like Schrödinger's cat, in that it's doing two things at once.
It isn't the case that it's really in one arm or the other, and you just don't know which.
If it was really in the left arm, then it would come out in
the second beam splitter equally in the two outputs,
if it was really in the right arm it would again come out equally in the two outputs.
This means that if there was no superposition, you would have equal chance of seeing the photon in both outputs.
But what really happens is the photon is in a superposition of the two arms, and when it hits the second beam splitter these
two alternatives interfere, and the photon can only come out in one of the outputs.
To explain how you actually use this, I'll explain the idea of the universal quantum computer,
which is needed for Shor's code breaking algorithm.
The idea of a universal quantum computer came from David Deutsch back in 1985,
just a few years after Feynman came up with the idea of a quantum simulator.
The idea of a universal quantum computer is essentially
that it's in a superposition of calculating a whole lot of different things at once.
The reason why he came up with this idea is that he was looking at it from
the perspective of the many worlds interpretation of quantum mechanics.
That is, you regard the computer as doing a whole lot of different calculations in different worlds,
and then you can interact them through interference.
Now the basic idea in a regular classical computer is the bit.
A bit can be either 0 or 1; with a whole lot of them you store data, and you can perform operations on these bits.
Bits are just like regular numbers, except they're written in base 2 instead of base 10.
When it comes to quantum computers, you replace the bits with a quantum version of bits, known as qubits.
These are written like bits, except there's a straight line at the left and an angle bracket at the right,
which indicates that this thing is a quantum state.
The idea is that you would encode these qubits on individual quantum systems, shown here in an artist's representation.
The 0 and 1 would be two distinct quantum states for each of the individual quantum systems.
These zeros and ones are what we call computational basis states.
The idea is that instead of just working with them, we can have general states that are superpositions of these things.
Here x would be some bit string, and we sum over all of these bit strings with various weights psi x.
These psi x can be general complex numbers, and you can think of the state as like a vector of these complex numbers.
Then when you go to look at what operations you can do on these states,
these can be represented by matrices of numbers.
Your operation acting on the state is then just matrix-vector multiplication.
The important restriction on these operations is that they have to be reversible.
That is, once you've done the operation, you need to have another operation that gets you back to where you started.
If you want to consider operations that are like classical operations, these will be the permutations.
What these do is to take one computational basis state, and turn it into another.
A simple example of a permutation operation is just the NOT operation.
This has a matrix representation like this, and takes a 0 to a 1, and vice versa.
This is obviously reversible, because if you do it twice then you get back what you started with.
The slightly more complicated example is the CNOT, or controlled not.
This has a control qubit, and if the control is in the state 0 it does nothing,
and if the control is in the state 1 then it does a NOT on the target qubit.
Here I've introduced the quantum circuit notation to illustrate this.
The idea here is that time goes from left to right.
The horizontal lines are representing the two qubits, and the vertical line is representing the CNOT operation.
The top line is the control qubit, and the NOT on the target qubit is represented by the circle with the cross in it.
Next we'll look at how to turn classical operations into quantum operations.
The prototypical classical operation is the NAND gate.
The NAND gate takes two inputs, it takes an AND of them, then the NOT.
The only case where an AND can give 1 is if both inputs are 1.
But because we take the NOT after that, the only case where we can get a 0 output is when both inputs are 1.
This is shown in the truth table on the right, where 0 is only obtained when both inputs are 1.
The NAND gate is very important in computing theory because it's universal.
This means that, if you consider any other logic gate you might want, then you can construct it just from NAND gates.
In turn, if you consider any calculation that you might want to perform, then you can construct it out of logic gates,
and those logic gates can be made from NANDs.
Then in the quantum case the NAND gate has a simple equivalent, which is known as the Toffoli gate.
The Toffoli gate is very similar to the CNOT, except now it has two controls.
What you can do is take the inputs A and B that you would input to the NAND gate,
and input them as quantum states as the controls on the Toffoli.
Then for the target qubit, you just initialise it to 1.
Then at the output, the controls are unchanged, but the target is now changed to the NAND of the two controls.
To see why this works, if the NOT is not performed, then you just get a 1 as the output in the target.
The only case where the NOT is performed is when both controls are 1, and then the output is 0.
There are some important principles that this is illustrating, which are used more generally.
As I said before, everything has to be reversible.
If you look just at the NAND gate on its own, then it's very definitely not reversible.
If the output was 1, then there were three different possible combinations of inputs.
A way to get the thing reversible is to keep a record of the inputs.
This means that, at the end, you still have a copy of the inputs, which you can use to undo the gate.
This is essentially what's happening in the Toffoli gate, where you have a copy of the inputs at the outputs.
Another thing is that you're going to need another register to put the outputs in
- that's the answer to the NAND gate in this case.
In the Toffoli gate we have this extra register down the bottom that's initialised to the 1 state.
Now we have a general way to turn a classical calculation into a quantum calculation.
As I said before, any classical calculation you can write out in terms of NAND gates.
By turning all the NAND gates into Toffoli gates, we're able to perform any classical calculation on our quantum computer.
So in this way, any function that we want to evaluate, we can evaluate on our quantum computer.
That means that we have an operation Uf that takes the x input as a state, and outputs f of x encoded as a state.
Just as with the Toffoli gate we had a copy of the input at the output, here we have a copy of x.
Also, as before, we have an extra register in the initial state which we put the result into.
I should mention that it's a little more complicated than this, because if you just swap the NAND gates with Toffolis,
you'll have a lot of extra ancilla registers that depend on x, due to keeping the controls at intermediate steps in the calculation.
However, it's fairly straightforward to clean those up so the function calculation is in the clean form that's shown here.
Now we start to see the power of quantum computing, because we don't
have to just start in a computational basis state x, that's a bit string.
We can start in a state that's a superposition over these bit strings.
Then when we evaluate the function, we actually evaluate the function at all possible values of x at the same time.
If there are n quantum bits, the qubits, then the number of function evaluations goes like 2 to the power of n.
As I was saying before, this is an exponential growth, which gives extremely large numbers.
If you had just 64 qubits, then the number of function evaluations would be
around a million times the storage of the world's largest supercomputer.
But that's only part of the story, the other part of the story is interference.
If you were to measure it, you would only get one value of the function.
What we aim for is some global property of the function, and to get that we need to use interference.
The prototypical operation for interference is the Hadamard gate.
The Hadamard gate takes a 0 and turns it into a plus superposition of 0 and 1.
The root 2 there is just for normalisation - you don't need to worry about that.
If you did the Hadamard again then you would just get back to the 0 state.
On the other hand, if you started with a 1, then you would get a minus superposition,
where you have a 0 state minus a 1 state.
It turns out that the Hadamard together with the Toffoli gate are universal for quantum computing.
This means that anything an arbitrary quantum computer can calculate, you can calculate with just these two gates.
The issue that you can't tell that there's a superposition without interference
is really why we don't see superposition in our everyday lives.
With Schrödinger's cat, if you were just to open the box and look, then you would only ever see the cat as alive or dead
- you would never actually see it as a superposition.
On the other hand, imagine if you tried doing a Hadamard on Schrödinger's cat.
If you had a superposition of a live and dead cat, then you could turn it into a live cat again!
This is great news for cat lovers, but you need to be a bit careful,
because if you actually had a minus sign in the superposition to start with
then you would turn it into a completely dead cat, which isn't so good.
Joking aside, if you could do this, then you could prove it was actually in a superposition.
Of course it is kind of difficult to bring a dead cat back to life,
and it's even more difficult to show superpositions with macroscopic objects.
On the other hand, with individual quantum systems like photons it can be done fairly routinely now.
This is exactly equivalent to the example of the photon and the beam splitters that I explained earlier.
You have a superposition of the photon in the two arms, and then the beam splitter
performs a Hadamard on the photon and gives you interference.
Next I'll explain how these ideas are actually used in a quantum algorithm.
This is just a toy problem, but it illustrates the ideas that are used with actual useful quantum algorithms.
This is known as the Deutsch algorithm, and it's the one that David Deutsch showed in 1985.
The problem to solve is where you have a function on a single bit.
That is, it takes a single bit as input, and gives a single bit as output.
What you want to work out is if the function evaluates to the same thing on 0 and 1.
In the classical case there is just no way around it.
You have to evaluate it at both 0 and 1 to work out if the function values are equal.
In the quantum case you can do better, and work it out with just one function evaluation.
The basic idea is to do the function evaluation on 0 and 1 simultaneously, then interfere the result.
This is illustrated with this quantum circuit here.
Remember that time goes from left to right; the horizontal lines are qubits.
We start with them initialised as 0 and 1, then perform Hadamards on each of them.
Then we have this Uf operation. Remember, Uf is the function evaluation, and it acts on both qubits.
At the first output qubit we perform a Hadamard again and then measure.
The result of this measurement will tell us whether the two function values were the same or not.
In this circuit we can actually divide things up into the superposition part and the interference part.
This first part here gives us the superposition.
The Hadamard sets the input into a superposition of 0 and 1, then the function is evaluated on both at the same time.
Then the Hadamard at the end gives us the interference.
That was just a toy algorithm, and next I'll explain an algorithm that has rather more real-world application.
This is Grover's search algorithm.
Now the idea of Grover's algorithm isn't something like an internet search or looking for an object.
The idea is to find an input to a function to get an answer of 1.
This might at first seem not to be so useful, but consider for example the case of factoring.
In that case the function could give 1 if we find the correct factor.
This means that if you can speed up a search you can speed up factoring,
though in this example there's better ways of doing it.
Another example is trying to prove theorems.
There your function can be 1 if a proof of a theorem is correct.
In general it can be extremely difficult to find a proof in the first place
- remember how long it took to prove Fermat's last theorem.
But once you've found a proof it's relatively routine to prove that it's correct.
If you could achieve an exponential speedup for a search then it would mean that proving a theorem
is essentially not much more difficult than checking the proof.
This is regarded as very unlikely, but with a quantum computer you can get some speedup.
Classically the complexity of the search is essentially going to scale like the number of possible inputs,
which means that it's exponentially difficult in the size of the input.
Grover's algorithm doesn't give you an exponential speedup, but it does give you a square root speedup.
The way that it works is more subtle than Deutsch's algorithm.
You do still need to do an evaluation of the function on all inputs simultaneously.
But then the interference step is essentially to reflect about an equal superposition state.
These two steps need to be done not once, but root N times, which is what gives us the root N complexity.
I'll illustrate this with a simple example with N equals 4, and the solution on the third entry.
We start with an equal superposition state, which is indicated by the bars at the bottom.
Next we apply the function evaluation, but now we choose the function evaluation to flip the sign on the solution state
where the function evaluates to 1, rather than putting the value of the function in an ancilla.
That means that only the solution is flipped here.
Now that isn't enough on its own to find the solution, because the bars are still of equal size.
Now reflecting about the equal superposition state is like reflecting these bars about the mean.
Calculating the mean, we find it is the dotted line here.
Then when we flip around the dotted line, all the bars get flipped to zero except the solution state, which becomes bigger.
As a result, we get the solution, the state 3, after only one function evaluation.
We can't do it in only one function evaluation for larger N, but we can do things in around root N steps.
Another way of thinking about this algorithm is that it's like two reflections giving us a rotation.
It's just like having two mirrors at a small angle to each other.
When you reflect in one mirror then the other you're getting an image that's rotated.
In Grover's algorithm the function evaluation gives a reflection of the solution,
and the other reflection is about the equal superposition state.
You can look at it on a plane like this.
You start with an equal superposition state, which is the s here.
The omega is the solution,
and we have a vector s prime which is orthogonal to the solution.
The function evaluation reflects us around s prime.
Then if we reflect around the equal superposition state, s,
it rotates us up to here.
If we initially started at angle phi away from the non-solution
state s prime, then we're now at 3 phi.
Doing this again gets us to 5 phi,
and doing it again to 7 phi
and again to 9 phi, which almost gets us there,
and then to 11 phi, which actually rotates us slightly past the solution.
This is a general feature of this algorithm, which is that it tends to get us almost, but not quite to the solution.
We can find the solution with high probability, though.
The number of rotations that you need in this picture is of order root N.
So anyway that finishes this video.
If you'd like more detail, there's more detailed presentations at my website at dominicberry.org.
Thankyou.