Does Monte Carlo’s quadratic speedup survive contact with real hardware?

Summary

Three experts in quantum Monte Carlo: Quantum Monte Carlo with Gustavo Ordoñez of Moody’s Analytics, Giorgios Korpas of HSBC, and Iordanis Kerenidis of QCWare, are interviewed by Yuval Boger. They talk about what quantum Monte Carlo is, the difference from classical Monte Carlo, how soon before it becomes a production-ready algorithm, and much more.

Get the full transcript at the Quantum Computing Report

Transcript

Yuval Boger: Hello, Gustavo. Hello, Iordanis. Hello, Georgios. Thanks for joining me today.

Gustavo Ordoñez: Hello.

Yuval: So, Gustavo, let's start with you. Who are you and what do you do?

Gustavo: Right. So, Gustavo Ordoñez. I work for Moody's Analytics. I'm a senior director and data scientist, and I basically work in research.

I build new models and explore new ways of using data to look at what can be done, and how we can make better decisions faster and more accurately. Those then power our products. So that's what I do. Part of what I do is to help the quantum ecosystem within Moody's Analytics, which is led by Sergio Gago, who I know has been on the podcast in the past.

So I support Sergio in that journey of establishing a quantum computing group at Moody's Analytics. The reason for that is that I'm very, very passionate about quantum computing. I was a research physicist many years ago, and that's where I discovered quantum computing. I've been keeping an eye on it as a hobby for many years, and in the last three or four years I've been looking at it on a more serious note, because it's becoming more and more likely that it's actually going to have an impact on the industry in the medium term, I would say.

So that's me.

Yuval: And Gustavo, what city are you calling from today?

Gustavo: Well, I'm calling from Scotland, actually. Stirling, in Scotland. It's a small city in between Glasgow and Edinburgh. I'm based in the Moody's Analytics offices in Edinburgh, but I'm working from home today, so I'm here in Stirling.

Yuval: Excellent.

And Iordanis, I think you're calling from Paris. Who are you and what do you do?

Iordanis Kerenidis: Hi, Yuval. Yes, I am calling from Paris. My name is Iordanis Kerenidis. I'm the head of quantum algorithms for QC Ware, which is a quantum software company. I started working on quantum algorithms more than 20 years ago.

I did my PhD at Berkeley, then I was at MIT, and for the last 15 years I've been based in Paris. I was working with CNRS at the university. For the last three years, I've been working for QC Ware, where I work on optimization and machine learning for the finance domain, but also other domains. We have worked quite a bit with different financial institutions, in particular on Monte Carlo methods.

So I'm very happy to be here.

Yuval: I'm glad you're here. And Georgios, where are you calling from, who are you, and what do you do?

Georgios Korpas: HSBC. I have a slightly different background than most people involved in quantum computing, since I come from very theoretical aspects of physics. I have a background in string theory and topological quantum field theories.

Within HSBC, I co-lead the programs in quantum optimization, quantum Monte Carlo, and aspects of classical machine learning as well. Just like Gustavo and Iordanis, I'm extremely passionate about the topic, and I'm very happy to be here.

Yuval: Excellent. I'm not an expert on quantum Monte Carlo, certainly not to the level that you are.

So maybe Iordanis, you can tell me what Monte Carlo is, and Gustavo, maybe you can explain the difference between Monte Carlo and quantum Monte Carlo. Iordanis, why don't you go first, please?

Iordanis: Sure. I'll try to say it in a simple way, as I understand it. I'm also not a finance expert.

The idea is that we have some assets that we want to price, for example, and we want to understand how to price them. The way we do it is by constructing some sort of model for the market, which mathematically is some stochastic process. Then we run many different scenarios according to this process.

For each one of these scenarios, we compute the right price for our asset. Once we've done it many, many times, we aggregate all of these results and compute, in expectation, what we say is the correct price for this asset. So this is the Monte Carlo way of pricing an asset, and Gustavo can continue with the quantum way of doing it.

Gustavo: Okay. Thanks, Iordanis. The idea behind Monte Carlo is actually very simple. You have a problem that is too difficult to solve analytically, so you can only tackle it numerically. What you do is draw from a random distribution that you can sample efficiently. The draws from that distribution that end up in the solution space you're interested in, you keep, and the rest you discard. By doing that, you can infer the answer to the problem you're looking for.

