Quantum Software Engineering

Many believe we are on the precipice of building the world's first scalable Quantum computer. But once they're here, how will we write software for them?

By Brinley Macnamara

Guests: Richard Preston and Jen Orr

Transcript

Richard Preston (00:02):

Say that you were trying to describe to somebody or tell somebody how to make a peanut butter sandwich. You're going to give them a peanut butter sandwich recipe card. Classically, you'd say something like this, and say, "Okay, step one, place one slice of bread on the counter. Step two, go and get the peanut butter from the cupboard. Step three, get out the knife from the drawer. Step four, spread the peanut butter on the bread," etc., etc., etc. So you tell the person each step of the way what they need to do in order to actually wind up with a peanut butter sandwich at the end.

Richard Preston (00:35):

Now, in a quantum perspective, let's say, maybe a quantum algorithms researcher might tell you how to make a peanut butter sandwich like this. Might say, "The bread is on the table, the peanut butter is on the bread." So they would just tell you what the state of the universe needs to be, but they wouldn't tell you that you need to go get a knife from the drawer and that you need to spread the peanut butter, and the other thing is that they might not tell you that actually ... There's no such thing as quantum peanut butter. Right, it's just theoretical. Nobody's invented it yet. If you actually need to go and implement that in real life, then you're going to be stuck.

Brinley Macnamara (host) (01:12):

Hello and welcome to MITRE's Tech Futures Podcast. I'm your host, Brinley Macnamara. At MITRE, we offer a unique vantage point and objective insights that we share in the public interest, and in this podcast series, we showcase emerging technologies that will affect the government and our nation in the future. Today, we're talking about the emerging field of quantum computing from a really unique perspective, that is from the perspective of a MITRE software engineer who knows a whole lot about what it takes to program a quantum computer. And by the end of this podcast, you should have a better idea of how you'd go about implementing a software program that makes a quantum peanut butter sandwich.

Brinley Macnamara (host) (01:50):

But before we dive in, I want to say huge thank you to Dr. Kris Rosfjord, the Tech Futures Innovation Area Leader in MITRE's Research and Development program. This episode would not have happened without her support. Now, without further ado, I bring you MITRE's Tech Futures Podcast episode number 14. I want to start with a quick disclaimer. As they sound, quantum computers are a special type of computer that are based on the laws of quantum mechanics. But if you're not a quantum physicist, you're in the right place. Because for this podcast, you won't need to know anything about how quantum physics works.

Brinley Macnamara (host) (02:36):

All you need to understand is that quantum computers are fundamentally different from the classical computers we use every day to check email and share our favorite cat memes. For this reason, they're never going to completely replace classical computers, but they may be able to solve some special types of problems much faster than a classical computer could. If you're interested in more technical details about how quantum computers leverage quantum physics, we're going to create an advanced version of this podcast. We'll release it soon after this one, so stay in the lookout. All right, we reached the end of my disclaimer. Now, onto the fun stuff.

Brinley Macnamara (host) (03:14):

Imagine you are an early investor in Bitcoin. Let's say you bought 10,000 Bitcoin back in 2010 when the cryptocurrency was going for nine cents a pop. You stored your 10,000 Bitcoin in a password-protected Bitcoin wallet on your computer and wrote your 10 character password down on a piece of paper. Now, fast forward to 2021, Bitcoin is going for $60,000 a pop and your 10,000 Bitcoin is now worth a whopping $600 million, but there's a problem. You can't remember where you put that piece of paper with your Bitcoin wallet password. You search for days, turning up the entire house to no avail.

Brinley Macnamara (host) (03:52):

At this point, your only option is to guess all possible 10 character password combinations. But there's another problem. Even at a million checks per second, guessing and checking all possible password combinations would take you 40 billion years. Yes, you heard me correctly. That's 40 billion years. More than twice the age of the universe. Your doctor friend tells you that even with more kale, it's unlikely you'll live 40 billion more years. Luckily, your quantum physicist friend has a different take on the problem. One day, perhaps in your lifetime, he says, "You may be able to use an algorithm that is specially designed for a quantum computer to crack your password in a mere 13 days."

Richard Preston (04:35):

So Grover's algorithm would allow you to search for some value in square root the number of steps as it would on a classical computer.

Brinley Macnamara (host) (04:43):

That's Richard Preston talking. You heard him at the start of this podcast. He's a Principal Investigator at MITRE who specializes in quantum software engineering. He's also a Group Leader and MITRE's Network Analytics department.

