At D-Wave, technical advisors like me often encounter a common question from prospective customers: “How do we know your hybrid solver is better than [insert classical tool] for our specific problem?”
To determine whether our hybrid quantum solvers are the right fit for your problem, we use a set of guidelines during the pre-sales process. As you’ll see, it’s important to note that problem formulation plays a key role in determining the solver’s suitability. Different solvers are built to solve different problems. Comparing two inherently different solvers is a bit like comparing apples to oranges — so you must do it carefully.
Adding to our family of hybrid solvers, we recently announced the launch of our new nonlinear-program hybrid solver, which raises the bar on performance, scalability, and ease-of-implementation — doubling problem-solving capability and handling up to two million variables.
This new formulation method has several advantages beyond performance, including the ability for the D-Wave team to more easily modify the solver as our capabilities evolve.
Watch the announcement video here.
Assessing the Customer’s Problem
When assessing a prospective customer’s potential problem, we use the following guidelines to determine which solver is best suited for the specific scenario:
What are the (decision) variables?
Are your variables binary, discrete/integer, or continuous? What are the relative mixes of those types? For problems largely made up of binary variables or integers with low ranges, our hybrid constrained quadratic model (CQM) solver excels.
The new solver, however, can handle exotic variable types such as lists or permutations. These can come in handy when problems obey certain symmetries, e.g., the 𝑛-location quadratic assignment problem (QAP). When solving the QAP with binary variables, one would need to use 𝑛² binary variables to explore a solution space with up to 2**(n**2) potential solutions. Think about that: with just 𝑛 = 17 locations, the number of possible solutions for a QAP exceeds the theorized number of atoms in the observable universe. With the new solver, we can make use of the QAP’s specific constraints and only use 𝑛 permutation variables, reducing the solution space to just 2ⁿ entries. That is a significant reduction in problem difficulty.
Is your problem nonlinear?
If the function you are trying to minimize or maximize only has linear terms, e.g. 𝑥₀− x₁ + 3x₂ + 10x₃, then we call it a “linear problem.” The CQM solver excels when there are many quadratic terms, e.g., 𝑥₀x₃. The nonlinear solver, as the name implies, is built to handle extremely nonlinear terms such as 𝑥₀x₂x₄, max/min functions or even the logical OR.
This nonlinearity is important. If the answer is “yes,” meaning you have nonlinear terms, then the chances of success with annealing quantum computing increases. Though they do not typically immediately benefit from annealing quantum solutions, it is possible for linear problems to benefit from D-Wave’s tools. We will explain this later when discussing linearization.
How many decision variables and constraints are there?
Our CQM hybrid solver can handle up to 500,000 variables and 100,000 constraints. The nonlinear program solver can handle up to 2,000,000 constraints and variables at once. If your problem still doesn’t fit, we can break it up and solve it piece by piece. In some cases, this is impractical, but it’s often a viable option.
Note that everything we’ve said so far assumes that the customer’s problem is immutable, but this is rarely the case. D-Wave’s professional services experts excel at restructuring and rewriting problems to make them more compatible with our solvers. In some cases, the customer may be inadvertently mischaracterizing the problem to fit their current tools, when in fact, our solvers might be a more natural fit. Let’s take linearization as an example.
Consider a simple binary optimization problem where we are trying to minimize the following objective function:
𝑓(𝑥,𝑦,𝑧) = 𝑥 + 𝑦 + 𝑧 − 𝑥𝑦 − 2𝑥𝑧 − 3𝑦𝑧.
With our hybrid tools, we can simply plug in this problem and solve it directly. If we were dealing with a linear programming tool instead, we’d need to introduce more complexity to this simple problem. First, we’d need to define binary variables:
𝑎 = 𝑥𝑦, 𝑏 = 𝑥𝑧 and 𝑐 = 𝑦𝑧 .
Second, we’d then introduce constraints to enforce:
𝑎 − 𝑥𝑦 = 0 , 𝑏 − 𝑥𝑧 = 0 and 𝑐 − 𝑦𝑧 = 0 .
Now our three-variable unconstrained binary problem has become a six-variable problem with three constraints.
To get the inherently quadratic problem ready for a linear solver, we had to make it more complicated by doubling the number of variables and adding three constraints where previously there were none. An advantage of using any D-Wave solver is that the problem doesn’t have to get more complicated just to fit into a solving tool. I have had discussions with customers who couldn’t fit highly quadratic problems on their linear solvers while I could use our hybrid tools to solve similar problems scaled up by several orders of magnitude. As discussed before, our new nonlinear-program solver takes this to another level and can easily handle a larger variety of nonlinear terms than even our CQM hybrid solver can.
When Comparing Solvers, Context Is Key
Now that we’ve provided some solid guidelines to follow, let’s investigate why it’s challenging to compare solvers across all problem types one might encounter. The first question to ask is how to define a winner in any competition between solvers. Typically, people need a tool that either provides faster or better solutions.
Even then we run into some ambiguity — for example, when balancing trade-offs in solution time and quality. If we find a solution that’s ten times faster than the competitor but with 5% less quality, is that acceptable? In a situation where we are running a daily calculation, such as routing for a delivery service, such a loss in quality might be worth the immense speedup. However, if we were designing therapeutic molecules in a pharmaceutical lab, then the downside could be too great a cost.
Once we’ve settled on whether to evaluate a tool on its criteria of “better” or “faster,” we then must consider what metrics to look at. We could just take runtime or solution quality, but looking at each independently can lead to problems with tradeoffs, much like I described previously. Instead, it is often practical to use metrics that combine solution quality and runtime. “Time to solution” (TTS) — the time required to have a high probability of getting a certain solution quality — is a useful metric. However, if your business problem is highly complex, TTS is impractical as it requires running the problem multiple times. An alternative metric, “solution to time” (STT) fixes a maximum time and evaluates which solver provides the best solution within that timeframe.
Small Details Can Change Everything
During pre-sales conversations, we aim to ensure that our prospect’s problem is well-defined. Even seemingly insignificant or obvious details can dramatically transform the nature of the problem and its suitability for different solvers. A minor change — such as adding a constraint requiring employees to have two consecutive days off in a scheduling problem — can turn a linear problem into a quadratic one, making it more suitable for D-Wave’s hybrid tools.
For example, a customer may come to us because they want to reduce employee turnover by making better schedules. They have E employees and seven-day-long shifts. Each employee j has a preference pⱼₖ for shift k.
We want to find a shift schedule that maximizes preferences.
To write this problem in a way that our solvers can understand, we define 7E variables where 𝑥ⱼₖ = 1 if employee j is scheduled for shift k and 0 otherwise. We will skip some basic steps such as ensuring that we have the minimum number of employees working each day. Our objective function thus becomes the following:
Note that this is a linear problem. Though it will run on our hybrid tools, formulating it this way doesn’t render our tool more useful than a classical linear solver. Regardless, we run the code, obtain the schedule, and show it to our customer.
They immediately realize something is wrong. Why are some employees working 7 days per week? They forgot to tell you that union rules require that each employee gets two consecutive days off each week. This changes everything. If employee j is not working shift k, then they must also not work either shift k+1 or k-1. We can formulate this as:
Now we have quadratic terms. This small detail completely changes the nature of the problem to one suitable for D-Wave’s hybrid tools.
The Challenge of Comparing High-Quality Solving Tools Across All Possible Problems
The examples provided above are highly simplified, but the point remains the same: if you want to compare two high-quality solving tools, it is challenging to do so in a fair and accurate way across all possible problems one might encounter. The fact that tiny differences in problem formulation can lead to huge disparities in problem plausibility means that two examples that are nearly identical to an untrained eye can be worlds apart from the point of view of the solver.
We must also consider the so-called “no free lunch” theorem, which states that exceptional performance on one problem doesn’t mean the solver will perform well on another. Because of this, we at D-Wave strongly suggest testing our solvers against the actual business problem you are trying to solve and avoid a suite of benchmarking problems unrelated to your use case. However, if you are still looking to use a problem library, the CQM solver does quite well with the quadratic assignment problems mentioned earlier. The new nonlinear hybrid solver, now available through D-Wave’s Leap™ quantum cloud service, does even better.
Navigating the complexities of hybrid quantum solvers can be daunting, but our team is here to guide you through the process. By working together to understand your unique problem and its nuances, we can help you determine whether D-Wave’s hybrid solvers are the best fit for your needs.
Don’t hesitate to reach out to D-Wave for assistance in exploring the potential of quantum computing for your organization.
Acknowledgments:
I’d like to recognize that this blog post is an amalgam of many conversations I’ve had with D-Wave’s algorithms and benchmarking teams, and I am very grateful for their help.
References:
About D-Wave
D-Wave is a leader in the development and delivery of quantum computing systems, software, and services, and is the world’s first commercial supplier of quantum computers. Our mission is to unlock the power of quantum computing today to benefit business and society. We do this by delivering customer value with practical quantum applications for problems as diverse as logistics, artificial intelligence, materials sciences, drug discovery, scheduling, cybersecurity, fault detection, and financial modeling.
Discover more at dwavequantum.com and begin your quantum journey today.