That, in essence, is the Monte Carlo technique, and it's extremely flexible. It works for a very, very large number of problems. It's also very powerful in the sense that it can solve very high-dimensional problems efficiently. But when I say efficiently, I mean it's very easy to code, very easy to get running, et cetera.

It's also not very efficient in the sense that it takes a long time to run, because you have to draw many, many samples from this random distribution. What quantum Monte Carlo does is leverage a very well-known set of algorithms in the quantum algorithm domain, namely Grover's algorithm and the amplitude estimation algorithms, to do the same thing you would do classically, but quadratically faster.

So if the particular problem you want to solve classically takes, say, one million simulations to reach the level of accuracy you're interested in, then in principle, theoretically, on a quantum computer you could do that with only one thousand samples. That's a huge gain if you take into account that many of these are huge problems for which you need very large computer clusters in the cloud running overnight to get to the answer.

So that is why this is one of the key problems in quantum finance being explored by financial institutions. But as I said, in a sense it does the same thing: it's sampling from a distribution. In this case, because the quantum circuit runs on a machine that is already stochastic by nature, you leverage these well-known algorithms I mentioned to do the same thing quadratically faster.

Yuval: So, Georgios, in your opinion, what makes quantum Monte Carlo at least theoretically better than regular Monte Carlo?

Is it that the random distribution for quantum could be truly random? Is it the ability to run multiple scenarios simultaneously on a quantum machine? Why the big interest in quantum?

Georgios: I would say it's essentially what Gustavo mentioned, which is the sample complexity.

If you have a very simple case where you want to run a classical Monte Carlo with, say, 100 samples, your confidence interval for this estimation would scale proportionally to one over the square root of 100. So that's an error of 0.1. But quantumly, using these algorithms that Gustavo mentioned and that Iordanis has been developing for a long time now, you can compute this confidence interval with a scaling that goes as one over M, where M is your number of steps. So for 100 steps, that would be 0.01, so that's 1%. It's essentially this improvement in accuracy that you obtain, which can also be converted to speed. However, I would like to note there are several limitations that we may discuss at a certain point.

Yuval: Iordanis, I think you work with customers in a variety of fields, maybe not just finance. Is quantum Monte Carlo applicable to additional areas, or is it primarily used in the finance field?

Iordanis: I mean, it is a very basic mathematical way of trying to calculate something, so it does have applications in many other domains.

But I think finance is one where it's really used all the time, and this is really where we're trying to see exactly how quantum can help, or when quantum will help. Because, as Georgios was saying, there are some caveats with this algorithm. The first one is that, in order to get the speedup from a million samples to a thousand samples, which is amazing if we manage to do it, right?

We need quantum circuits that are very deep, let's say a thousand deep, and this necessitates very good quality qubits, which are not the qubits we have today, but which we hope to get at some point. One way to try to overcome this obstacle is based on some work we did with Goldman Sachs, which says a very simple thing: if you want this thousand-times-faster algorithm, then you need this very deep, thousand-deep circuit.

But you can get a ten-times speedup if you have a ten-deep circuit. So you don't have to wait until you have very, very good quality qubits to get the entire speedup. You can start getting smaller speedups, which hopefully will still be relevant from a business and finance point of view, with much simpler quantum circuits.

So this is one of the two reasons why we now think that quantum Monte Carlo may not be so far off in the future, but a little bit closer, let's say midterm. The second quick comment I want to make: up to now, what we were counting is how many samples we need to take from this process, from this distribution, right?

One part we don't talk about so much in the quantum case is how difficult it is to actually take one sample from this distribution. Because in order to run this quantum algorithm, we need to do this sampling in superposition, in a quantum way, to fit it into the quantum algorithm.

And it's not obvious how to do things like a Brownian motion or geometric Brownian motion very efficiently in the quantum case. So this is also a very interesting part: how do we make this step more efficient? Then we may be able to do not only ten samples, but a hundred samples, to get a hundred-times speedup.