Richard Preston (04:56):

So for example, if you had a ... If you were trying to crack a password, you said you had ... You lost your password to your Bitcoin wallet. On a classical computer, you would have to go through and check each individual possible key or possible password in order to find the one that works, right? There's not really anything better we can do than just do brute force. So Grover's algorithm, it's kind of like a brute force in that we are really exploring the entire space of possible keys, but we're trying to do that almost all at once.

Brinley Macnamara (host) (05:33):

Grover's is just one algorithm in a growing class of algorithms that possess a so-called quantum advantage. By the way, when we say an algorithm has a "quantum advantage," we simply mean that it can solve problems on a quantum computer much better than a classical algorithm running on a classical computer could. Now, if you've been keeping up with the quantum computing headlines, you may know that many research groups across the world have already built quantum computers. IBM even makes some of their quantum computers accessible to the general public through their cloud computing platform.

Brinley Macnamara (host) (06:05):

Why aren't we already using quantum computers to crack our forgotten passwords? The biggest reason is that today's quantum computers are extremely limited in their scale. By scale, we mean the amount of information a quantum computer can represent at any given time. In quantum computers, we measure scale by the number of quantum bits or qubits a quantum computer has. Today's universal quantum computers have anywhere between five to 127 quantum bits. To put this into perspective, today's classical computers have up to 60 billion classical bits. Accordingly, there are still many open questions about the amount of quantum bits will be required to run practical quantum algorithms like Grover's.

Brinley Macnamara (host) (06:48):

Option A is to wait and see, but this will be risky because just as any crypto investor would jump at the chance to crack our forgotten Bitcoin wallet password, so too will hackers, and they won't stop at our Bitcoin wallets. Luckily, we have an option B, which is to implement quantum algorithms in software and simulate them on classical computers. Of course, classical simulators are inherently limited in the scale they can achieve. According to Richard, a classical simulator's memory usage grows exponentially with the number of qubits an algorithm requires. Quantum algorithms that need thousands or even hundreds of qubits are out of the question for classical simulation.

Brinley Macnamara (host) (07:24):

That said, simulating a few dozen or so qubits is within the realm of possibility. Moreover, algorithms that can't be fully simulated can oftentimes be run through something called a classical resource estimator, which can give researchers a rough idea of how big of a quantum computer a given algorithm will require even without fully simulating the given algorithm. This means that even without the existence of any practical quantum computers, quantum software engineers like Richard had made a lot of progress on these so-called practicality assessments of quantum algorithms, all on their own classical computers without ever having to touch a quantum computer.

Brinley Macnamara (host) (08:00):

For instance, in his own practicality assessment of Grover's algorithm, Richard found that it would take as many as 800 to 6,000 quantum bits to crack real-world passwords with Grover's, and these figures don't even include the additional qubits that would be required to ensure the algorithm is fault tolerant. Now, it's also important to note that you can't implement quantum algorithms using the types of software engineering tools that you'd use to build a mobile app or a website. Quantum software engineers have their own set of tools, including their own programming languages, software development kits and compilers, in addition to classical simulators and resource estimators. I asked Richard about how one quantum programming language, Q#, compares to conventional languages like Python and Java.

Richard Preston (08:42):

Yeah. The syntax is not that unfamiliar, right? You have to type a semicolon at the end of a line. You use curly braces to denote the scope of your functions and your operations. But at the end of the day, quantum computing is a completely new computing paradigm, and so some of the syntax is going to look different and some of the ways that you have to think about programming is going to be different, no matter which programming framework you're in.

Richard Preston (09:08):

An analogy I sometimes use is if you're going between different classical programming languages, for example, if you have some Java program or an algorithm implemented in Java, and you want to port it to Python, that translation is relatively straightforward. It's like going from English to Spanish, right? Whereas trying to go to a quantum programming framework, or quantum language, this is like going from English to Japanese, right? Sometimes there's not a direct translation at all, and so you have to really think differently about how you're expressing those steps of an algorithm.

Brinley Macnamara (host) (09:44):

In addition to the challenge of translating from the classical paradigm to a quantum one, Richard also encountered another huge translation challenge during one of his own practicality assessments.

Richard Preston (09:55):

I was looking at what would be required to crack certain hash algorithms.

Brinley Macnamara (host) (10:01):

By the way, cracking hash algorithms is just fancy engineering speak for cracking passwords.

Richard Preston (10:07):

