‘Combinatorics’ problems expose the limits of classical computers and represent the potential for quantum computers to create value for organizations.
COMPUTERS DO ARITHMETIC. Underlying every amazing application of computers today is math, calculated using binary digits or ‘bits.’ The original computers of the early 1950s could perform about 465 multiplications per second — much faster than the ‘human computers’ who performed such calculations for the military and other organizations, as portrayed in the movie Hidden Figures. Today’s computers are billions of times faster.
However, despite these advances, there is an important class of arithmetic problems that remain out of reach for classical computers for the foreseeable future: Large-scale ‘combinatorics’ calculations. Combinatorics problems ask the question, ‘How many ways can this set of objects be combined?’ Such problems can also ask whether a certain combination is possible, or what combinations of objects are ‘best’ by some defined metric. In many cases the number of tasks required to answer these questions — such as counting all possible combinations — grows exponentially as the number of objects grows, and this is what makes finding the answer so computationally challenging. The promise of quantum computers lies in their potential to drastically reduce the time it takes to solve these sorts of problems by utilizing algorithms that make use of ‘quantum effects.’
In this article, we will show that — from a management perspective — quantum computing improves combinatorics calculations, and that this will lead to transformative changes for many industries.
Combinatorics in Practice
Not all combinatorics problems require quantum computers. There are problems that are comparatively easy for humans as well as classical computers and sufficiently large quantum computers to solve (i.e. trying every sequence of 22, 23 and 24 combinations). There are also combinatorics problems that are challenging for humans to solve, but easy for classical computers as well as for sufficiently large quantum computers (i.e. trying every possible combination on a gym lock). Notably, there is no benefit to having a quantum computer solve either of these sorts of problems, because we can work through them with our existing computers. Next, there is a class of combinatorics problems that are challenging for classical computers to solve, but may be comparatively easy for a sufficiently large quantum computer to solve. These are the types of problems where quantum computing will prove useful in business.
Combinatorics problems ask the question, ‘How many ways can this set of objects be combined?’
CYBERSECURITY. The World Economic Forum has highlighted that “quantum computing could make today’s cybersecurity obsolete.” As a result, perhaps more than any other application, the use of quantum technology in cybersecurity has increased government attention and public sector investment. When the U.S. passed the Quantum Initiative Act in 2018 to fund quantum computing, cybersecurity issues were at the core of the discussion. Quantum computing has also received attention in the context of competition between the U.S. and China — again with an emphasis on security generally, and on cryptography in particular.
Underlying this attention and investment is the recognition that the technology underlying modern cryptography uses combinatorics. In 1994, MIT Professor Peter Shor showed that certain types of encryption would become substantially less complex to break with a sufficiently large and coherent quantum computer. Shor’s algorithm highlights the opportunity for solving large-scale problems (or the reverse, creating a large-scale threat) with fully functional and reliable quantum computers.
This does not mean that current cybersecurity solutions will soon be obsolete. As indicated, reliable, large-scale quantum computers don’t exist yet, and the timeline for their arrival is unknown. Nevertheless, there are business opportunities today in preparing for a future of ‘quantum decryption.’ In some contexts, long-term encryption of files is important, such as in the U.S., where classified information must remain secure for decades. The security of stored data is threatened when the key data used to encrypt a file is vulnerable to interception. In such cases, even a small probability of a large-scale quantum computer creates a commercial opportunity in quantum-safe encryption.
Just like the widespread fear of a possible Y2K bug led to massive investment in computer system upgrades, fear of a possible quantum computer using Shor’s algorithm means that developing quantum-safe encryption systems will be prudent in specific sectors. The potential of quantum computing should lead to a change in cryptography practices such as longer key lengths, but not an end to encryption. To this end, the National Institute of Standards and Technology (NIST) is in the process of selecting public key cryptographic algorithms that are capable of protecting sensitive information well into the foreseeable future, including after the advent of quantum computers.
There is a small but growing industry focused on helping companies prepare for the potential end of the usefulness of current encryption techniques. These companies focus both on hardware, such as quantum key distribution, and software solutions. For example, KETS Quantum Security is developing thumbnail-sized, on-chip quantum encryption hardware; and evolutionQ, founded by University of Waterloo professors Michele Mosca and Norbert Lütkenhaus, helps organizations prepare for the ‘Quantum Age’ by providing quantum risk assessment, risk management and cybersecurity solutions. The company recognizes the uncertainty around the arrival of quantum computers, and as such, their tools do not require quantum computers to work. They are focused on preparing systems for the potential for quantum computers to hack existing encryption techniques. In other words, while the expertise of the company founders is in quantum computing, their near-term solutions are largely classical.
CHEMICAL ENGINEERING. Other areas where quantum holds great promise are in material discovery and drug development. Developing useful new molecules requires combinatorics because there are so many possible combinations of atoms, and so many possible ways that they can bond. The histories of material discovery and drug development are full of stories that discuss the impact of serendipity and luck on discovery. For example, Ivermectin is a drug that was first used as a treatment for heartworm in animals. In the 1980s, the drug was further developed as an effective treatment for onchocerciasis (also known as river blind ness) and has gone on to improve the quality of life for hundreds of millions of people.
Nearly as remarkable as the drug’s impact on the world is the amount of luck that was needed for the discovery to be made in the first place: In the 1970s, Satoshi Ōmura, a scientist from the Kitasato Institute in Japan, took a sabbatical in the U.S. While there, he struck up a partnership with Merck. Upon returning to Japan he took soil samples and sent interesting bacteria from those samples to the U.S. for Merck to assess. One of these samples, taken near a golf course in Japan, contained bacteria which eventually was used to develop Ivermectin.
In recent years, scientists have increasingly turned to computational chemistry simulations for these applications. With computational chemistry, scientists try to understand both a material’s molecular structure and its properties. Based on these simulations, they then choose the best candidates to ultimately synthesize. The goal of computational chemistry has led to cost efficiencies in the R&D process relative to prior methods which involved trial and error or simple luck.
However, computational chemistry simulations are in and of themselves challenging. First, a molecule‘s properties are strongly influenced by its lowest energy state. Thus, to generate inferences on both a molecule’s structure and its expected chemical properties, the starting point of many simulations is to identify the structure that will yield a molecule’s lowest energy state.
Here, combinatorics problems again arise. For example, simulating a molecule involves assessing the interaction between every electron and every proton in every atom in the molecule and the interaction of those particles with every other atom in the molecule. Notably, every electron from every atom is repelled from every other electron from every other atom, and every electron from every atom is attracted to every proton from every other atom. Thus, the addition of an ‘incremental atom’ to a molecule can lead to an exponential increase in the number of interactions that have to be accounted for. Because of this, only comparatively small molecules are accessible to highly accurate, generic solutions using classical computers.
One approach, pioneered by D-Wave Systems over the last 20 years, is to explore optimization problems that might display an advantage for an algorithm called ‘quantum annealing.’ Quantum annealing aims to find the best solution to a problem by exploiting the tendency of quantum mechanics to ‘tunnel’ through barriers between different possible solutions. In September 2020, D-Wave launched a new hardware system useful for this purpose. Since the approach may be amenable even on relatively noisy quantum devices, it has inspired other hardware manufacturers to explore a variety of algorithms for their own current hardware.
Optimism regarding quantum computing’s eventual impact on Chemical Engineering is high, in particular following IBM Quantum Computing’s simulation of beryllium hydride in 2017. As University of Toronto scientist and quantum entrepreneur Alán Aspuru-Guzik suggested following IBM’s achievement, “When quantum computers are able to carry out chemical simulations in a numerically-exact way, this may lead to the discovery of new small-molecule drugs or organic materials.”
OTI Lumionics is one of many companies that uses a computational approach to molecule discovery in which they try to determine a molecule’s structures and properties jointly. OTI starts with thousands of potential candidates to simulate and then pares the list down using computational methods to those that may have the desired properties, based on estimates of molecular structure.
OTI is experimenting with different quantum hardware platforms for materials creation and is one of the first companies to model its problems in a way that can be implemented on D Wave’s quantum annealing hardware. Their work in quantum has provided a twofold benefit for the firm, one long term and one near term: The long-term benefit is that OTI will be quan tum-ready if and when quantum computers become sufficiently powerful; and the short-term benefit is that OTI’s work in quantum has yielded near-term returns by helping the company de rive quantum-inspired algorithms that it can then apply on current classical computing architectures.
From arbitrage to credit scoring and derivatives development, combinatorics challenges are common in finance.
Recently, OTI was one of four companies to be invited to use Microsoft’s new quantum-inspired service as part of Azure Quantum. New evidence suggests that OTI’s quantum-inspired algorithms combined with Azure Quantum on classical hardware perform better than other classical methods that can be run on the same hardware. These improvements on classical hardware are important. According to OTI CEO Michael Helander, the cost to experimenting with quantum — measured as the opportunity cost to assigning staff to work with quantum technologies as opposed to some other platform—has been outweighed, even in the near term, by the benefit derived from creating these new quantum-inspired algorithms.
Other companies are also exploring the use of quantum computing for material or drug discovery: Menten AI utilizes a combination of quantum computing, synthetic biology and machine learning to aid in the creation of new proteins; and Zapata Computing, which pioneered a number of near-term quantum computing methods for chemical simulations, has developed a commercial software platform featuring ‘quantum libraries’ with applications in chemistry, biopharma, machine learning and more.
BANKING AND FINANCE. From arbitrage to credit scoring to derivative development, combinatorics challenges are common in banking and finance. One way banks and other financial institutions deal with these problems is to simplify them to reduce the set of possible solutions. The issue is, constraining the set of possible solutions means that sometimes the best solution is not found.
Many of the challenges in this arena relate to the classic ‘travelling salesman problem’ that has been a staple of operations research for decades: The idea is that one salesman has a number of cities to travel to and needs to get to every city once. The goal is to find the shortest route that (1) goes to each city once and (2) ends up in the starting city. From a value proposition perspective, the benefit to using the shortest route is straightforward: The salesman will presumably generate the same revenue by travelling to each city, while minimizing travel costs by pursuing the most efficient route.
It is relatively straightforward to find the shortest route when there are comparatively few cities to travel to (e.g. four). However, the problem becomes less and less tractable as more and more cities are added. When the number of cities gets sufficiently large, quantum computing may eventually offer the potential to speed up the process to the point that finding a global minimum ‘route’ through all possible cities becomes possible.
A surprisingly large number of business problems can be framed as variations of the travelling salesman, including circuit design, package delivery and train scheduling. More specifically, researchers have identified combinatorics problems in banking and finance that might benefit from quantum computing, including portfolio optimization, foreign exchange arbitrage and credit scoring.
In credit scoring, for example, banks use data to predict which customers are likely to default, and which are likely to repay their loans. There are two types of errors that banks can make when making a loan decision. One arises when the bank’s credit scoring model suggests lending money to a client and the client subsequently defaults; and the other arises when a bank’s model suggests not lending to a customer when the customer would not have defaulted. It is costly to lend money to people who default; but it is also costly to refuse profitable customers.
One might assume that banks would like to incorporate as many different factors as possible when credit scoring. However, a paper by quantum computing software company 1QBit highlights a cost to using a large number of factors: verifying the accuracy of the information. After all, without robust verification, borrowers may omit key information or outright lie. Therefore, lenders might be willing to sacrifice prediction accuracy for a reduced cost of verifying the accuracy of a loan application.
Many other financial problems involve understanding the set of possible outcomes for a number of assets. For example, the decision to invest in a portfolio of stocks involves simulating the distribution of possible future prices from the portfolio’s underlying stocks. With a small number of underlying assets to model, these simulations are relatively straightforward, and banks and financial institutions use a tool called ‘Monte Carlo simulation.’ These simulations are widely used for derivatives pricing and risk management.
As the number of underlying assets and factors grows, the pricing of advanced derivatives and the construction of value-at risk models can require simulation of the joint distribution of a large number of assets. These are combinatorics problems because the future value of one asset may be related to the values of the other assets. Risk assessment requires more than knowing the possible set of future values of the various assets: It also involves knowing how those values relate to each other.
For example, suppose a bank wants to conduct a risk assessment on a mortgage portfolio for homes in Florida and Nevada. If real estate prices in those states move together — so that a crash in Florida prices means a likely crash in Nevada prices — then that portfolio is likely to be risky. In contrast, if the prices are independent and do not move together, then the risk of that portfolio is lower. But if we add in all other U.S. states, plus many other countries, the complexity of this problem increases substantially. In such a setting, Monte Carlo becomes very slow on a classical computer and this limits the ability to price complex derivatives or simulate value-at-risk models in a timely manner.
Interestingly, a McKinsey report notes that many banks have reduced the use of Monte Carlo simulations for value-at-risk calculations. The report cites increasing computational complexity as a possible reason, emphasizing that the number of factors that banks need to simulate has grown over time. The potential for quantum-accelerated Monte Carlo simulation is a speed-up with respect to the underlying simulation itself — and this may enable new types of derivatives to be priced or risk models to be simulated more quickly.
Given the computational intensity of many banking and finance problems, there is potential for profitable applications of quantum computing as the technology matures. Some companies have already made progress: CogniFrame is developing a ‘financial services operating layer’ that will be positioned atop the Quantum Cloud and used to help solve challenging optimization and simulation problems; and Multiverse Computing is using quantum and quantum-inspired algorithms to develop a comprehensive software suite to solve quantitative financial and macroeconomic simulation problems.
Such applications are promising, and they may not require a fully functioning large-scale quantum computer to provide business value. This is another area where quantum-inspired algorithms might arise that make it easier to solve combinatorics problems on classical computers. Nevertheless, the highest value combinatorics problems in finance and banking will likely require substantial advances in quantum computing technology. Until such technology becomes available, there is near-term potential for quantum-inspired algorithms to generate profit opportunities.
In Closing
Francesco Bova is an Associate Professor of Accounting at the Rotman School of Management and is actively involved in Rotman’s Creative Destruction Lab as Academic Lead for CDL Toronto and the Lab Economist for CDL’s Quantum Stream.
Avi Goldfarb is the Rotman Chair in Artificial Intelligence and Healthcare and Professor of Marketing at the Rotman School as well as Chief Data Scientist at the Creative Destruction Lab. He is the co-author with Rotman Professors Ajay Agrawal and Joshua Gans of Prediction Machines: The Simple Economics of Artificial Intelligence (HBR Press, 2018) and the forthcoming Power and Prediction: The Disruptive Economics of Artificial Intelligence (Harvard Business Review Press, November 2022).
Roger Melko is Canada Research Chair in Computational Many-Body Physics and Professor of Physics and Astronomy at the University of Waterloo. This is a condensed version of a paper, “Commercial Applications of Quantum Computing”) that appeared in EPJ Quantum Technology.
This article was published for the Rotman Management Magazine.
Learn about your GP Leadership profile
Where do you rank in your Power, Challenge, Aspirational and Foundational traits?