So putting these two things together, doing the stochastic modeling very fast and saving on the number of samples we need, can, we think, provide an end-to-end quantum solution to the Monte Carlo pricing problem in the near future.

Yuval: So Gustavo, I'm curious about your perspective on how practical it is today.

I mean, obviously there are algorithms like Shor's algorithm that promise amazing things but are impractical on today's computers. You work at Moody's. Are you using quantum Monte Carlo in production today? Or if not, how far away do you think it is?

Gustavo: No, we're not using it, and I don't think we're going to be using it anytime soon.

That's why, in my opening, I mentioned the medium term. By medium term, I'm talking probably five years, maybe five to 10 years, something like that. The limitation right now is the hardware, as Iordanis was alluding to. We don't have hardware with enough fidelity to really run these algorithms in a naive way.

So we need to find ways to extract as much as we can from the noisy hardware we're going to have for the foreseeable future. Therefore, what algorithm developers need to do is find ways to deal with the fact that we're going to have noisy hardware.

We're going to lose some of the theoretical advantage promised by the algorithms we know today. So the task is to find ways around those limitations and still extract as much advantage as you can.

But as I said, I don't think it's going to happen anytime soon. Another thing I would say is that, on the classical side, when we run classical Monte Carlo, we never, or very rarely, use the most naive way of running these algorithms.

There are many, many improvements you can make on the classical side, like importance sampling and other variance reduction techniques. There are many of them, and they already give you a huge advantage over the naive classical Monte Carlo algorithms.

Yuval: So Georgios, maybe you want to add to that, and Iordanis after that. You mentioned some of the work you did with Goldman Sachs. Maybe you could give us a lay of the land of the improvements you've seen in recent years.

Georgios: But maybe first, some background for people who may not be so aware of what we mean by quantum alternatives to Monte Carlo.

Essentially, it's not one algorithm. It's an amalgam of three or four quantum subroutines, quantum algorithms. And indeed, if you want to run the original ideas as they were developed in the 2000s, it's very difficult, as Iordanis has mentioned.

He also knows this very well, since he's one of the co-developers of improvements to these algorithms, where, for example, you can take some of these subroutines and replace them with something else. That something else could be a classical part, for example. So there is some classical post-processing as your algorithm develops. It may not be the best thing you could do, but it can definitely bring it into the timeframe Gustavo mentioned, the five-year timeframe.

There are other variations that Iordanis is much better placed to explain, for example his QoPrime quantum amplitude estimation, which is also very promising. So I think it's not all negative, by any means. But at the same time, I totally agree with Gustavo that there is some pressure, especially when you don't work in a university, to focus only on the algorithmic side.

But quantum computing is three steps: data loading, compute, and readout. Maybe the community should also pay more attention to, for example, the problem Iordanis briefly mentioned, which is data loading, doing it more efficiently in order to speed up your computations and not bury your quadratic advantage in these overhead costs.

And the same, of course, goes for having accurate readouts. So when we develop these algorithms that are so fundamental and will be of such importance for financial applications, we need to take a step back and look at the bigger picture as well, because improvements on these sides, at the beginning and the end of the algorithm, can actually bring the algorithm closer in time to actual application.

Iordanis: Yeah, I totally agree with Georgios that if we really want to see any of these advantages in practice, then we need to take care of every single part of the workflow.

He was mentioning the data loading part: how do we load these Brownian paths or things like that. We have been working on this lately. It's not an easy thing to do, but we do think we can provide very shallow circuits, like logarithmic-depth circuits, for this data loading part, which in turn would mean that the depth of the entire circuit and the required quality of the qubits can be much, much lower.

So yeah, I would still agree that we are five years out from seeing quantum Monte Carlo really start to bring something. I wouldn't put it closer than that. And to make it happen in five years, we do need the hardware to continue to develop and advance, as the roadmaps are saying.

We believe they will continue to advance the way they think they can. And on the algorithmic side, as Georgios was mentioning, we do need to keep working on it. We shouldn't think of quantum applications as something where the algorithms are already there and we're just waiting for the hardware, right?

We really need to push the algorithms as much as we can, because, as Gustavo was saying, we have to make do with very noisy and not very big quantum machines. We have to make the best of them, and we really need to understand everything about them if we're going to make good use of them and bring some sort of real-world advantage.