I was looking at if you were going to apply Grover's algorithm to, for example, SHA-256, what would that look like? How would you actually write a software program, not just on paper, but in code... how would you write a software program that would conduct this, we call it a pre-image attack on a hash algorithm? As I mentioned, we're still pretty early in what the hardware can offer us right now, but you can run simulations and unit tests and you can start to see, for example, how many qubits would be required to run this program, how many quantum gates would need to be applied in the course of this algorithm, what is the gate depth, in other words.

Richard Preston (10:45):

And these are all precise metrics that you can use to say this is when this application would be practical, is when we have quantum computers that are capable of running this type of program. That was some of the work that I started out doing, and then more recently, we came up with this idea of making that process of taking a quantum algorithm that's described in the literature and implementing it in software, making that process easier. Because what we found was that many of these papers were described in a way that didn't really lend itself well to software implementation, and there's a couple things there.

Richard Preston (11:26):

The first thing is, as I mentioned, sometimes the implementation details are lacking. For example, they might say, "apply this black box operation," but they don't tell you what's in the black box. They just tell you, "yeah, it is what it is." You have to figure out how to do that. The other thing is that many of these quantum algorithms in the literature are described using Dirac notation, which is a mathematical notation which fully describes the state of a quantum computer at any given step of the algorithm.

Richard Preston (12:06):

And this is mathematically complete, but it doesn't always tell you how to produce that state. From there, we realized that if we could come up with a tool or toolkit to try to translate that direct notation into something like a quantum circuit diagram, which shows you all the operations and all the gates that needs to be applied at each step of the algorithm, this would be very useful to software engineers. This is the research project that we're working on now. It's called QUASIT, Quantum Statevector Implementation Toolkit.

Brinley Macnamara (host) (12:37):

To review Richard's Quantum Statevector Implementation Toolkit, aka QUASIT, ingests a quantum algorithm in Dirac notation and outputs the same algorithm as a quantum circuit diagram. He refers to his tool as a Quantum Statevector Implementation Toolkit because Dirac notation will encode each state of the quantum computer at any given step of the algorithm as a "state-vector." But for the purposes of this podcast, all you need to know about a quantum statevector is that it boils down to some really confusing mathematical notation. So, whenever you hear statevector, just think confusing mathematical notation.

Brinley Macnamara (host) (13:13):

Now, to understand why translating a sequence of quantum statevectors into a quantum circuit diagram is incredibly useful, let's return to Richard's quantum peanut butter sandwich recipe. And at this point, I need to let you in on a little secret, which is, our quantum recipe analogy isn't 100% accurate. This is because it implies that a formalized quantum peanut butter sandwich recipe leaves out the concrete steps for how you'd go about making a quantum peanut butter sandwich. But the reality is much more nuanced.

Brinley Macnamara (host) (13:43):

The truth is that quantum physicists tend to be very detail-oriented people who go to great lengths to publish the implementation steps of their quantum algorithms. However, the mathematical notation, i.e., the direct notation, they use to describe these implementation steps is really difficult to understand if you're not an expert in the field. In other words, this mathematical notation is enough to convince other quantum physicists that a particular peanut butter sandwich recipe is exponentially better than every peanut butter sandwich recipe known to man, but not enough to implement the recipe in a programming language like Q#. Here's Richard.

Richard Preston (14:17):

Certainly to get your algorithm published, it has to be correct. Right? The math notation that we use, the Dirac notation that would describe the state of a quantum computer at each step of the way, this is a complete description of the algorithm. But just because it's a complete description doesn't mean that it's an easy description to then implement in a software program. You could think of it like a mathematical proof, right? You could have a mathematical proof for that an algorithm works or that an algorithm has certain properties, but it's a different task altogether to then code it in a particular programming language.

Jen Orr (14:54):

In the beginning of our research effort, our team poured over literally through hundreds upon hundreds of academic papers discussing quantum algorithms.

Brinley Macnamara (host) (15:04):

That's Jen Orr talking. She's a Principal Engineer at MITRE and is interested in how QUASIT can help the U.S. Government with their own practicality assessments of quantum algorithms.

Jen Orr (15:13):

If you've seen even a handful of these types of papers, it's definitely no easy feat to understand and translate it to practical terms, and also when you're reading these papers, it's very hard in full confidence to say if these quantum algorithms that are referenced in there would actually be useful for specific government challenges. It's just really complex. So, sponsors need a tool that can study the practicality of these algorithms, but in a way that is simplified.

Brinley Macnamara (host) (15:44):

