An introduction to quantum computing for quantum conversations and Stanford Quantum.
Video • Slides
Transcript
Thank you all for coming, and thanks to Alexy for having me. Today we’re going to talk about quantum computing in general, and then AWS braket a little bit in particular. The purpose of my presentation is just to try and give you a bird’s eye view of this field, an overview of how exactly it works, and some different approaches that are out there right now. Towards that end, we’ll try to do a very brief overview of the theory of quantum computing, and then from there, we’ll look at the actual hardware and virtual hardware devices that are available to run quantum simulations. We’ll also look at some of the software that exists that you’ll actually use to program your circuits and run things. From there, we’ll look at some applications of these techniques, different fields that I think these quantum computing methodologies can be applied to, and then at the end we’ll talk briefly about this concept of quantum supremacy and the future of this field in general.
Quantum mechanics
The basis of quantum computing is quantum mechanics. I did a talk on this a little over a year and a half ago at TensorFlow World and I’ll simply repeat what I said there, which is that I would love to throw up one slide and you understand it perfectly, but I don’t think that’s possible.
The basis of quantum mechanics we’ll say, is this thing called the Schrödinger equation. It can be written quite simply as Eψ=Hψ. The E in the equation is from E=MC^2, Einstein’s equation, which just means energy. Ψ is a little bit tricky to explain, but you might think of it as simply being our system. Then the H with the ^ on top is called an H bar, this is just a special form of matrix called the Hamiltonian. And so Hamiltonians are a way of encoding the state, we’ll say. So, then Schrödinger’s equation says nothing more than the energy of the system is equal to the state of the system. This is deceptively simple because a number of interesting observations follow out of this mathematical equation, and as a result, it’s considered to be the pinnacle of 20th-century physics.
Wave functions are an important part of how all of this works. They come to us by way of classical mechanics where they are used there to describe things like sound, and interactions with energy in the systems. But the way that quantum mechanics uses them is slightly different. In quantum mechanics, we have the state, the wave function itself. But then we also have this concept of the conjugate pair, so the opposite of the state. I think this is where the mind-bending stuff out of quantum mechanics comes because the conjugate literally encapsulates all of the other possibilities in the universe. This is where you get into the philosophical questions and things like that.
There are a few different ways of working with these wave functions. A gentleman named Dirac popularized what’s called Bra-ket notations where we think of the Hamiltonian as being sort of a projection in inner space with these two vectors. So the one-wave function is going one way, and the one going the other way is the opposite, so to speak. Then from there, we can work with these operators in a linear fashion. We might say that the Hamiltonian then is just some real matrix times the cross product of these two vectors.
Self-study
Like I said, this is a pretty dense field. I saw that you all were talking about the best way to pick it up. I don’t know that I can necessarily tell you the right way to learn, but I thought maybe I could talk about some of the stuff that I studied and that I found useful, and maybe that will be of value to you. The single best reference I’ve found on the subject of quantum mechanics is this set of online lectures, it’s called Quantum Physics 130 from the University of California, San Diego. They start with first principles, we’ll say, and walk you all the way up to deriving the Dirac equation for the hydrogen atom analytically, which is literally as far as you can do things using analysis.
I think you’ll find, or at least I’ve definitely found that whenever I’ve tried to do all this, that I had a lot of holes in my mathematical education, so I’ve had to spend a lot of time going back and relearning my mathematical basis for things before I could make sense of all this other stuff. Towards that end, ideally, you could take a course on linear algebra or something like that. But for me, I don’t like whenever people say… “If you want to learn this first subject, you need to learn another subject and then come back.” For me, I think the best way to do it is to just try to get as simple of a high-level understanding of the problem as possible, and then you can add more and more mathematical rigor as desired.
So towards that end, this book called “Quantum Mechanics in Simple Matrix Form” by a gentleman named Thomas Jordan is as succinct and concise and clear an overview of the subject of quantum mechanics as I’ve found. He does everything just in matrix forms, he doesn’t even use wave functions. Then he does everything else, which is sort of like trigonometric identities. So I think somebody with even just a high school education of mathematics and a little bit of how to multiply matrixes could read this book and understand the high-level math that’s going on. Professor Jordan has another book titled Linear Operators for Quantum Mechanics. It’s a really succinct high-level overview of this field if you’re interested in linear operator theory. So I would recommend that as well.
In the process of trying to relearn all this mathematics, I went down the rabbit hole of differential geometry. I wish all physics was taught that way. This book Differential Forms with Applications to the Physical Sciences is just a lovely book to try and explain physics through differential geometry. In particular, I became interested in the work of David Hestenes who spent a lot of time trying to unify the worlds of differential geometry and quantum mechanics. These last two books are basically an overview of analysis, they are by this gentleman by Alan MacDonald. Part of the reason why I recommend his work is because he is sort of a disciple of Hestenes, so I think that’s interesting as well.
These first few books I’ve shown you are like Dover books on mathematics, so for like $10, you can buy yourself a lifetime’s worth of math.
Quantum computing
Quantum computing proper then is simply bringing the concepts of computer science to this quantum realm. There is a gentleman by the name of Scott Aaronson who has done interesting work in his field, but he had this set of lecture notes on the arxiv that I thought was actually a really concise overview of this subject as is possible. This set of lectures, it’s like 10 chapters, and it goes wonderfully off in the deep end of quantum black holes and things like that, but I thought chapters one and two were just a nice clean overview of these things. Chapter one was simply reviewing the mathematics of linear operators for quantum mechanics, and then chapter two breaks down how we bring traditional computer science complexity theory to the quantum realm.
The basic idea in computer science is that we have sets of what are called “np-complete problems.” Basically, an np-complete problem is just a problem that there is no good way to solve it, and by extension, the only way to solve it is to test every single possible answer or option. If you would allow me to turn a phrase, we might say we have to explore the entire universe of possibilities.
SAT solvers are one area of np-complete problems. This is something I spent a bit of time on in grad school, so that’s my window of this whole world. SAT solvers oftentimes in order to solve a problem, they’re sort of constructed to say, “is this problem valid or not?” “Is this a real problem?” So really, if you look at how it actually programs at the SAT solver level, it’s actually just all like a gigantic truth statement. “Is this statement true or false?” But, in order to know that, you have to actually solve the problem, and by extension, then you can come back to that question.
The reason I talk about this is because in quantum computing, we have this concept of oracle functions where we can consult a quantum oracle, so to speak, and it can give us a probabilistic 1 or 0 as to whether or not it thinks that we have the answer. So for certain problems, if we set up our systems correctly what the quantum computer can do is basically explore all these solutions in a sub-linear time. It can actually go through all of the options at a less than np complexity. And so ultimately this opens the door for this explosion of linear versus exponential complexity, or rather for certain problems, a quantum computer can provably solve them faster than any traditional classical computer.
AWS Braket hardware
AWS Braket is a service that AWS finally opened up to the public last fall. You can run quantum circuits on actual real-world quantum hardware. You can use these techniques directly. They have a handful of different devices on their platform, we’ll walk through them here. But you should be aware of these things. They have this Rigetti device which has 30 qubits. This is a startup that’s been sort of at the forefront of trying to build these quantum computers, and they’ve been able to make them larger and larger. They have another one that’s just an ion trap device, it’s 11 qubits. AWS provides two sets of simulators. The sv1 can emulate up to 34 qubits of state space, and they recently announced the tn1 which can emulate up to 50 qubits, but your problem has to be structured in a certain way. It may not be able to solve all sorts of problems.
Then also the other devices that AWS will provide you access to are D-wave quantum annealers – these don’t really work with quantum entanglement, but there are some interesting problems that we can run on these devices. The first generation of hardware had about 2k qubits, but then they also recently announced another version that has about 5,700 of these qubits to work with.
qsim + cirq
I tried to make a few different demos for you all, and I ended up making this one randomly, but actually, I think this is probably the most important slide I can show you. I’ve just constructed some random circuits of various sizes and then wrote down how long it took to evaluate each one. So we’re going from a little 8 qubit system all the way up to 34 qubits.
So this blue line isn’t really showing us anything more than that as our system gets larger and larger, it takes more and more time in order to evaluate as we would expect. Basically, the process looks to be a nice clean straight line. The trick is over here on the left side of this graph because this chart is in log units. So each of these little gray lines is two orders of magnitude more time to run that particular circuit. So from this, we can see that my computer can emulate a 20-qubit system in under a second, but as we go up from there, it just starts to take longer and longer to do these things.
By the time we get to 33 qubits, it takes about 40 minutes to run a simulation. I went to 34, this took about 10 hours, but technically it was hitting the memory, so my computer starts swapping – I only have 128GB of ram on my machine. But you can see that as we increase the complexity, the amount of time for the computer to simulate it just starts to grow astronomically. We might imagine another rung up on this thing, somewhere around a million seconds. So one more rung would take 10 days to run, and if we went up one more rung from there, we start talking about three years of simulation time. One more rung past that and all of us will be dead before the program finishes.
The first demo I think you should run on the AWS Braket system is simply a demonstration of what is called Bell’s inequality, or Bell’s theorem. This is basically one of the classical proofs of the entanglement phenomenon, and rather than doing it theoretically, you can empirically derive it. So there is a demo of this running on the Rigetti with the AWS thing, and you can simply fire it up yourself.
Quantum chemistry
If we can imagine small 2 qubit system entanglements, then we can start to think about building slightly larger ones. From there, I think we can get into the realm of quantum chemistry. I think this is one of the more interesting short-term practical applications of all this stuff. We have this whole world of physical chemistry where we derive the properties of various materials just basically off of how their electron fields work together. So we might want to, say, simulate hydrogen atoms and then try to measure their energy levels. So there are classical algorithms in this space, notably like the Hartree-Fock algorithm. But the problem with this is that Hartree-Fock can’t really capture properly a quantum system. So then you start introducing these adjustments, notably like density functional theory to try and make your predictions match the real world. But if we have a quantum system, effectively we can simply measure the energy of our quantum system and by extension, we can derive our data empirically rather than having to do the math behind it.
There is a company called Pennylane, it’s a startup in this space. They have a whole website with a lovely set of demos and tutorials on various different concepts on quantum computing, and I think you owe it to yourself to look through those things. The demo, in particular, I would tell you to run is simply their demonstration of the VQE algorithm on H2. That would be the quickest way to wrap your head around this stuff. They have tools to bridge out to Pytorch, which is the machine learning framework. So if you have the skills with Pytorch, this can complement some of that. This VQE algorithm, or variational quantum eigensolver as it’s called – I think it’s really interesting because of the ability in the near term to run these quantum circuits and be able to do meaningful science on top.
So what we’re seeing here on the left is how the VQE algorithm was laid out and how it actually models a circuit for this paper which came out last year. Then what we’re seeing on the right is the results, we’re measuring the actual electron density, and by extension the energy levels. To me, the most important part of this graph is simply the difference between this dark red and light red line. It’s showing that when they made the system bigger, it was able to produce better and more accurate results. So by extension in the future, as we can build larger and larger quantum circuits, using them to run these simulations to match expectations from the last century or so of traditional sciences in this field. It gives us this really interesting ability to have this feedback loop of reutilizing prior knowledge to build larger and larger systems and circuits.
The next demo I think you should run is something called Grover’s Algorithm. This picture is attempting to explain how the circuits are laid out for this. There’s a demo of this for the AWS system running on the ion trap device, so you can get it running yourself pretty easily. The key thing to take away from this slide is right down here, the part where it says, “Repeat O of the square root of N times.” This would be an np complete problem in traditional computing, but this quantum circuit is able to have an exponential speedup and solve it in sub-N time. So by extension, this opens the door to the realm of the potential quantum speedups for these sorts of problems.
Another thing you’ll notice from this demo is that these devices are quite noisy, and it’s going to be a long time before we’re cracking encryption systems or anything like that. From there I thought it would be interesting to look at some of the D-wave systems because I think what they do is much more practical for sort of solving problems in the here and now.
Quantum annealing
The D-wave systems are constructed around what’s called QUBO, but basically, we take our problem, and we encode it as a graph, and then we reduce the energy of the system, and then in theory we can find in the embedding of the graph that correlates with the answer that we’re looking for. This paper that I took these slides from was taking various SAT solvers and then converting them to run on the D-wave device, and then we’re talking about a lot of the interesting real-world numerical stability that you had to do to actually get these things to work.
Another paper on the D-wave that I thought was interesting – but effectively, they used the D-wave device to factor a large number on the order of 200k, which is larger than any other quantum device to date as of this paper. But basically, they used some abstract math to convert their factoring problem into a very complicated graph reduction, and then this picture is showing how the adjacency matrix and by extension the activation of the D-wave system and when it’s run.
So then the D-wave has all of these optimization algorithms that they have that you could run on top. There are a bunch of these acronyms in this space. We have QALO, QUBO – that’s quadratic unconstrained binary optimization – and then they have various statistical optimization approaches. The one that stood out to me was the traveling salesman problem. In Grad school, we had to write a solver for this using simulated annealing, and so this was very much similar to the stuff that I had done before. They modeled a set of cities, you convert it into a graph problem, and then you can run it on this D-wave device. That would be the one I suggest that you do in order to wrap your head around this whole thing.
Then the D-wave had a bunch of graph problems – if you’re familiar with that literature, basically you can run on this device and bring it over if you have a problem if it fits in that realm already. Then I thought I would also mention this other paper – this is from IBM, it’s simply an overview of various different attempts to try to implement every algorithm they could find on a quantum device, and I just thought this was a really interesting paper for showing you a whole bunch of different potential approaches, and maybe you will find one in there that is of interest to you.
Quantum networks
A lot of my background is around neural networks and so if we have graphs, then we can have neural networks. This is a paper on quanvolutional networks. It’s sort of constructing something like a CNN we’ll say, but in the quantum realm. But they are building their own operators, and then by extension, able to attempt to categorize input images as just like a basic neural network layer.
Then this is the other paper in that field – it’s actually a little bit before that one, but basically, they are just building a quantum convolutional, and then a quantum pooling operator, and they combine these two together to make a classical fully connected neural network style approach for categorizing mnist digits. So there’s a nice demo of this one – TensorFlow has released this TensorFlow Quantum Package which is just allowing you to bridge out to the wider world of TensorFlow, and so by extension, you can get datasets and stuff like that for free. So they had this TensorFlow quantum tool which, if you’re familiar with TensorFlow, is just a good set of tutorials and stuff to run through to wrap your head around some of these different concepts.
Quantum supremacy
Then at the end, I would like to just talk a little bit about this idea of quantum supremacy. This is from a paper that Google published last year – their Sycamore device, which had 53 qubits, was able to demonstrate solving a problem that a classical computer wouldn’t have been able to do.
If you look at this graph, to me it’s basically the opposite of the graph I showed you earlier. But if you look at the left side, basically they are building larger and larger qubit systems and it becomes harder and harder to measure and get the results to make the system cohere, but they were able to get this 53-qubit system to output the answers that they were looking for. And then over here on the left side of this graph, we’re just seeing estimates of how long it would take for a traditional computer to perform these same results.
Then this is a paper that came to us by way of China a couple of months ago. These Chinese researchers were able to demonstrate what’s called Gaussian Boson sampling. This is like a large-scale physics experiment where they generate a bunch of photons using lasers and they do some tricks to get them bouncing around together in sync, and then by measuring the results on the other side, they have in theory solve a problem that would be impossible to simulate on a traditional computer system. They claim their system will do 43 qubits of simulation level without that much difficulty and then they had better and better runs, so they demonstrated that their system had done this experiment at the 76-qubit level as well. This is the second proof of quantum supremacy, so to speak, that we have now. We’re seeing the dawn of these probabilistic processors potentially opening up new doors and new possibilities.
Future
With that, I thought I would talk about the frontier. This is a slide I stole from an AWS presentation last year, but I think it really illustrates these concepts as well. Everything I’ve shown you today is in this “zone one” over here. With this quantum supremacy experiment where the red dot is, we might say that we’re starting to cross the phase change into this realm where these quantum computers can do stuff that we have not been able to do yet. Then we can argue about where this orange line should be. Some people think that we can do meaningful real-world problems, like 400-500 qubit systems. But what is interesting to me is that we know where we are, we know where we want to be, and in the future as long as we can go down and to the right, someday hopefully humanity will be able to use these tools with some regularity and make them easy to do.
To recap – we’ve talked briefly about the theories of quantum computing and how it works under the hood. We’ve looked at some different applications that I think will become more and more prevalent in the future. Along the way, I’ve shown you a set of different demos that you could run to get this stuff working with different various hardware and software approaches in this field. And finally, I wanted to say that the future is literally people like you and I. I think it is great that Amazon is making these tools available to whoever wants to run them. I think this just opens up the possibility that anybody in the world is able to play with these tools, and I think that’s really cool in general.
I wanted to say thank you to AWS, they gave me some credits to run all of this. But all of the demos I have shown you today were like $5 to run on an actual quantum device. So by extension, I would argue that for the price of a pizza, you can duplicate everything I’ve shown you here. The only difference for any of you between being a theoretical quantum computer scientist and being an applied quantum computer scientist is a little bit of your time. I hope that you play with these tools yourself as well.
Thank you for listening.
Q&A
You mentioned that for the price of a pizza you can play with the tools. But I’m wondering, how much time do you have to actually spend to prepare on the brakets and get everything in there? I remember when I was applying to get access to Rigetti’s machine a year ago, and it was taking a few months before I got into the list and I got access to Rigetti. They give you free access, but I’m wondering how long does it take to go through the process with AWS?
Basically, you can sign up for AWS and you can load up the various notebooks on there. It’s based around their SageMaker platform. Then you can program your experiment into the notebook and then you hit a submit button and it sends it out to be scheduled on the actual device. It depends on the device you want. They’re not always available. But for most of them, every 24 hours you should be able to get your experiment in. Then at the end, you get a batch job back, If you’re familiar with doing machine learning workflows with preemptible instances – that’s something I do a lot of – then it’s just to be very much that same workflow where you type all of your code in there, hit send, and then eventually you can get a result back. But most of the time, under 12 hours, and your experiment will get scheduled. Not all of the devices are available, but the D-wave ones are usually available. The ion trap usually has less of a waiting time, but then the Rigetti ones seem to be the most popular right now, at least that’s what I’m noticing whenever I played with it.
References:
Books:
- Quantum Mechanics in Simple Matrix Form, Linear Operators for Quantum Mechanics • Thomas F. Jordan
- Differential Forms with Applications to the Physical Sciences • Harley Flanders
- Linear and Geometric Algebra + Vector and Geometric Calculus • Alan Macdonald