Yuval: You spoke about the hardware and the need for deeper circuits. Would more qubits help? I mean, if you had a choice between a computer that can run a 10 times deeper circuit or one that has 10 times more qubits, would one be much better for quantum—

Iordanis: Yeah, yeah.

Yuval: —Monte Carlo than the other?

Iordanis: It depends on the application.

I think on the Monte Carlo side, the quality of the qubits is more important than how many qubits. We do need more qubits than we have today, but I think the bottleneck is really that we need to do these deep computations, so we need more depth. Of course, you can get more depth by error-correcting your physical qubits.

So if I had many physical qubits, I could use some of them to make fewer, better qubits, let's say. But yeah, we need a couple of orders of magnitude better fidelity than we have today. That is in the hardware providers' roadmaps for the next five years, right? So we are not expecting anything out of the ordinary to happen.

And we are continuing to reduce, as you said, how many qubits we need, or how good these qubits need to be, and still get a good result.

Gustavo: Yeah, if I may add a little to Iordanis' answer, I think it also depends on the particular problem in finance we're talking about. Iordanis already mentioned that one of the uses of quantum Monte Carlo would be in option pricing, and there you typically have a few sources of uncertainty in the problem.

We have the price of the stock, and maybe the volatility, which you can also assume follows some kind of stochastic process. You can add jumps to the process as well, so you might have a third source of uncertainty, or stochasticity. And for each of these sources of uncertainty, you would need more qubits to deal with it, right?

Now, if you move into a basket of options, where you have, say, ten or 15 assets, the problem multiplies by 15. And if you move into the realm of, for example, credit portfolios, where you're potentially dealing with millions of assets, then even if you assume there's only one source of uncertainty per asset, you would need at least one million qubits just to deal with the uncertainty from the assets.

So it really depends on which application we're thinking of. In some, we can get away with fewer, better quality qubits, while the more complex applications in finance would actually need millions of good quality qubits.

Yuval: Now, I think the original Monte Carlo method was invented at Los Alamos as part of the Manhattan Project, and obviously there were a lot of physicists and mathematicians there. When you work on these algorithms, even with that five-year horizon, what kind of people do you need on your team to improve Monte Carlo?

Are they more finance people? Are they biologists? Quantum scientists? Is there a particular type of person you're looking to add to your team?

Gustavo: If I start: typically, we're looking for people with a technical education. So we're looking for people with master's degrees or PhDs in a quantitative subject.

That can vary: people from math, engineering, physics, economics. But you can also go to the more specialist financial mathematics type of expert. The advantage of having someone with more of a financial mathematics background is that they already know the types of problems we're solving in finance.

But at the end of the day, these quantitative skills are very easy to transfer from one domain to another. So if you have good mathematical skills and good analytical skills, combined with a decent amount of IT and programming skills, then you're in a good place, right?

If you tick these boxes, it doesn't matter so much whether you're coming from physics, mathematics, or financial mathematics; you will get there. Although I would say that, in the beginning, there's always a steep learning curve to get to the level of knowledge about the financial industry that you need to really use those mathematical and analytical skills to solve real-world problems in finance.

Iordanis: Yeah. On our side, I think one important thing is experience in building and developing new quantum algorithms, and this is something quite rare, because we are not a very big community, unfortunately. So we need people who are very confident with classical algorithms and quantum information, so they can start developing new quantum algorithms.

But I agree with Gustavo that the most impactful research happens when expertise on the quantum side comes together with expertise from the finance side, because we need to understand what the real bottleneck is, what we need to care about more or less, and what problem we're really trying to solve.

Understanding the financial part is really what makes the difference between a theoretical publication on quantum algorithms and a real financial solution on a quantum computer, right? So I think we need both.

Yuval: And Georgios, do you have something to add?

Georgios: Yeah, I totally agree with both Iordanis and Gustavo.

I would just like to add a small comment from my experience. I found the interaction with people who understand stochastic mathematics particularly useful: stochastic differential equations, stochastic optimal control, and real analysis.

