Quantum Machine Learning
TWiML Meet-up Video Lecture and Slides
The study of books is a languishing and feeble motion that heats not, whereas conversation teaches and exercises at once. … When anyone contradicts me, he raises my attention, not my anger: I advance towards him who controverts, who instructs me; the cause of truth ought to be the common cause both of one and the other. — Michel De Montaigne
Recorded Lecture
Presentation Slides
*Please note the transcript of the talk provided below was incorporated into this post on 5/22/19. Many thanks to YouTube for their excellent transcription service.
This Week in Machine Learning & AI
Okay I’ll go ahead and jump right on in so the topic of this discussion is going to be around the intersection of two emerging fields: quantum computing and machine learning. It’s going to be a two-part talk. I’m going to cover a lot of ground pretty quickly and obviously you’re welcome to ask questions any time. I will have slots for questions at the midpoint and at the conclusion, so you know the preference is you can hold till then, but you’re welcome to ask questions at any time.
Just a quick introduction my name is Nicholas Teague. I’m a professional in the renewable energy industry. I have a background in marketing, engineering, and procurement — that’s my day job and for fun I write on Medium — essays addressing emerging technologies as well as some creative writing.
Okay so part one of this talk is an adaption of a blog post that I published in 2016 which is basically kind of an overview of some of the fundamentals of quantum computing and the goal is that through this discussion you’ll have a better idea of what it means when people talk about quantum computing. Just kind of the fundamental concepts. I’m going to take it for granted, in the interest of time, that you guys have some familiarity with some of the fundamentals of quantum dynamics — I’m gonna use concepts like (I mean obviously it’s not a simple subject) but I’m going to use concepts like superposition, interference, entanglement, and measurement and those are going to come up, and so I’ll point you to some reference literature if you’d like to learn more and I’ll be here to answer questions as well.
- Feynman Lectures On Computation — Richard Feynman
- QED — Richard Feynman
- Feynman and Computation — Anthony Hey
So I’ll start with kind of a highlight of an important figure in the industry, a well-known physicist by the name of Richard Feynman. He was a physicist first, but he was also fairly well rounded. He was infamous for picking locks at the Manhattan Project. He was an accomplished bongo drummer, a visual artist, as well as a writer of many popular books ranging from autobiographical personal anecdotes to more technical matters like physics and computation. Some of his books that I’d recommend: the first one I read was QED which is a very accessible treatment of quantum electrodynamics which is a good introduction to some of the considerations of quantum theory, and then from a computation standpoint his lectures on computation, which was a class he conducted at Caltech, has been assembled into a book and it’s a great introduction to computer science. And then there was also an excellent companion book which addresses some of the frontiers of computing and is very relevant to the subject matter.
So I’ve heard it said in a paper by the physicist Murray Gell-Mann that Feynman’s biggest contribution was discovering how to sum quantum histories using the path integral method, and he’s very well known for visualizing subatomic particle interactions in Feynman diagrams (which he painted on the side of his van) so these are just a few of the things that he’s known for. He had a lot of contributions. And with respect to quantum computing his kind of call to action was a talk in 1981 which brought a lot of attention to the field. It was a talk called “Simulating Physics with Computers” where he basically asked for researchers to investigate ways to incorporate systems with quantum behaviors to improve our ability to simulate natural systems that are outside the reach of classical computers.
So when we talk about classical computers and quantum computers the most typical way that they’re introduced is based on kind of the fundamental building block of computation, which is the bit versus the quantum qubit. And in classical computing our paradigms of digital computing have all basically been different realizations of systems that can achieve some binary state, which is represented by 0 or 1, which then form a computation by a progression through a series of logic gates. And the logic gates basically take an input of 0’s and 1’s and then based on the type of gate applied find outputs of 0’s and 1’s. And with a sufficient set of gates it’s possible to reproduce any digital circuit, which gives you computational equivalence to a Turing machine, or universal computing. And some of the different paradigms of digital computing have been things like electro-mechanical systems, vacuum tubes, relays, transistors, and then our current generation of integrated circuits. So with quantum computing it’s actually going to be an entirely new paradigm, outside of the paradigms of digital computing, such that the basic building blocks of computation, instead of bits, will be quantum bits (or qubits), which take advantage of quantum superposition between the two states 0 & 1 — that is up until the point that you measure the state and then the act of measurement causes that superposition to collapse, and you end up with a classical state.
So what does it we mean when we talk about a superposition of a qubit between the post measurement states of 0 or 1? This slide is kind of inspired by some of the lectures of Scott Aaronson. And basically a naive way to think about this might be to say that there exists some probability of a measurement generating a 0 or 1 for a particle in superposition, such that we could describe the state of the superposition as the sum of the (probability of a measurement generating a 0) plus (1 minus that that probability) which would then sum to unity. And it turns out this is insufficient to describe the full range of behaviors that are illustrated and that are realized for quantum bits in superposition.
So if we wanted to get more creative we could allow for those classical probabilities to have positive and negative values, and then we will just subject to the constraint that (the probability of a measurement generating is 0) squared plus (the probability of measurement carrying a 1) squared sums to 1, which you could visualize the on a point of the exterior of a circle. It turns out this is also insufficient to describe the full range of behaviors that are demonstrated by particles in superposition.
So the actual way that we can visualize and represent a qubit in superposition is by an analogue to classical probability, but allowing for it to be both positive and negative, as well as real and imaginary — so it’s a complex scalar. And if you subject that to the constraint that for that quantum version of probability (the absolute value squared of a measurement generating 0) and (the absolute value squared of a measurement generating 1) sums to unity. And that gives you the correct way to describe a qubit in superposition. And you could actually visualize that superposition as the point on the exterior of a spherical shell. And in quantum computing that spherical shell is known as the Bloch sphere. And so basically this is a way to visualize what we mean when we say that a qubit is in superposition.
So the Bloch sphere basically is an analogue of classical computing of classical bits, which is just one of either a 0 or 1. The Bloch sphere has poles — the North Pole represents the the state collapsing to a 0 and the bottom pole the state collapsing into a 1. And it’s from that complex scalar representation that we can derive a classical probability of a measurement generating a 0 or 1. It’s worth note that there’s some limitations of the Bloch sphere representation. It’s primarily meant to visualize the state of a single qubit in isolation, and as you incorporate additional qubits with resulting interactions and entanglements, the dimensionality the system goes up beyond what we can represent using pencil and paper.
- A Blueprint for Building a Quantum Computer (2013), Meter, Horsman
So now that we’ve talked about what we mean when we talk about a qubit in superposition, let’s talk about the physical realizations of how we actually build a qubit. I’m not going to spend a lot of time on this, but I just want to highlight that there’s several competing architectures that are being investigated and researched for commercial application. And basically each one of these architectures is just some system that has quantum properties which can be measured, manipulated, and controlled. The quantum superposition of an ion spin, of an electron spin, photon polarization, the superposition of a magnetic flux, and basically things like that. And they’re not all equivalent. Some of them have the potential for more scalability. You can incorporate working systems with more of them with current technology. And also some of them are more robust to errors and decoherence, and then some of them have different potential gate architectures.
I’m going to highlight one particular architecture because it’s going to come up more when we get to the quantum machine learning considerations. That is an architecture that makes use of the flux qubit, which is the quantum superposition of the magnetic spin. And with that we can have what we call adiabatic computing. Some of the physical practical considerations include they require refrigeration to near absolute zero for superconducting purposes, as well as heavy shielding from electromagnetic interference. So the the first one to market with this type of computer is a company called D-Wave, and their current generation has ~2,000 qubits. And from what I understand their next generation will be upwards of 5,000 working qubits. However something unique to this architecture is that it lacks a sufficient gate set for universal quantum computing, so the adiabatic computing architecture is a special-purpose machine — with key applications being quantum annealing, which is a kind of optimization algorithm.
So we in machine learning are obviously very familiar with optimization algorithms, generally back-propagation. And the goal if we have some fitness landscape (which could be a set of weightings for a neural network for instance), the goal is to find the low point in some fitness landscape. Here is a 3D one for visualization purposes. These can be much higher dimensionality than just 3D. And then as far as quantum annealing is concerned, there’s a classical computing version analog called “simulated annealing” which is realized by exploring that state space using randomized perturbations, or thermal jumps, which are gradually stepped down in intensity. So the quantum computing equivalent is what is realized with adiabatic computers and it’s called a quantum annealing. And in addition to the thermal jumps for exploring the state space it also makes use of the superposition for what’s called quantum tunneling between points.
Now if we want to explore applications beyond quantum annealing, we’ll need a universal quantum gate set. And so let’s just quickly talk about what we mean when we talk about a quantum gate. Now a gate in classical computing takes an input of 0’s and 1’s and forms an output of 0’s and 1’s. The superposition of the qubit as a state is a little more complex. And the actual realization of the application of the quantum gate is realized via linear algebra. The superposition is a vectorized state, and the application of a quantum gate is realized through the multiplication with some unitary matrix and it’s more -
- Can I jump in with a question and also give folks a chance to ask questions before we go from the qubits to some more complex aspects. I guess my question is like fundamentally is a little bit more basic, like is the qubit is, how do you articulate like what the qubit is a physical manifestation of?
Sure so there’s different architectures that are competing for adoption, and basically each one of these is some system generally at the atomic scale or so, that has some quantum properties. And it’s a system that we can — what makes for a good qubit is that our ability to interact with it, and to measure it, and to form gates to manipulate the superposition.
- Okay so qubit doesn’t correspond to a specific single thing, it can be implemented in several different ways, it’s just some you know where we’ve isolated some kind of quantum property that is probabilistic in nature, like some electron where we kind of know where it is probabilistically or something like that.
Well the analog to classical computing is a bit which can be realized either in an integrated circuit or as a transistor — which has a 0 and a 1 state. So all this is, is think of it as just a kind of a quantum transistor, that it allows for once you measure the state, it collapses that superposition, and it realizes some classical state of 0 or 1 — but prior to measurement it’s in a quantum superposition.
- Ok any other question? Either via voice or chat or slack meetup Channel.
All right, cool, um so we were talking about quantum gates and the application of the gates realized — basically the way to picture the application of the gate on a single qubit is we talked about the Bloch sphere representation, which is a way to visualize the superposition. And so as you apply a single qubit gate what you’re doing is taking that superposition which is represented as the point on the exterior of a spherical shell, and rotating it around one of the axes. And so that’s for a single qubit, and then as we incorporate multi-qubit gates the interactions and entanglements become a little more complex. And it’s through the application of these quantum gates that we can implement our quantum algorithms, and realize entanglement and things.
So we have sufficient vocabulary now to talk about the quantum model of computation and it’s, I have here just a representative circuit diagram, and these are read from left to right. Basically the left side of the diagram represents an input of qubits prepared to some classical state. In this case we prepare the qubits, and then the application of the gates are a series of unitary matrix transformations on the vectorized superposition, which generate interactions and entanglements between the qubits. And then it’s the right side of this diagram the dials here represent the act of measuring the state of the qubit, and through the act of the measurement the superposition of the qubits collapse, and so we lose some information in the act of measurement. As a result the actual output of a quantum algorithm isn’t going to give you an answer with 100% certainty, it’s going to follow a probability distribution. And so there’s a requirement for some replication of the steps of calculation until you reach satisfactory probable certainty.
- NIST Quantum Zoo
So I’m just going to highlight a few examples of quantum algorithms just to give you a flavor of the type of the most fundamental. These will come up a lot in the literature — so that if you’re reading more about I’m sure you’ll come across these. One of the earliest algorithms to be discovered was called Shor’s factoring algorithm, and this is an application of factoring numbers (which has applications in cryptography). I’m not going to explain the workings of the algorithm but just to give you a flavor of how it goes about doing that, it makes use of a quantum version of the Fourier transform which enables phase estimation which is used in that factoring operation. So that particular algorithm allows for an exponential speed-up versus classical computers — problems that would take a classical computer some amount of time can be exponentially sped up using quantum resources.
Another example is Grover’s search algorithm, which is a type of database search application. And I want to be careful how I describe this, because Scott Aaronson is known to hammer home the point that quantum computers don’t just work by putting everything in a superposition and picking the right one, but there’s a kind of amplitude amplification of the state space such that as you have your database put into a superposition the algorithm works to reinforce the solution, and then cause the other portions of the database to interfere with each other. And it’s through that application that you realize a speed-up in a database search — which is not actually as much of a speed-up as Shor’s factoring, it’s only a quadratic speed-up.
And then another important category which is a little more recently developed is called the Harrow-Hassidim-Lloyd algorithm. This has applications in linear equation solving. Basically, basic linear algebra, so it it has wide applications as well. And there’s many more algorithms out there. A good resource I found if you want to learn more about the types of algorithms that are available is a page published by NIST called the Quantum Zoo. So if you just type that in the search engine it should come up.
So we’ve talked about quantum computing, we’ve talked about algorithms, now we’ll just kind of jump up a few levels of abstraction and talk about computational complexity, and which basically helps to illustrate what exactly it is we’ll be able to achieve with quantum computers. So computational complexity is a way that computer scientists categorize and classify the types of problems that can be addressed by computers. And this here is a subset of some of those categories that are studied, and it illustrates the type of problems that can be addressed with classical computing resources as well as quantum computing resources. This diagram can be read from the bottom to the top as increasing resources required to address a problem, and basically it describes the scaling of resources that are required with increasing problem complexity.
So some of the important classes, I won’t talk about them all, but P stands for the polynomial class. And this is the class of problems that a classical computer can solve with scaling in polynomial time with increasing problem complexity, which is for example the type of problems that you can address using your personal computer. Another important lattice is NP, which is non-deterministic polynomial. And these are a class of problems that can be, they require exponential scaling of resources to solve — but once you have a potential solution, checking and confirming you have the right answer, it only requires polynomial resources. And so that kind of quirk of the NP class has led some to speculate, well maybe P and NP are in fact the same class. And it turns out all you need is one example of solving an NP problem (correction: NP-complete problem) in polynomial time, and you can prove that’s the case — and there’s even a million-dollar prize if you have a spare weekend some time to give that a shot. The smart money is that it’s it’s probably not the case but I don’t think anyone’s been able to prove it or disprove that conjecture with certainty.
And then as we get to quantum computing the BQP set stands for those class of problems that can be solved scaling with polynomial resources using quantum computing resources. And I guess what’s being illustrated here in some of the key takeaways is that the polynomial set is a subset of the BQP set, so basically any problem we can solve with classical resources we can also solve with quantum resources. That’s not to say we would — the overhead of error correction and stuff for quantum computers is much higher, and so generally if you can solve a problem with classical resources you’re probably going to do so. But another key takeaway is that there’s more problems that can be addressed with polynomial scaling of resources using quantum computers than are available to us with classical resources. Another important takeaway is the dashed line representing the boundary of this BQP set is illustrating that the actual boundary of this set is not known with certainty. And there’s still a lot of research being conducted of the types of algorithms that are available which may or may not change this distribution. So we talked about is P equal to NP, some people have wondered is BQP equal to NP. And I’ve seen some demonstrations that Grover’s search algorithm, which is only a quadratic speed-up vs. classical computers, is optimal — meaning that that’s probably not the case — that the BQP is probably not going to be equal to NP.
So if you’d like to try to implement some of these algorithms, some of the resources available in the commercial market there are resources available now. Rigetti and IBM both have gate based quantum computers which target universal computation. And then D-Wave, which we talked about earlier as a special purpose computer for adiabatic — and they each have their own API and cloud service as well as lots of educational materials. So that’s good resources to learn more. And then there’s a lot more platforms under development that are not yet available on the commercial market. Some of them include Microsoft, Google, Fujitsu, Xanadu, Intel, and IonQ. Some large companies and startups as well.
- Quantum Computing Since Democritus — Scott Aaronson
- Quantum Computation and Quantum Information— Michael Nielsen and Isaac Chuang
- Quantum Information Science — edX online course
- Wikipedia
- The Dreams That Stuff Is Made Of — Stephen Hawking
- Quibbling Over Qubits
Some literature I’d recommend if you’d like to learn more: a very accessible work is Quantum Computing Since Democritus by Scott Aaronson. It addresses quantum computing as well as some considerations for computational complexity like we talked about. And then kind of the authoritative textbook treatment is Quantum Computation and Quantum Information by Nielsen and Chung. And that is very much kind of considered the bible of the industry. There’s an online course that’s very good it’s on the EDX platform, called Quantum Information Science. It’s offered by MIT — it’s a series of courses it’s worth checking out. Wikipedia is a good resource if you’re introduced to some new vocabulary. And then Stephen Hawking, if you’re interested in the history of quantum dynamics and the science behind it, he collected a series of papers in a book called The Dreams That Stuff Is Made Of — it’s a really neat resource. And then I blog on Medium, and this talk was actually an adaption of a paper I published in 2016 called Quibbling Over Qubits, and if you’d like to learn more that’s a good place to check out too.
So before I jump into Quantum Machine Learning are there any questions with respect to quantum computing in general?
- Just an observation, this seems to be a difficult area to learn.
Right I mean it’s not something you learn overnight but it’s just a matter of using the right resources. If you follow popular press accounts you’re not going to learn anything. I mean they all say a thousand different ways that a qubit is a bit in superposition, they won’t tell you much else, so it’s just a matter of getting your hands on the right resources.
- Is there something you suggest, like something for dummies?
Well I mean the Quantum Computing Since Democritus is a very accessible work, and there’s also a lot of public lectures out there that are on YouTube: Scott Aaronson, Michael Nielsen — John Preskill I think has some lectures out there. And yeah there’s not a lot of really very good that I found kind of introductory resources like targeting undergrads maybe. But you know if you’re willing to spend a little time and effort, the information is out there is just a matter of finding it.
- So is the assumption you need to understand advanced mathematics before you understand quantum computing right?
Yeah I mean it’s linear algebra. It’s vectorized matrices, subject to some constraints. And it’s — I’m oversimplifying.
- Physics required?
It helps. I mean like I said I kind of took it for granted that some of the concepts of quantum dynamics you know. There’s a lot of good introductory material for quantum dynamics, and if you’d like to learn more about, just you know googling things — like the dual slit experiment is, there’s a lot of good resources, and that’s like a really illustrative type of experiment to kind of see what kind of strange properties are exhibited by quantum systems. I think that starting / getting out of the starting blocks, understanding superposition is something that you just have to get over when you’re starting to think about quantum things, and like why I tried to start with the Bloch sphere because it’s the most intuitive way I found to think about what it means when we say that a qubit is in superposition — because there’s these range of states, as you get towards the top of the sphere your classical probability of collapsing to 1 state gets closer to 100%, and as you get towards the bottom of the sphere your probability of collapsing to the other gets, so it’s a it’s kind of a quantum analog of classic probability — expanded for additional dimensions. It’s like a classic probability — but it has a positive or negative values as well as real and imaginary components.
- And all of the implementations that you mentioned for this Bloch sphere, is that fundamental to all of quantum computing? Are there variants of the Bloch sphere that depend on the underlying physics and properties of at the quantum level?
So I gave an illustration of one set of universal quantum gates, and this is not the only set of universal quantum gates — it’s possible to have a much smaller set of gates that you can still achieve universal computation. But in practicality you want to make use of — I’m not really an expert on quantum gates quite as much but there’s more than one potential set of Universal gates. And you know with the adiabatic computing version you don’t have a universal set, and that’s why you’re kind of subject to just specialized applications than with the architectures that are being offered by the likes of Rigetti and IBM. They target universal gate-based quantum computation.
- Okay and where is the vector come from? Is it analogous to in classical computers, you know, a bus or some — you’ve got n qubits wide you know that’s your your bandwidth, your bus size?
Well here the dimensionality of your system is a function of the number of qubits, and the Hilbert space is how you describe the dimensionality, such that one qubit has possible states after measurement at 0 or 1 so that’s a two dimensional system, and then for every additional qubit you incorporate, you increase the dimensionality such that 2^n gives you the dimensionality of the system. So it’s it’s more of like an informational capacity, as far as the transmission of quantum states through a channel, and in a circuit the physical realization of that I’m less an expert on. Ok well the 2^n is still, I mean that’s just the capacity of some number of qubits in terms of binary representations. Yeah it’s the dimensionality and like the Bloch sphere, which is a single qubit in superposition, even though it’s like a 3D picture, because your superposition is constrained to the outer rim of the sphere it’s actually a 2D system, because it can be described as with just two angles. And so the Bloch sphere is a two-dimensional state.
- Quantum Machine Learning — Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, & Seth Lloyd — Nature volume549, pages195–202 (14 September 2017)
- Slides are based on the preprint available on arXiv [link]
Okay well let’s go ahead and jump on into the second half of the talk. I think this half is a little bit shorter, but this is an overview of a recently published paper which addresses the intersection of quantum computing and machine learning. It’s a paper by Jacob Biamonte as well as Wittek, Pancotti, Rebentrost, Wiebe, and Lloyd. And I want to put an asterisk that I based my review — partly to avoid copyright issues as well as stuff like that, as well as I don’t have access to university library — so I based my review on the preprint that’s available on arxiv. Which is actually a little outdated I’m sure. The actual paper was published in September of 2017. It’s a rapidly progressing field, I definitely highly recommend if you have professional interests to check out the published version that was in the Nature Journal. That being said I’m going to include in my slides numbering for citations. If you’re interested in reading more about any of this specific subject matter the numbering convention of the citations is based on the arXiv preprint, which is there’s the number here if you’d like to see the preprint. Also another asterisk is I took a little more of a creative license in the slide preparation here so there’s a little more, you know, illustrations that aren’t necessarily directly related to material that are just being provided for color — so I hope you’ll grant me a little leeway from that standpoint. But I’ll go ahead and jump right on in.
The paper is meant to address the intersections of quantum computing and machine learning, and so one of the key points of the paper is that that the interface of quantum computing and machine learning actually goes in both directions, in that using classical machine learning resources helps us to understand and control quantum systems, and then parallel using quantum computational devices it gives us the ability to enhance the performance of machine learning algorithms for problems beyond the reach of classical computing.
So this is a really cool venn diagram that’s included in the preprint that I don’t think made it into the final published version. I’m not going to spend a lot of time on it, I just wanted to call out that it’s a really neat visualization. And the idea is that the categories on the left represent categories of machine learning and the right represents quantum information processing and then the intersection of quantum machine learning is the subject matter addressed by this paper. I’m not going to cover the entirety of the paper, it’s definitely more than this time slot would allow, I’m just going to offer some highlights. If you’d like to learn more I’d suggest checking out the paper. What I will cover is I’ll just offer a quick flavor of classical machine learning methods being applied to quantum systems. I’ll talk about using quantum computing devices to enhance our machine learning algorithms and then I’ll also talk about some of the frontiers in quantum machine learning as addressed by the paper.
So first we’ll talk about using classical machine learning on quantum systems and I’ll just provide one example just to give you a flavor. So when a researcher is studying a quantum system it’s generally in a lab environment, and the goal is to design / develop / benchmark / and control that quantum system. And quantum computers is the example we’ll focus on. And just as a reminder, I’m not sure if I really addressed this with sufficiency in the first half, is that the whole idea of quantum computers is that once we reach sufficient scale and implementation we’ll be able to achieve quantum supremacy, which is basically the fact that will allow for exponential speed-up versus classical computers in select applications.
So as far as using classical machine learning methods and to develop quantum computers one of the key areas is in the design of quantum gates. We talked about the gate implementations in the first half of the talk, and it turns out that the actual physical realization of these gates is a challenge for quantum computers. And it’s being supported with the use of supervised learning techniques as well as reinforcement learning techniques. So that’s an example of classical machine learning algorithms improving our quantum systems.
So now we’ll talk about quantum enhanced machine learning, and this is obviously the meat of the paper and I guess the purpose of the meetup. So the paper addresses two ways that quantum mechanics can enhance machine learning. One is that quantum computers can perform machine learning algorithms for problems that are outside the reach of classical computers. And the paper gives examples in big data techniques, it gives examples in adiabatic optimization, as well as examples in Gibbs sampling and I’ll talk about each of these going forward. The paper also addresses some other things that I’m not going to address but I just want to call out that it’s in the paper. It mentions that some of the techniques developed in evaluating quantum systems can improve machine learning algorithms, and it talks about tensor networks and renormalization techniques and bayesian networks — so those are if you’d like to learn more those are in the paper and it’s just an interesting tidbit that some additional avenues of using quantum techniques can enhance our machine learning.
So for the example of applying quantum computing resources to Big Data problems the paper offers two ways to realize quantum speedups in the performance of big data problems. One is with respect to query complexity — basically we talked about earlier the Grover’s search algorithm which is a way to provide a quadratic speed up for some database search application, and through the application of Grover’s search algorithm the number of algorithmic queries to an information storage medium can be reduced. And then another way that Big Data speed ups can be realized is through gate complexity, such that the number of elementary gates to obtain your results, and that’s realized by a type of quantum technique for finding matrix eigenvalues. That’s not to say that the application of big data with quantum computers is simple.
It turns out the key challenge is that before we can perform a quantum computation on some set of big data we actually have to load the state into the quantum computer, and this is actually what can dominate the cost in the algorithm. And so the paper offers two ways this can be addressed, one is using a pre-trained generative model, and then it also talks about loading the data into a low depth circuit for accessing the data using quantum RAM (QRAM). And there’s a citation there.
So we’ve talked about big data, let’s now talk about the special-purpose application of adiabatic optimization which we talked about in the first half of the talk. So adiabatic optimization, also known as quantum annealing, is basically a way to address a constrained optimization problem, and in so doing it’s restating the problem in the form of an Ising model — which just a quick flavor of what we mean when we talk about an Ising model, it’s a way to model a set of elements with pairwise interactions of spin states subject to excitation by temperature. Just like a magnet if you heat it enough it loses its magnetism and parallel if you lower the temperature it reaches its low energy state, and so an Ising model is just a generalized version of that pairwise interaction of spin states. And adiabatic optimization is a way to embed an optimization problem into a physical system such that once it reaches that low energy state that is stores the problem solution.
And the operation of adiabatic optimization is realized in two ways: via thermal fluctuations as well as by quantum tunneling which takes advantage of the superposition in state space of the fitness landscape.
So the paper gives a few examples of some systems that have been demonstrated using adiabatic quantum computing. It doesn’t go in a lot of detail it just kind of sites you to external resources and so I’ll give it the same treatment. But some of the examples that it offers include boosting algorithms, natural language processing, anomaly detection, probabilistic graphical models, manifold learning, a maximum entropy model — and so these are all examples of the types of machine learning applications that have been addressed with adiabatic quantum computing. And this is current as of like 2017 I assume.
- Does the paper note any specific results for any of those?
It just kind of, just illustrates hey here’s the type of applications that have been addressed using adiabatic resources, so I’ve included citation numbering here so I guess the intent is if you’d like more about any of these specific applications this gives you some some channels to do so.
- Can you give specific examples of problems that can’t be solved by classical computers that can be with quantum, do you get to that in the slides? Do you have a specific example that comes to mind or do we even like have we characterized the problem enough to really articulate that yet?
Yeah I’m gonna get some more, I mean in the big data techniques what’s being demonstrated is that there are speed ups of performing big data applications, and so those are speed ups that are not available with classical resources, and then yeah I’m gonna get to some more of those.
So where we left off we were talking about adiabatic computing in applications in machine learning and so I’ll just talk further about this adiabatic quantum annealing operation. And one important point is that in theory quantum annealers should provide a global minimum of your fitness landscape, and it’s in theory that the output would be a global optimum. In practice there’s a number of implementation issues that deviate from the theory and so in reality after you perform your adiabatic optimization you end up with energy levels that follow a Gibbs distribution, which is a type of probability distribution. So Gibbs sampling is a way using classical resources, using Markov chain Monte Carlo techniques, to evaluate and sample from that distribution to model that equilibrium probability distribution. And then it turns out there’s also a quantum equivalent of that sampling technique called quantum Gibbs sampling, and through that it’s possible to evaluate Gibbs distributions.
So this Gibbs distribution it turns out is useful and relevant to Boltzmann machines. And just a quick rehash, Boltzmann machines are a type of neural network architecture that instead of using a deterministic activation function (like logistic or RELU for instance) the activation functions are stochastic units such that if you have a output of neuron it won’t be a defined value, it’ll be subject to some probability distribution. And then Boltzmann machines are generally trained using a Gibbs sampling technique which we just talked about, so they can be trained using classical resources. And it turns out they can also be trained using adiabatic quantum computers for training Boltzmann machines.
However there’s one key difference and that is that with classical methods training Boltzmann machines you’re limited to restricted Boltzmann machines, which is subject to, although you’re allowed for interconnectivity between adjacent hidden rows, restricted Boltzmann machines do not allow for interconnectivity within the neurons within the same row. Then one of the key findings I thought it was of importance was, with quantum Gibbs sampling you will now have the ability to efficiently train deep networks of non-restricted Boltzmann machines. And so that means that, we basically have a whole new class of neural network architecture using quantum resources that weren’t available to us previously, which strikes me as a big deal. I don’t know first hand, you know, some of the applications, but anytime you have a whole new class of neural network architecture, that just seems like a big deal.
So we’ll talk about some of the frontiers in quantum machine learning. The paper cites a few additional experiments that have been performed using quantum resources and machine learning applications. The last set of experiments we listed were all adiabatic computing. Some of these make use of gate based computing methods. And again the paper isn’t going into a lot of detail about the actual realizations of these demonstrations but it cites external resources if you’d like to learn more. And it illustrates examples like speaker recognition, chaotic time series prediction, classifiers, and input encodings, as well as things like simulating a chain of traps ions and regularized boosting methods.
So we’ll close by just talking about some of the frontiers. Quantum computers can outperform classical ones in some machine learning tasks, but kind of going back to the first half of the talk we talked about the computational complexity profile and how the boundaries of the bounded quantum polynomial set (the BQP set) we don’t know with certainty. And that’s kind of what’s being discussed here is that the full scope of the power of quantum computers is not known with certainty. So there’s still research to be done and still learning to be done.
And then another highlight that I took away is that one of the key points of the paper is that quantum computing and machine learning will coevolve, and that as we improve our machine learning it’ll help us to design and evaluate quantum states and quantum computing, and in parallel as we improve our quantum computers they’ll be enabling for certain classes of machine learning.
- Deep Learning With Python— Francois Chollet
- Deep Learning — Ian Goodfellow, Yoshua Bengio, and Aaron Courville
- fast.ai
- arXiv cs.AI
- Nature Machine Intelligence
- From the Diaries of John Henry
Some additional resources I’d recommend if you’d like to learn more from them (just to give me a chance to highlight some books I liked from the machine learning realm) — Deep Learning With Python is written by the architect behind the Keras framework Francois Chollet and it’s a very accessible work that balances kind of considerations for the beginners as well as some considerations for researchers and so it’s a balanced work that’s well done. For a kind of authoritative textbook treatment everyone hear has heard of Deep Learning by Goodfellow, Bengio, and Courville, it’s still state of the art for the most part. And then obviously fast.ai, and that’s a good online course. I have found that just at least dipping your toes into the arXiv cs.AI stream for computer science / AI from time to time is a good way to get exposure to papers you might not see otherwise. And then this paper was published in the Nature journal and Nature is actually coming out with a dedicated machine learning journal which will start in January of 2019 (Nature Machine Intelligence) so given their treatment of quantum computing I have high expectations for what that’s going to look like. And then I blog as well. I’ve done a lot of writing on machine learning. The first kind of dedicated address of the topic was a post called From the Diaries of John Henry so if you’d like to see more that’s a good resource.
And that’s all and so covered a lot of ground any questions?
- Questions for Nick? You definitely covered a lot of ground. There’s a conversation on slack about how many drinks we’re going to need to after this and going to take for this stuff to sink in.
Cheers.
When a person can no longer laugh at himself, it is time for others to laugh at him. — Thomas Szasz
*A thank you is owed here to Sam Charington for providing an opportunity to share. The podcast This Week in Machine Learning & AI (TWiML & AI) has proven a consistently high quality exploration of machine learning industry insights, and for those looking to build domain expertise the podcast and associated meet-ups are extremely worthwhile channels to do so.
*For further readings please check out my Table of Contents, Book Recommendations, and Music Recommendations.
Books that were referenced here or otherwise inspired this post:
Feynman Lectures On Computation — Richard Feynman
QED — Richard Feynman
Feynman and Computation — Anthony Hey
Quantum Computing Since Democritus — Scott Aaronson
Quantum Computation and Quantum Information— Michael Nielsen and Isaac Chuang
The Dreams That Stuff Is Made Of — Stephen Hawking
Fashion, Faith, and Fantasy in the New Physics of the Universe — Roger Penrose
Deep Learning With Python — Francois Chollet
Deep Learning — Ian Goodfellow, Yoshua Bengio, and Aaron Courville
(As an Amazon Associate I earn from qualifying purchases.)
For further readings please check out my Table of Contents, Book Recommendations, and Music Recommendations.
