Fred Chong: Closing the Gap Between Quantum Algorithms and Hardware

okay so good afternoon and welcome to another of the Yale quantum institute colloquia talks we're very glad today to have Fred Chong visiting and he's been here for a couple days and meeting with people in variety departments ECS Applied Physics and so on so fred is the seymour goodman professor at the computer science department at university of chicago fred is trained as a computer scientist and as a computer architect but he's been may be lured over to the quantum side let's say and is doing more and more quantum things these days he's the lead investigator of a new 10 million-dollar NSF project in in the division of computer science called epic which is enabling practical scale quantum computing with several collaborators at Chicago and elsewhere Fred got his PhD from MIT and was first on the faculty at UC Davis then he spent some time at UCSB from 2005 to 2015 before moving somewhat recently to Chicago and he's won several different awards his research interests span computing quantum computing multi-core and embedded architectures computers security and sustainable computing and you know I think we're very glad to have Fred here some of us have known him for a while and been chatting with him and find more and more in the field of quantum information that there's things we can bridge between let's say hardware and software and what Fred's gonna do today is give us this talk which is being recorded for future use on closing the gap between quantum algorithms and hardware using vertical integration and code design so thanks a lot for coming Fred it's been a wonderful visit and we're looking forward to this and this talk is sponsored by the quantum Institute and also by the Department of Electrical Engineering and computer science so thanks thanks a lot so what day today is I'm going to talk about what we can do together computer scientists and to close what I'm going to describe as a gap between the algorithms that we want to run and the machines that we expect to have in sort of the foreseeable future and and this is the subject of this large NSF project that we're just starting which is called epic and and it's it's and it's sort of that's a sort of a microcosm of what we're trying to do in which we have you know algorithms people from MIT working with computer scientists from UChicago with also some technology people Dave Shuster at UChicago and Ken Brown at Duke and and many of the ideas that I'll talk about today come from discussions with with those team members all right so most of you are probably somewhat familiar with quantum computation but I just have to do a couple slides of motivation you know we're looking at this problem because this is sort of an exciting time for quantum computing and from sort of a computational point of view you know quantum computation is interesting because it is sort of the only technology that we know that can scale computation potentially exponentially with the number of devices that we build and that can fundamentally change from a computer science point of view what is computable or tractable for computation and that you know being able to solve some of those intractable problems in specific areas can be very interesting for things like chemistry simulation and optimization in particular in the near term and you know practically that might lead to a sort of impact such as you know better materials better things like photovoltaics even better processes for things like nitrogen fixation you know we're also interested you know from in the computing sort of industry and computing world you know we have this phenomenon where traditional CMOS scaling Moore's law Dennard scaling those things are sort of petering out a little bit for us and so you know this has a potential of giving us at least in very specific instances a to scale and accelerate things and also studying quantum computation also produce a sort of as a healthy competition with classical computation so you know the best way to get a lot of classical algorithms people to work harder on their algorithm is to have a quantum algorithm it supposedly is better right and that has in fact led to interesting advances in the past so you know we've been working on this problem for a while and and I would say we've been working on this problem from a fairly theoretical point of view looking at sort of very far future machines with fairly perfect devices and lots of devices but we're sort of into this interesting time where in the next few years we expect to see real machines that you know are of non-trivial scale and we've actually struggled a bit for a while we've told you before a while to figure out you know how do we distinguish those sort of theoretical ideal machines that we used to think about with the ones that we're gonna be thinking about for the next five to ten years and john press kill has this nice sort of term that we like which calls the new noisy intermediate scale quantum computer or Niska sounds a little bit like risk computing and it's also interesting that you know that that denotes that we're sort of in this privileged time where we you know really might be able to demonstrate a computation which is classically not computable and that's one of our goals in our project and you know here we see some of the machines that have been announced that are out there they're mostly under test so we're still seeing how well they're going to work but the indications are that we're in a position where we're gonna have you know maybe 100 cubits of some sort in the next five years that we can do some computation on right maybe more if we're lucky but even with that sort of nice point in history that we're at we have a fairly large gap between the algorithms that we're familiar with and the machines that we expect so you know the algorithms that are probably most well-known Shor's algorithm for factorization and Grover's algorithm really you're looking at running on like on a hundred thousand or a million quantum bits right and this is for this scaling graph is for trapped ions but you know you see that there's sort of a large gap of many orders of magnitude between those sort of well-known algorithms and the machines that we might expect even going you know in ten years into the future right so you know we're sort of now in this regime where in the algorithm space there is a lot more attention to these sort of near-term algorithms or heuristic algorithms quantum simulation quantum chemistry quantum approximate optimization algorithm so these are heuristics that basically minimize energy right but you see that even these they're still sort of a gap here and that's sort of the point of what we think we as a project and the community we're trying to build we would we would like to try to address and so we'd like to address this sort of further gap with this idea of sort of hardware software code design right basically bringing the software closer to a model of what hardware really looks like from a computer science point of view actually breaking abstractions that make it easier to write the software but make it less efficient and so you know we have the stack from algorithms down to programming languages compilers architecture some model of the devices to the actual devices and this stack historically has been sort of very weakly connected right we actually have the stack in some form for these ideal devices but what we'd like to do is to really look closely at this redesign it for this near term or sort of a misc era so we have this very aggressive goal you know our goal is that we're gonna build a stack and make the translation from algorithms devices a hundred to a thousand times better than it is right now okay we actually think we could sort of do this because the base line isn't that great right now but mostly you know these layers of abstraction make you make it so that you do things very inefficiently and what that does is a factor of sort of a hundred to a thousand would translate into some large number of years of machine improvements right so we're trying to do is shift this intercept point well ideally in the next five years you know in the lifetime of our project but also ideally because it's sort of some proof of concept that this is an interesting thing to do would be a good thing in the next five years for the field in general just to be a little more precise you know so I plotted you know number of qubits which is sort of the number you always see in the press and when we announce machines but more precisely we're really talking about the space time product which is essentially the number of qubits times the number of gates right IBM would call this the quantum volume and so if you have a machine that has a two-bit GAE error of ten to the minus three that means that you can run one gate one bit with a thousand gates all right well sort of eight it's two qubit gates but but you've got 32 bits right you could only run 32 gates on each one right or you could have a thousand cubits and we're only run one gate on each one so the volume is very can be very restricted right and ideally I think Google says you know they're optimistically they'd like to get here 128 qubits thousand gates on each one right and if we had that really then we could probably do something interesting on that machine right but the reason I bring this up is because when I talk about addressing this gap I talk about increasing the efficiency both in terms of how many qubits we use and how many gates we use or sometimes even trading those two off right so probably most of you are somewhat familiar with this but I'm just going to sort of establish a baseline for those not familiar with quantum computation you know when we talk about a qubit we talk about some sort of bit representation that is implemented in some sort of quantum physical device and we talk about a superposition of zero and one and we have this notation which it uses these probability amplitudes and every additional cubit that you add all right doubles the number of states that you're dealing with which is no different than the classical case right you can represent an exponential number of states with every cubit or every bit classical bit in the cubit space these are potentially in super positions so you have all of those possibilities simultaneously right and what you're doing is you're manipulating these probability amplitudes such that you're doing some sort of useful computation and you know sir colloquially we might call that quantum parallelism or some form of parallelism which gives you an exponential number of states to work with which you know theoretically gives you some computational power right but the hard part is of course when you measure this system collapses so it's hard to come up with algorithms copses to one state it's hard to come up with algorithms that you do some useful computation in some useful amount of time right I'm often asked from sort of domain scientists and people want to use quantum computation you know what is a good quantum application and sort of there's some interesting implications of you know how quantum computing works all right the first one is that we we generally have a bit of an i/o problem right so input and output is fairly expensive and in fact you you want to put in a small amount of data in the form of a few bits and have that become an exponential amount of computation right that's what a quantum computer is good at right for example you'll often hear you know the other popular buzzword these days is big data everyone says well can you put big data and quantum computing together probably not because if you had to put an exponential amount of data into the machine then you won't get any advantage doing the exponential amount of computation right so you need this sort of compact problem representation and the examples that we have are things like inverting at a complex function modeling some small molecules or small graphs doing optimization on those things so those are sort of high complexity computations that come from a very compact problem representation we also because the the devices are unreliable the algorithms tend to be probabilistic we need an easily verifiable solution typically you know so Shor's algorithm is easy to verify because you just multiply the two things together and you see if that's the product things like modeling the lowest energy state of a molecule may be harder to verify you may have experimental data you may have the best-known classical solution the other sort of interesting thing that's happened in the last few years is that we've come to a much stronger reliance upon this model of a classical quantum co-processing right this is actually very helpful for our situation so you can take sort of the best known classical algorithm say for modeling quantum chemistry and you run that on the biggest classical supercomputer you can find and you get the best solution you can and then use that to build the starting initial sort of sauce or initial condition for the quantum algorithm then you run that for a very small time on your little quantum computer and then you hope that it improved the estimate and then you hand it back to the classical one and you just go back and forth right and and this is actually gives us a very nice situation because you know we're always competing with the classical machines but in this case we're starting from the best classical solution so if there's any improvement that can be had with sort of the quantum sort algorithm and model on a small machine then it gives us a much better sort of chance of improving of computing something that wasn't computable before right and it's also the case that we don't have a lot of good quantum algorithms because they're hard to come up with so we have a small number of kernels sort of algorithms that we have to exploit in order to do anything you know sort of computationally advantageous so what I'm mostly going to talk about today is how does the software model the hardware there's also sort of the other direction you know how can the hardware change to be better for the software and we have a sort of stack of tools which is analogous to what we might in the classical world called circuit synthesis which is essentially going from some high-level language like C and compiling all the way down to hardware okay so we do this in the classical world all the time for either what are called application-specific integrated circuits or FPGAs and it's interesting because the problem is more restricted and in some ways easier or at least more optimizable for quantum machines and quantum alguns because we typically know a lot about the program and the inputs and the characteristics of what we're trying to run because if they're very small programs as you know we we might compile a program specifically for quantum chemistry to model a specific molecule so that we basically know everything about the program which interestingly for us in the past meant that the compiler quickly ran out of compute and resources and memory resources on a classical machine so we we might even run the compiler on a supercomputer basically so that because we know so much about the program in the classical case there are enough unknowns that we sort of run out of things to optimize in the quantum case since we sort of know everything we can do all kinds of classical compiler optimizations to the nth degree okay other things that are interesting you know a little different from the classical case we have to manage errors and the precision we desire it's actually less different than you would think and I'll get back to this because classical machines now that they're often energy or power constrained are starting to do this so classical software tool chains already have this capability so we can leverage those techniques and of course we're sort of in this interesting time you know which is a little bit like the 1950s in classical computing where resources are super scarce right every bit and every gate is is really scarce and so it was interesting what I could give this talk to all computer scientists I like to say you know you ever you ever look at the history of computer science and you think if I was only alive and 1950s I would have written so many papers and done so much stuff because it was all new well that's where we are in quantum computing right everything is new right so this is a simple model that we have for our software you can think of quantum can the quantum commedia vice is sort of like a coprocessor or like a GPU essentially and so to us it sort of looks like this right we have a high-level language see like language that we call scaffold it compiles to an assembly language of basically quantum gates and then that goes into a program that sort of run concurrently on a classical control processor and a quantum coprocessor in the real case this is probably a little more complex but in terms of what the compiler thinks of this is what it does and it's a lot like you know you can pilot program for GPU it's the same thing you sort of decompose the program the classical processor is controlling the GPU that's true yeah so what so somewhere in here there's something that produces microwave pulses but the compiler thinks of this as just sequencing all that control so some sort of compute power that does that and then somewhere like it along this boundary is the low-level control so in fact our compiler actually doesn't produce the pulses but we then feed into some other toolset like IBM's quiz kit or actually Dave Shuster has his his set of control software so so we basically just feed into somebody else's control so although we are changing that so one of the ways to make things more efficient is to to not have that boundary to sort of directly create pulses for example so this is very too much about the details this is actually what our toolchain currently looks like it's 40,000 lines of code it's open source and but and it's sort of neat because it uses this like very well-established compiler technology called LLVM which is open source library from Illinois and a lot of sort of real compilers have been written with this infrastructure and what did does is it it does a whole bunch of optimizations pass by pass right so it does the one at a time that's to control complexity that actually isn't optimal because something you do here might affect something you do over there and you might have to go back around so one of the things that will make this more efficient as sort of collapsing some of these layers in the past we were compiling for programs that were say for a million cubits or something like that and we had to do this in order to make the computation manageable for each of these layers but if we're only compiling for 100 cubits or small program we might be able to collapse a lot of this which is something we're going to be doing this it's I sort of this is broken up into sort of the logical part which assumes sort of perfect gates at qubits and then then it goes to some physical stuff which it like maps the data to specific physical locations schedule things introduces error correction worries about communication things like that so this is what we have we're after gonna be spending a significant amount of effort in the next five years retargeting being this approach and this infrastructure from you know ideal giant machine to noisy little machine yes so it doesn't run anything it exists because it was it was written for the IRP quantum computer science project or a program and what it does is it does resource estimation so it counts the number of qubits and the number of cycles it would take to run on a hypothetical machine and it allows you to do the optimization zhan these large programs and sort of look at the effect of those optimizations so this is sort of for example what that compiler would do it did a whole bunch of sort of traditional compiler optimizations takes you know loops and unrolls them into lots of instructions and all kinds of sort of traditional things optimizing code that are going to run the classical machine it is you can think of it as pretty much the quantum machine I mean the classical machine all it's doing is keeping track of the ordering and the parallelism essentially so so this this like the scheduling all the operations we focus on the quantum part okay and then this just sort of shows you for a set of things like Grover's algorithm and Shor's algorithm the compilers able to expose a lot of parallelism so what these bars are is we have more and more quantum bits you know how much faster is the thing because the sort of traditional speed-up graph and and so this you know these things work but now we're gonna try to do a lot better and what I'm going to do and the rest of the talk is talk about what are the kinds of things we're going to need to do to target you know sort of realistic machines okay so it's a little bit of a grab bag of things so this is a paper from the Delft group very recently end of last year 2017 it actually it's a microarchitecture for a pseudo real machine right so you know for say a quantum dot machine and it actually won best paper which is sort of amazing that architects decided that quantum computing mattered probably because I got to vote but I was on the best paper committee but this the sort of the most interesting thing about this is that it's a very traditional architecture it's a it's a micro coded machine so it's just like lots of old classical machines and what it the interesting part of it is has this little boundary here where it queues up micro instructions so that it can play them back and there will be no gaps in the microwave pulses essentially so it sits as a synchronous asynchronous boundary and so that was sort of the innovation of this little architecture it was that it identified the fact that I had to run a whole bunch us figure out a whole bunch of stuff queue it up and then play it back at a speed that the the quantum control wanted it to come come at basically so so one best paper but it's not without shortcomings so I would say that this traditional approach and our traditional software stack is probably leaving too much on the table in terms of optimization okay and I'm gonna give you an example of some work that I'm doing with Dave Schuster which showed you why you should break this abstraction at for example architecture wise okay so so this is a instruction set architecture you know so that that thing had a really strict instruction of that architecture so here's a place where we might not want to do that so our compiler takes C code and compiles it down to two qubit gates which are essentially our instructions okay and then those two qubit gates are turned into week and them to somebod some other software that turns out it to microwave pulses right so here's the thing that we can do instead of taking two qubit gates in this set of results which are sort of preliminary we go up to five qubit gates right and what you can see is if we can directly generate control pulses for five qubit gates it takes less time right and so this is sequence length this sort of rough measure of number of pulses in time and we get about a factor of two improvement in the sort of number of pulses that we need achieve the five qubit gate if we did it directly versus a whole bunch of two qubit gates all right and then this this is for a QA o a so the optimization algorithm and the two red lines are for different parts of the circuit the best and the worst advantage that we got and the blue lines the average of for the whole day okay so this actually I think is we expect to get a lot better for one we could probably build this take this out to ten cubits and another is this actually the first set of results is very simplistic and assumes global interconnect and so if we went to modeling the IBM machine with a 2d mesh or something it's going to have a lot of swap gates and as they're going to take a lot of time and it turns out that this approach is really good at combining swap gates with other gates right so we're gonna get a pretty big advantage here I think and remember we wanted a factor of a hundred to a thousand ads you know so we need a lot of factors of ten or five or something like that right but this is one of them and what this does is it totally breaks several layers of our software right so instead of you know dealing with instructions we have to at some point start emitting just basically Big Unit Aries and then handing them to this optimal control so gradient descent optimizer essentially this is also very computationally expensive in order to push this to ten cubits and to look for good sequences we're probably gonna put this on a giant supercomputer so you're gonna use lots of memory and search lots of sequences here's another interesting thing it is it is it that's right that's right it's it is an exponentially complex thing and so we are sort of brute-forcing it as far well not really we're doing some gradient descent and we're doing it as best we can ironically QA Oh a essentially death gradient descent a sort of so we could use q aoa to optimize q aoa but you know there's a lot of these things are a little circular computer scientists love this they're like but why don't use the quantum computer to do that you know and and and that that is probably not something we're gonna do in the next five years but maybe ten years from now we'll be doing that right so like one of the things we're gonna be looking at is verification and everyone's sort of saying oh well fair cake verification is really hard you should really use quantum computer to do verification yeah of course assuming that the quantum computer was already verified and works right so yeah another interesting thing that we've been looking at it may not immediate or interviews because sort of novel and exciting it but I mean I'm a quantum computing way to view it's actually pretty simple right so when we compile these programs we use a lot of ancilla or scratch bits right and a big sort of culprit of that is something like you know we generate a lot of reversible arithmetic and you know instead of you know we start out essentially with NAND gates right and then we have to produce reversible gates and the smallest sort of reversible gate is 3 to put 3 out and so compared to 2 input one out there are a lot of scratch bits there right so you have all these scratch bits and it turns out well we could reuse them but we can only reuse them if we actually uncomputable so there's a direct trade-off between the number of bits we use and the amount of computation we do we do extra computation to get bits back and so we can either do the computation at the end or which doesn't really help us but we do it as we go or with some frequency essentially so the more computation we do the fewer bits that we use ok and so this is sort of our what we call quantum memory management right and so here's a here are a few applications that are once again so a lot of our results are for big applications so we have yet to see how well these will work for small applications right because this is our old infrastructure so in the old infrastructure we can see that we can save a lot of qubits that's the read so that's a fraction of qubits that we can reuse so we no longer need that many qubits so we get a very up yuto's over 75% qubit reuse in this boolean formula algorithm and not so good in this binary welded tree and this is like a Grover's that inverts sha-1 so and this is how much compute we need extra compute it's an extra number of gates that we need to get that savings ok and so remember what I told you was what's important is the space-time volume right so we just multiply these two graphs together I get this right and what you see is for this guy here it was not worthwhile right the space-time volume is bigger than what it was before but for this guy here actually it's pretty good right so it's up greater than factor of two improvement in space-time volume right so that's a this is another technique that we sort of and ice this is the extreme case we can actually uncomputable errs actually have to make gonna make a decision as to how much of this to do i had this organized this way because like the first one is like an architecture problem the second one is like a OS ish problem or memory manager problem I gave a talk at a place called S Plus which is architecture OS approving programming languages ok so here is an interesting problem that whenever we want to go from a sort of ideal machine to a physical machine we actually have to figure out where does the data go right physically and we want to minimize how far apart the data is and you know as and if machines get bigger and for example our modular and clustered in some way that we have to worry about how much communication there is between as we get further and further apart this is a very traditional problem in classical parallel computing and in even classical chip layout ok and we use things called graph partitions right these these use the spectral zero eigenvalue methods which basically minimize find the min cut of things and so this is a spectral community algorithm and so this is a hierarchical algorithm for for magic States and it's sort of tree based and you can see that we can the the the partition err can find some nice groups right and so if you if you map these on to clusters for example then you can see that the lot of edges inside they're not so many between there right and so that's that's a very traditional thing to do it's a little bit interesting it's complex because this kind of approach is very nice because it it it computes a global optimum of some sort it's just hearest ik but it but it takes advantage of lots of global information as to what the graph looks like but it tends to be static so what that means is say we take a function and we look at the graph for a function or I'm part of a circuit and we come up with a good mapping for it but within that circuit it could be that you know maybe the data could move somewhere or that the mapping doesn't have to be static and there's a so at Intel they have a recent paper where they used totally greedy dynamic approach right and it works well for small machines but there's some trade-off between how dynamic you want it and how globally optimal you want it right so the greedy approaches don't know anything about the global optimum the global approaches don't know anything about how things change right you can get something between that with granularity which is like you take a circuit or function you break it up into time steps and you have a different mapping for each one but then you have to minimize the amount of shuffling around between mappings or else it'll cost you right so that's something we're looking at there's a sort of weird complexity also like the last thing I showed you which is qubits can be reused okay but when they're reuse that means they suddenly appear somewhere in the circuit and then they have to when the next time it's where they're being used they have to move over to that place right and so the mapping actually is now affected by this dynamic more dynamic reuse thing right and so it's just sort of I don't know layers and layers of complexity and what you can optimize but that that is another thing we need to consider all right here's another one that's sort of at a lower level you know for you know in computer science one of the you know other big buzzwords is machine learning right and you know there are some interesting techniques that people have used to adapt to for example device behavior they're also sort of interesting techniques here so at IBM they were they've been doing some just sort of very simple statistical differencing of things right they run this a circuit at different gate times and expose different gate noise orders of gate noise and they subtract that out and so they get some really nice sort of better Fidelity's just by repeatedly running the circuit as opposed to changing their machine in any way what I find interesting here actually is is a lot of these machine learning approaches aren't so practical because they require a lot of training data and retraining and so one of the things that we've done for classical computing systems is use a combination of machine learning and control algorithms to dynamically adapt to varying system behavior without having to retrain right and so I think there's hopefully some leverage to be had in that kind of combination all right so now we get into sort of the funny part of this so we're in this sort of ridiculous bootstrapping situation right where you know we write code we have this compiler 40,000 lines of code we have application code we basically never run it on anything because we don't have a machine that's big enough we don't have simulators that are big enough right and so we're in this situation where you know if I if I took my code tomorrow and I ran it on you know the 50 cubed IBM machine and obviously it wouldn't work I wouldn't actually know which errors came from the software and which errors came from the hardware right and so this is actually sort of for us a large part of our project is this issue of formally verifying that the implementation of the algorithm is correct and the and the implication of the compiler and its optimizations are correct right we in the past have not had any of this stuff actually we were you know so asked to make the compiler but never asked to do this and I think it's a really important thing and it's it's a very interesting you know so there's a lot of this technology in computer science typically it's not used that much in industry or in practice but here we have like really strong motivation to use that right and there's also very interesting sort of theoretical fundamental question here which is what we'd really like to do is come up with some way of checking programs that isn't exponentially complex but we still want the program to have exponential computer computing power right so if we actually you know our MIT collaborators really like this problem because they're actually perfectly happy to have negative results so they're like well if we simulate this that means that we've proven that this isn't dust has no quantum supremacy right so that that's interesting to them from a sort of a practical point of view what we would really like to find is some way of of checking some restricted properties or partial computations that is either polynomial in time to check or maybe just exponential but with a smaller exponential than the the actual computation right and and and that's you know something that we're trying to explore right now and now part of that comes in other efforts that that that are related you know one effort that's related is just making the biggest quantum simulator you can write this sort of typically noise free simulation but so you know we have this like 45 qubit simulator that ran on some do-e giant supercomputer and then you have a few of these results for restricted simulations like random shallow circuits where they use a tensor contraction to optimize the order in which you simulate Tezz so that you use less memory and fewer operations so they could get to 49 there this is a very interesting area of research I have a student going up off to Argonne to sort of do HPC high performance computing tricks to you know make this 49 or something like that right you know just use the biggest machine do memory compression and all kinds of crazy stuff and make this push this up it's an exponentially difficult problem so it's only so far we could go but what's interesting about this is this defines the line between classical and quantum right so you're going to build a machine and you want it to be more powerful than a classical machine it has to be more powerful than this thing right and so this blind keeps moving a little bit you know we're probably pretty safe at 100 cubits I mean right now get there but but you know the funny thing about this right the Google machine used to have the target of 50 cubits and then this is like IBM when it came and wrote this paper 49 and just to maybe stick it to them and then they're like oh so then they're like 72 yes you know right I mean is this comparison because that's right this yeah so yes that is unfair that that is unfair yeah you're right you know like so you really should have more qubits that are perfect right so but it's so yeah it's just a sort of a rough guide this is a very interesting line between classical and quantum right in fact here's an interesting result you can simulate right any quantum circuit with only Clifford gates in polynomial time right and so we know that in order to have a good quantum algorithm that's more powerful than a classical algorithm it has to have more than Clifford gates and in fact you can simulate a small number of T gates also in polynomial time and so there's that boundary is some squishy boundary between you know how many peak eighths do you mean before it's like naught this is more powerful than classical and so you know this is something we're sort of exploring even just to test programs right it's like we can test small parts of our programs that are simulate able and in fact we have this sort of idea which is sort of interesting which is if you know the inputs and outputs of a specific instance of a quantum program or circuit we might be able to constrain the simulation to be polynomial which basically from in a classical world that means we can in polynomial time do one software test vector right so input/output pair and then it becomes a testing problem where you have to pick test vectors that sort of exercise the program right so that's sort of a methodology we're trying to develop so that's also related to this other piece of the software puzzle which is that so the sort of holy grail of programming language and software people is that if we only wrote a better program languages better tools than the quantum algorithms people we come up with a lot more cool quantum algorithms right and so if you talk to quantum algorithms people they would say no way it's not how we do it right but it is the case that in our experience implementing a quantum algorithm is really difficult so let's say that someone wrote a paper that says here's linear systems algorithm or something takes like a year and a half to write that algorithm for real on a machine right it's like we're implementing all this stuff and there's a little there are a lot of errors both semantic and sort of performance problems and so this is a there lots of a lot of detail there and in that specific task I think there is a big role for software tools better languages better feedback debuggers we don't have debuggers you know so software tools that can help us write good implementations of algorithms and so you know some of that's visualization maybe some of that is maybe breaking up algorithms into libraries or templates so that you could people applications programmers can easily use those and so I'm going to talk a little bit about visualizing some properties and something called program synthesis just as examples so here is a time varying graph of every qubit in a linear systems implementation for different essentially parts of the circuit okay and on the y-axis is the sort of the fraction of those qubits that are entangled with each other so it's basically how much communication or how much sort of what's the relationship between those qubits and sort of the higher the fraction the harder it is to simulate the machine and the harder it is to build a machine that can a physical machine that could support that communication essentially and I'm sort of interested in seeing you know what's the fraction really and it actually is a little bit lower than I expected right it can't be trivial it can't be too low or else there's probably there's no computational advantage to the algorithm but it's not quite as high as I thought it might be and so this is something that we might want to understand better because this helps us in mapping the algorithms it helps us in understanding how to simulate them and it also helps us in understanding if you wrote an algorithm and this doesn't look right that might show you that you know you didn't implement it correctly for example so really one sort of final further afield thing is there is this technique in classical computing which has recently become popular in the last few years called program synthesis and program synthesis is this sort of interesting technique where you you sketch the program so you write some specification program that's not an implementation it's incomplete it's it can be sort of partial and this thing called the synthesizer essentially exhaustively searches for all the implementations that meet the skeleton or the sketch and then this thing called the verifier checks to see if it's a correct implementation so you have to have a some way of checking to see if the program does what you want it to do right and then sort of just goes around and then out comes some programs this technique actually has been used to create things like Network protocols for networking security policies for implementing different secure computing systems so when you have a restricted domain a restricted problem and maybe a special language domain-specific language then they can do this reasonably well and you might imagine that quantum circuits quantum computing is a sort of restricted area that we might be able to apply this so we're just starting this here's sort of a little hand example that of one of my students played with so he sketched quantum teleportation and then he by hand he didn't have an implementation exhaustively searched all the things within his sketch right and the interesting thing is he came up with this little protocol which like no human would come up with right and and it's not clear it's useful I mean so his particular there are two benefits of this number one he's interested in coming up with interesting variants interesting implement of different algorithms maybe they'll be useful for something we don't know yet I'm actually interested in just a correct synthesis path like so we have an algorithm and we create an inflation and we know it's correct right that in this case that might be easier than what the situation we have right now which is we have an algorithm that someone implemented by hand and we don't know if it's correct and even if we had a specification of if it's of what it should do it's very hard to check those two things together all right so basically check and implementation against a specification there are ways of doing that that's we are actually doing that too but in this case the forward sort of synthetic path might be easier than the checking path to see if something is correct all right so let me wrap up this really comes down to what are the right abstractions okay so right now we have all these layers and the state-of-the-art right now is you know we don't have much in the waste specification or formal methods but there are you know there's a formal language called cook which does allows you to prove things about programs if you write them in that language we might you know Express algorithms in terms of the properties of the Hamiltonian and then we can check that against some implementation or it may be synthesize some implication and right now we have all these little programming languages that exist out there they each have their strengths and weaknesses and then they mostly all go down to some form of gates or quantum assembly which now you know so IBM is is has a standard being called open chasm it's a variant actually we came up with chasm like 15 years ago you're not with Ickes group and it's sort of our fault that we didn't impose any control on it because everyone has their own flavor of chasm actually but now we're trying to you know standardize it and then you know actually there even IBM is even thinking of coming up with the Czar's a pulse control interface so that if we have these layers of software we could sort of target different machines with some abstraction of what pulsus look like so this is sort of maybe this what it where we are now a lot of what I talked about today is sort of breaking this right you know going directly from here to here for example right and so you know that's something that we are going to explore over the next five years or longer and think about you know where where must we if we want efficiency break abstraction and where can we you know where where can we leave it in place right and that really comes down to this sort of interesting question which is you know I talked about this gap between algorithms and devices right and filling this gap well there's this other sort of weird gap that we deal with now all the time because we've done fifteen years of work where we were on this end and now we're on this end and in fact it's sort of awkward cousin like you know when I write a paper I have to say this is about this side and then sometimes I would still write something like this like oh no this is about this side and then the question is over time how are these things going to relate to each other right we did all these sort of short-term tricks right we're gonna do how many of them were persist as we scale the number of qubits optimistically to the right right and you know in in classical computing this happened right in the 50s we were here and as we got to play over here we started ignoring things like physical properties we started ignoring things like well we don't care how many bits we use right will we ever get there that's not clear in the classical in the quantum space also the classical space is moving back this way because of energy constraints we are starting to worry about no easy computation with approximate computation so we're sort of breaking that abstraction even in the classical space so I actually feel like we're probably going it up somewhere in the middle here I mean I know how many bits it's going to be but we're gonna have some mixture of the things we learn in the next five to ten years and some mixture of the things we had before right so I'll just say well strapped up with you know one of the things that we're doing is sort of community building so we they're very few computer scientists or computers other than theorists in this field and they're basically just a few of us on this team and so we're trying to like greatly increase that and and as part of that we're creating a whole set of tools that go from our tools to the IBM tools down to their machines and then sort of educational materials and examples of these research problems right and it's geared towards you know computer scientists but you know in general this might be useful to the community as a whole it should be nicely packaged this is our project website we keep it all there and so as we've developed this well it's all going to be open source and released and it'll be like yeah Jupiter notebooks and videos and all that stuff and in and and this website actually as a whole you know we have a an umbrella which is like going to be an industry consortium and and probably an academic consortium since there's actually a hundred people are registered for this thing right now so so that community as we build it will try to sort of nurture forward and and provide tools and and guidance and collaborations as we go so you know where are we right so you know I think it's an exciting time right it's a historic time or we hope it's a historic time right and I think that you know it is is there's this big missing piece which is this middle the software and the architecture and that it's going to be a really key part of accelerating progress in the field right and I think that you know what we're really looking for a sort of like the right models and it's abstract shion's to sort of get the maximal leverage at this point and maybe into the future so that's it thank you very much [Applause] so for quantum computing this actually a lots of effort will be spent on doing error correction and meant being for tolerant against the errors and can comment down how this like a software thing could actually make that putt be even more efficient so do you mean error correction in the traditional sense or maybe I should repeat that right okay so do you mean error correction in the traditional sense or like like the error correction we talked about like errors Oh continuous aircraft motivational engine more traditional right so actually in the next five years we are not focusing very much on error correction because we don't expect to have the resources to do that so we're focusing actually on what we would call error mitigation so any kind of very lightweight redundancy some of our team members are sort of at the algorithms and sort of applications or chemistry level and so they're looking at sort of application specific methods you know sort of redundant sampling or does a little bit of redundancy in the data structures so you know we're we can probably probably only afford like factor of two redundancy not like a factor of twenty or so or thirty right and so that's that's our focus in the near term it's still the case that we're hosts it's funny my students they just keep going they like we're always tempted to do more work on the right-half because we you know have all this infrastructure and still have ideas so they just wrote another paper on like surface code decoders or something I'm like but that's like a lot of qubit so anyway our you know our project norm nominally is targeting a hundred to a thousand cubits and the Rilke okay maybe thousand cubits you know I think we'll still put the project name on it or something but but I think it but our focus our emphasis is is going to be not those those I'd like to ask one so I like the discussion about quantum volume but you also had this slide we were showing some metric that went by a little too fast not me the degree of entanglement between oh yes certain qubits it seems to me like maybe you know quantum volume if you just do it in a very straightforward way you might have almost no entanglement I mean you could have many many gates you know but if you if you if you started all on the ground stae and just start doing things nothing much is gonna happen right all right so and there's this also this thing you talked about with the number of T gates somehow mattering so right is there a way to efficiently compute something about the not just the sort of straightforward volume from the space-time area but the effective interesting part of Hilbert space volume the degree of entanglement times number of qubits right and and maybe how does that algorithm or that metric you showed relate to this yeah so I think that would relate in the sense that well so as a software tools person the way I would calculate the sort of the more realistic quantum volume is I would just run it through the tool chain for a specific application right and I could scale it out for any architecture and sort of it have an automated metric that's applicant specific to the to the connectivity of an application and specific to whatever machine that you have now most often we want some sort of analytic thing that's very abstract right and so number of qubits is abstract qubits times gates is abstract IBM actually defines quantum volume as number of as the volume that you can get with a random circuit right which is a very demanding actually concept set of connectivity right because most circuits probably have some locality random Serkis have all these global connections so that's a very hard metric that they use I mean I would probably use something that was maybe a benchmark set of programs program graphs and then you know we could calculate the volume for all those graphs and maybe take an average or some have some statistics on that that would be maybe some compromise between the really simple thing and the very sort of having to have the software tools to calculate it for you also be interesting to the computer science people so you know just from brief interactions with various computer science people they they learn different math than we learned and they you know they they have a very different you know quantitative background so do you have you've now developed an educational bridging type of curriculum or bootcamp or process for saying how much quantum and what kind of quantum do I teach people who think of themselves as primarily computer scientists you know applied mathematicians so shall we say I mean so you tell us how you were addressing that yeah that's a really interesting question I mean I'm not sure we have the answer yet although it is one of our charters as NSF cares about this kind of thing and there are a number of people working on this problem also you know from different organizations I mean I think the problem is actually computer scientists vary quite a lot right you know even within computer science you know you could teach people about quantum computing from sort of a linear algebra point of view which is already abstracting away a lot of the noise and device models but then that's even just a subset of computer scientists because then a lot of computer scientists might like you too so in I I'm in the architecture community and architects tend to think of things as circuits and you know graphs and things like that but not so much like you can teach it to them in linear out with linear algebra but they won't get any intuition out of it actually that's sort of actually the way I am like I understand how things work but it doesn't like someone has I have to like reduce it to like an architecture or a graph or you know some set of costs and circuits or something like that and so so I usually we usually teach things that way like this we mostly teach things to architects right like so we come up with some abstraction we come up with some parameters for devices and components and then we sort of show how that composes and so it it looks like you know a fairly abstract like abstract or like reductionist view of how machines are built with some very you know sort of relatively unexplained rules like oh well these two things are related we won't really explain how but you know they are and then or maybe there's some error mode between these things so we that's right I think that that is typically how we start you know in our research is a little different because right now we're having to look more closely at machines so our specific students oftentimes have some background you know if in multiple degrees and things like that so they they they can it's but we're I mean we're the group at the boundary right but I sort of imagine a lot of groups that we want to get involved in this are going to be far above the boundary essentially I mean it is it is also case like so at Chicago we have this thing called the Institute for molecular engineering and they have like a quantum engineering degree program and they're actually trying to abstract this away or not come up with a methodology that's gonna be much closer to teaching how physics and devices work for engineering students right but not necessarily physics students okay I think maybe in the interest of time they see there's a few more questions but maybe we should sort of wrap up here so I think it's very interesting talk you've given us and I really am glad to see that you are working in this kind of area I mean I think I agree wholeheartedly about this being a very interesting time and if we're gonna make quantum computers useful it's not going to be just a hardware problem or a software problem it's definitely going to take the combination of both so thanks for sort of setting the table and okay [Applause] [Music]

Channel: YaleUniversity

Views: 2,019

Rating: 5 out of 5

Keywords: Yale, Quantum, Algorithm, Computer Science, Yale Quantum Institute, Fred Chong

Id: GYHdutMfoX4

Length: 62min 40sec (3760 seconds)

Published: Mon Apr 30 2018