The reason is that often, at the initial stage of quantum algorithm development, we omit certain technical details about the speedups we claim and such. However, you have to take these small technicalities into account. For example, what type of function, what type of distribution are you working with?

There's a difference between Hölder continuity and Lipschitz continuity, and this affects a lot the bounds you give on your algorithms. There's no single answer, right? So I believe a lot of disciplines can contribute at different levels of algorithm development, but they all have a difficult learning curve.

Yuval: Very good. As we get close to the end of our conversation, I want to ask you one of my favorite questions. If you could have dinner with one of the quantum greats, dead or alive—and don't say both dead and alive, no superposition here—who would that person be? Maybe Iordanis first, then Gustavo, and then Georgios, please.

Iordanis: Sure. I think I've had dinner with many of the people who are alive, so I'm very happy with that, and I'm sure I'll get the opportunity to eat with the rest of them. So I would go for someone who has been dead for a long time, and I would say Niels Bohr. The main reason is that Bohr actually had the right idea and the right intuition about quantum mechanics, and there was a big fight between him and Heisenberg about what quantum mechanics really means.

Even though we talk more about Heisenberg and Heisenberg's uncertainty principle, it's actually Bohr's idea that we believe today. So I would really want to have dinner with Niels Bohr and understand how he came up with all these counterintuitive ideas that are actually the ones we believe today.

Gustavo: Okay, I think I would want to have dinner with Paul Dirac. The reason is that I admire the passion he had, and the self-belief that he had found the right solution when solving his famous equation, which in essence predicted antimatter, right?

And the positron was found, I think, a couple of years after he published his findings. But the entire community was thinking it couldn't be right, because his solutions predicted negative energy, and that didn't make any sense.

He found the solutions so elegant that they had to be correct; it was just a matter of finding the right interpretation. I think that was incredible, and I would love to hear from his own mouth how he coped with the potential pressure around him to ditch that theory, and how he managed to stick to his guns and keep digging until he found a more plausible explanation.

It turned out to be the right one, and a massive new discovery for science.

Georgios: Okay. I would go with Alan Turing, because I think he's a giant, and he's one of the people responsible for the age of information we live in right now, including quantum information.

The ideas he sparked, from philosophy to pure math, to applied math, to engineering, and his contributions are enormous: the notion of computable functions, what is computable and what is not. I would be very curious to ask him a lot of questions and get intuition and inspiration from him.

I think that would be my choice. Maybe I would invite John von Neumann as well, if I were allowed.

Yuval: Excellent. And Gustavo, I had a previous guest who said that Dirac was not a very good conversationalist. He spoke very little, but when he spoke, it had tremendous meaning.

So I think my previous guest said, "Yeah, I'd love to have Dirac, but maybe we'd also have Feynman or someone, just to keep everyone engaged."

Gustavo: Yeah, apparently Paul once said to Feynman, "Do you have an equation named after yourself?" And Feynman didn't.

And that was it. That was the end of their conversation. So yeah, it could be quite awkward, that dinner with Paul Dirac. You're absolutely right. But still, he is one of my absolute idols, so I would love to spend the time, even if it ended up being a very one-way conversation.

Yuval: Perfect. Gentlemen, thank you so much for joining me today. What's the best way for people to get in touch with you to learn more about your work? Maybe Gustavo, then Iordanis, and then Georgios?

Gustavo: Yeah, anyone who is interested in quantum computing and how we are thinking about using it at Moody's can get in contact with me. I can leave my contact details with you, and if anyone wants to reach out, they can. I'm also on LinkedIn, so anyone interested in knowing more about what we do can send me a contact request, and I'd be happy to accept and have a conversation.

Iordanis: Yeah, the same: through LinkedIn or through the QC Ware website. We collaborate with many people in finance, so we're always happy to talk more about these topics and work together to make it happen.

Georgios: For me, it's the same. You can find me on LinkedIn. If you want to know anything about how we use quantum at HSBC, what we're interested in, and what we're doing, I'll be happy to provide answers and engage in nice discussions. And also, of course, through arXiv papers and such.

So there are ways. Yeah, absolutely.

Yuval: Excellent. Well, thank you so much for joining me today.

Georgios: Thank you.

Gustavo: Thank you.

Yuval: Thank you.