This is where the quantum circuit diagram comes into play. Recall, the quantum circuit diagram is what you get when you run a quantum algorithm through Richard's Quantum Statevector Implementation Toolkit. As it sounds, a quantum circuit diagram is a visual representation of a quantum algorithm that tells you, in practical terms, exactly what you need to do to implement a quantum algorithm in a programming language like Q#. And in doing so, it leaves out all the mathematical fluff, no pun intended, that quantum physicists required to determine whether a quantum peanut butter sandwich really does possess a quantum advantage.

Richard Preston (16:18):

The long term vision, if we're really successful, would be this is a tool that could be used by industry and government and academia to just accelerate the process of taking a quantum algorithm and then actually applying it to a real world problem. One of the things that we are doing with the tool is developing a library of quantum algorithms that are out there, and I think if we're able to grow a community of users around this, then perhaps we could get some engagement in other people uploading algorithms to the tool, so that's the long term vision. We're not there yet, but we're really working towards it.

Brinley Macnamara (host) (16:56):

Just out of curiosity, are most quantum algorithms open source?

Richard Preston (17:01):

Yes, definitely. This is a very active research community, and in fact, the idea of quantum computing is not that new, it's simply the actual physical quantum computers and the physical quantum computing capability that is new. There have been theoretical quantum algorithms being published, academic papers being published for decades. But now we have the potential of actually taking those algorithms out of the papers, out of the university, let's say, and actually employing them in real solutions. That's what's really exciting about this industry right now, is that we're starting ... over the next decade, we're going to be crossing the threshold of this being a lab curiosity and a theoretical idea to being something that can be used in real life to solve real problems.

Brinley Macnamara (host) (17:58):

In addition to his work on QUASIT, Richard also spends a lot of time teaching the fundamentals of quantum software engineering to high schoolers, university students, and professionals. I asked Richard why he's such a strong advocate of software engineers learning how to program quantum computers.

Richard Preston (18:12):

Yeah. Let me take that from two perspectives. The first thing, just to maybe inspire people to learn about this, you're probably not going to be put out of a job, but if you are a programmer, think about what it was like when you first learned how to program. It really changes the way you think about solving problems. I had that same experience again when I learned how to program quantum computers. I would really encourage everyone, if you're curious about quantum computing, it won't actually take too much of your time, go out and find some tutorials. MITRE has some materials that stem.mitre.org/quantum you could look at.

Richard Preston (18:55):

But there's tons of materials out there, and start playing around with it and try to understand what the principles are and how it defers from classical programming. Because, again, I think one of the really exciting things about quantum computing is that this is a fundamentally new technology. Not just a new technology, but a new way of thinking about computation and so this has the potential to unlock all kinds of possibilities when humans, creative humans, start thinking differently about how computation works. That's what's really exciting about it. But just more practically, yeah, we definitely need people that are capable of using this technology because it will be important, right?

Richard Preston (19:42):

Once we have quantum advantage, once we can say, "All right, I can solve this problem much better if I incorporate a quantum computer into that solution," if you are not capable of doing that, let's say as an institution or a nation, then you will fall behind the competition. At the end of the day, as humans, we're really striving to build a brighter, safer, more exciting world for the next generation and for the generation after that. If the next generation ... To the extent that the next generation is better equipped to use this technology when they grow up, then we'll all be better off.

Brinley Macnamara (host) (20:30):

This show was written by me. It was produced and edited by myself and my co-host, Eliza Mace, Dr. Kris Rosfjord, Dr. Heath Farris, and Beverly Wood. Our guests were Richard Preston and Jen Orr. The music in this episode was brought to you by Sarah the Instrumentalist, Ooyy, Jerry Lacey, Blue Dot Sessions, and Truvio. We'd like to give a special thanks to Dr. Kris Rosfjord, the Technology Futures Innovation Area Leader for all her support.

Brinley Macnamara (host) (20:55):

We'd also like to give a special thanks to Dr. Gerry Gilbert, a MITRE Technical Fellow and the Theoretical Quantum Physicist leading MITRE's Quantum Moonshot, for his role in making the final version of this podcast the best it could possibly be. If you'd like to learn more about quantum software engineering, check out Richard's course at stem.mitre.org/quantum. We're also working on another podcast that covers more advanced topics in quantum software engineering. It'll be the next podcast we drop, so stay on the lookout. Copyright 2022 MITRE PRS number 22-2154, July 20th, 2022. MITRE, solving problems for a safer world.