Back to Quantum ABC's

Quantum Computers will be ideal for solving "Combinatorial Problems". But what is a Combinatorial Problem?

Image generated by the author using Midjourney

Over the past few posts, I’ve done a deep dive into each of the main Quantum Computing modalities, and while I try to write from a layman’s perspective, digging into the modalities can veer into technical territory. This post is intended to zoom back out and provide a high-level primer/re-orientation for why Quantum Computing is getting so much attention.

Some of you may be new to Quantum and others may be digging in but getting confused with attempting to understand what causes Superposition (a qubit being in multiples states at once), Entanglement (qubits can be inherently connected and correlated) and other quantum principles. So whatever your position on the learning curve, let’s drop the quantum physics and linear algebra and try and reframe the approach to appreciating Quantum Computing’s power through the lens of a non-physicist.

So, this post will NOT cover qubits or gates or trapped ions or dilution refrigerators. No strange Bloch spheres, Hadamard gates, T2 lifetimes or quantum circuit diagrams. Let’s try and approach this from a real-world application, with something many of us use regularly if not daily. Shaving cream.

Shaving Cream?

Yes, let’s see how designing shaving cream can benefit from a Quantum Computer.

Imagine a company that makes a premium shaving cream. Its scientists have developed 12 proprietary beard- and hair-softening chemicals. Each one is similar in purpose, but slightly different in structure and behavior. Some soften coarse hair better. Some absorb faster. Some are more stable. Some feel better on skin.

Now let’s say each of those 12 softening chemicals can be prepared in 5 different forms. Maybe one is emulsified, one is whipped, one is suspended differently, etc.

Right away, we have:

12 softeners × 5 forms = 60 possible starting points (multiplication is the hardest math in this post, but don’t worry if your math is not strong, just assume the totals described here and below are accurate).

That does not sound too bad.

But shaving can be hard on skin so a good shaving cream needs skin protectants.

Let’s say the company has 25 possible skin protectants, and each of those can also appear in 5 different forms. And let’s further assume shaving cream can include between 1 and 3 skin protectants.

If the formula uses just one skin protectant, that is:

25 protectants × 5 forms = 125 choices

Still manageable.

But if the formula uses two skin protectants, the number jumps. We are no longer just choosing one thing. We are choosing pairs. That gives us:

300 possible pairs × 25 form combinations = 7,500 choices

And if the formula uses three skin protectants:

2,300 possible three-protectant combinations × 125 form combinations = 287,500 choices

Add those together and the company has:

295,125 possible skin-protectant combinations

Now combine those with the 60 possible softener starting points:

60 × 295,125 = 17,707,500 possible shaving cream formulations

Or almost 18 million possible products.

And this is still a cartoonishly simple example.

We have not added fragrance, texture or shelf life. We have not added cost differentials, regulatory constraints or manufacturing yield. We have not added whether the cream works better for sensitive skin, oily skin, dry skin, curly hair, coarse hair, or people shaving in cold weather versus hot weather.

This is where the real world gets interesting.

The challenge is not that the company lacks ideas. The challenge is that it has too many possible ideas.

This is called a combinatorial problem. A small number of choices, when combined, can create a surprisingly large number of outcomes. The math underneath this involves factorials — the exclamation point math you may remember from school, where 6! equals 6 x 5 x 4 x 3 x 2 x 1 = 720. Combinatorial problems are where Quantum Computers will shine. I’ve referenced this in past posts, often using a seating chart at a party as the example/problem. For example, if we have a table with 8 guests, arranging a seating chart seems fairly mundane, but there are 8! or over 40,000 different seating arrangements. Throw a dinner party with just 20 guests and suddenly there are 20! or more than 2 quadrillion (a 2 with 18 zeroes) seating combinations!

Now let’s shift back to the shaving cream. What does the company do about those 18 million possible product combinations? They can’t realistically create and test every one. So maybe they use some basic reasoning to determine the likely best ones? That is exactly what companies do today. They use experience, chemistry, historical data, intuition, simulation, and trial-and-error to narrow the field. They do not test 18 million shaving creams. They make educated guesses. Some of those guesses are very good. Some are not.

But what if the best formulation is quite novel?

What if the best shaving cream is not made from the ingredient that looks best on its own, but from a strange combination of ingredients that only works because of how they interact together? In complex systems, the winner is often the best combination, accounting for various trade-offs.

A softener that looks average by itself might become extraordinary when paired with the right skin protectant in the right physical form. Another ingredient might work beautifully in the lab but fail in manufacturing. One combination might produce better glide but worse shelf life. Another might be slightly less luxurious but dramatically cheaper to produce.

This is not just a shaving cream problem. It is a drug discovery problem. A battery chemistry problem. A fertilizer problem. A logistics problem. A portfolio construction problem. A semiconductor materials problem. A supply chain problem. In other words we are immersed in an abundance of combinatorial problems.

This is why quantum computing matters.

Quantum computers are not simply “faster computers” in the normal sense. They are not magic laptops that run Excel at lightspeed. Their promise is more specific and often more interesting. They will be unusually good at exploring certain kinds of enormous possibility spaces, especially where the answer depends on interactions among many variables (in other words, combinatorial problems).

In our shaving cream example, using a classical computer would be impractical since it would have to model and run possible outcomes on nearly 18 million different combinations of ingredients, one at a time. However, this is the kind of problem where quantum computers could eventually matter a lot. Not because they magically test every possible answer at once — that is the oversimplified version — but because they are built for problems where the answer depends on how many variables interact together. In a classical trial-and-error process, the shaving cream company has to narrow the field using educated guesses: test this ingredient, eliminate that one, tweak the formula, repeat. A quantum computer, in theory, could approach the problem more like searching a landscape. It could use the known characteristics of each ingredient such as softening power, irritation risk, stability, cost, texture, shelf life and look for combinations that best satisfy the goal. The real power is not in evaluating one ingredient at a time. It is in finding the best recipe among millions of possible recipes, especially when the winning answer may come from a combination no chemist would have thought to test first.

I am not a shaving cream expert, but wanted to use a relatable real-world problem to help show why combinatorial problems are so prevalent and so difficult. Much of the focus on Quantum Computing has been on encryption/decryption, which is a real opportunity/threat, but the broadest benefit we will gain form Quantum Computers will be their ability to solve large combinatorial problems in a reasonable amount of time. This will lead to better batteries, new drugs, more efficient transportation logistics, better weather forecasts, optimized investment portfolios and a myriad of other combinatorial solutions. Quantum Computers are not yet powerful enough to lead to advances in these areas, but they are getting better all the time and should be contributing to such problems/solutions in coming quarters not years. And while that timeline may be controversial to some, the ability of Quantum Computers to solve combinatorial problems is a well accepted fact.

---

Disclosure: The author is a venture investor with investment interests in quantum and may have an interest in companies discussed in this post. The views expressed herein are solely the views of the author and are not necessarily the views of Corporate Fuel Partners or any of its affiliates or any companies it has investment interests in. Views are not intended to provide and should not be relied upon for investment advice.