Algorithm Speeds Monte Carlo Predictions on Quantum Computers – InApps 2022

In a world where the uncertain specter of climate change and a global pandemic dominate the headlines, being able to accurately predict potential outcomes can help us better determine which is the best path forward in any given scenario. While the practice of forecasting has been around since ancient times, it’s only in the last several decades that computers have made their mark in the field by propelling data-driven methods of predictive analytics.

One of the most well-known class of computational algorithms for tackling such predictions are Monte Carlo methods, which are used to model the probability of different outcomes when random variables play a role. But running these models can be computationally intensive, and present a challenge to the computational limits to today’s binary-based “classical” computers. Thus, the next logical step is a transition to using more powerful quantum computers in order to more quickly and accurately model the full spectrum of complexity inherent in today’s most pressing problems.

Quantum Speed-Up

In a recent breakthrough that will give the nascent quantum computing industry a boost, UK-based startup Cambridge Quantum Computing has developed a new algorithm that demonstrates a considerable speed-up in how these predictions can be performed, which was detailed in a recent pre-print paper.

“Monte Carlo methods are extremely widespread in science and business — basically, any time some reasoned decision must be made in the face of uncertainty, the chances are that a Monte Carlo method is being deployed,” explained Dr. Steven Herbert, a senior research scientist at CQC. “This includes applications ranging from weather forecasting, to designing particle-physics experiments in the Large-Hadron Collider, to deciding who to award the victory to in a curtailed sporting event (for example, using the Duckworth-Lewis Method in cricket) — and indeed the pricing of sports betting markets.”

In particular, Herbert’s work focused on a technique known as Monte Carlo integration, which is used by banks, asset managers, hedge funds, and financial planners to do things like option pricing and risk analysis.

“‘Monte Carlo integration’ is really just a grandiose name for sampling from some probability distribution (for example, when we roll a dice we uniformly ‘sample’ a number between one and six) and then averaging the samples to approximate the mean,” said Herbert. “However, this simple process is remarkably computationally intensive, and so the fact that there is quadratic quantum speed-up available (quadratic means the quantum algorithm will complete in about square-root of the time it would have taken classically) makes it an extremely attractive prospect to become one of the first applications to see a real useful quantum advantage.”

In contrast, Cambridge Quantum Computing’s new algorithm leverages the ability of quantum computing to model an increased number of random values in a simulation, thus augmenting the scale and accuracy of predictions.

Typically, Monte Carlo simulations run on “classical” computer systems can take hours — sometimes even overnight — to complete. By that time, the results of the simulation may already be obsolete. While basing important decisions on outdated results may not have a huge impact on things like optimizing delivery times in supply chains, it can sometimes mean the difference between life or death when strategizing during critical events like a pandemic.

In contrast, CQC’s new algorithm leverages the ability of quantum computing to model an increased number of random values in a simulation, thus augmenting the scale and accuracy of predictions. It does this by using a hybrid approach, where a portion of the simulation is run on conventional computing systems, and another portion performed using quantum computers, thus striking a balance between the operational cost-efficiency of classical systems, and the increased accuracy and considerable computational power of quantum systems.

“Every method of quantum Monte Carlo integration has a theoretical ‘quadratic’ quantum advantage over classical Monte Carlo,” said Herbert. “However, before this breakthrough, in order to do quantum Monte Carlo integration you also had to perform ‘arithmetic’ operations like inverse-sine and square-root on the quantum computer. Doing so offers no intrinsic quantum advantage, however, and nobody had figured out how to offload these operations to a classical computer. That’s what I did, and if we are to see useful quantum advantage in the ‘NISQ era’ (that is, while quantum computers are still ‘noisy‘ and resource-constrained), then it is absolutely crucial to use the quantum computer only for the precise operations where it gives a computational advantage. Otherwise, the quantum state will decohere before the computation is complete, rendering the results unreliable.”

Broadly speaking, this hybrid approach of combining both classical and quantum systems isn’t new within the industry, with companies like Microsoft and IBM offering their own composite platforms. While quantum computing can offer a remarkable boost over classical computers in solving most complex computations, there are still situations where classical computers can still edge out an advantage over their more error-prone quantum counterparts. In this sense, CQC’s hybrid technique offers a win-win solution to a difficult problem, which had not been available before.

“This proposed algorithm is the state-of-the-art in quantum Monte Carlo integration,” said Herbert. “It can solve any Monte Carlo integral with the full quadratic quantum advantage while using the quantum computer only for those operations where there is quantum advantage. None of the other approaches achieve all of these.”

Herbert added that the recently announced partnership between CQC and Honeywell Quantum Solutions (HQS) will mean more closely coordinated improvements in the development of quantum hardware and software in the future, particularly when it comes to enhancing the implementation of quantum Monte Carlo integration.

“I look forward to working together with the experimentalists and hardware engineers to pinpoint and remedy the precise ways in which algorithms are ‘resource constrained’ when executed on actual quantum hardware, and hence, remove obstacles in the path to quantum advantage. In principle, this approach really is the ‘best of all worlds’, however, in practice there are still application-specific refinements that can be made. That’s our next job: to find partners who are keen to explore the transformative effects that quantum Monte Carlo integration will have on problems relevant to their business, and to engineer tailored solutions.”

Read more in the paper.

Image: Erik Mclean via Unsplash