How to Solve Optimization Problems with Azure Quantum QIO (Part 1)

Learn how you can leverage Azure Quantum QIO to solve optimization problems.

This blog is part of a 5-part-series where I give you an overview of the process for solving optimization problems with Azure Quantum QIO. We’ll start with the overall process (part 1), have a look at how to write cost functions representing the optimization challenge (part 2 and part 3), see how to submit these to Azure Quantum (part 4), and conclude with the validation and interpretation of the optimization result returned by Azure Quantum (part 5).

Introduction

Azure Quantum is a great online service for using quantum technologies for various scenarios, from optimization, simulation, machine learning, etc. The service offers two paths of quantum solutions:

  • Quantum Computing
    Here you can submit gate-based quantum algorithms (specified in Q#, Qiskit, Cirq) to quantum hardware. In today’s NISQ-era only limited in numbers of qubits, but great for preparing yourself for a future of scaled quantum machines.
  • Quantum Inspired Optimization (QIO)
    QIO efficiently simulates quantum effects (like tunneling or annealing) on classical hardware. Turns out that this approach provides a speedup over traditional approaches without the need for using actual quantum computers. This way, you can already solve optimization problems with quantum approaches where quantum hardware available today is not scalable enough.

In this blog series, we’ll focus on Quantum Inspired Optimization (QIO). We’ll have a look on how to solve actual business optimization problems with Azure Quantum. This includes deriving a processable format of the business problem, submitting that to Azure Quantum and post-process its result to give a business answer to the business question.

The Overall Workflow

Optimization is the process of finding the best solution to a problem given by its desired outcome and constraints. The task is to evaluate a large number of alternative configurations to optimize a certain metric. Such a metric could be costs, processing time, risk, etc.

Examples for such optimization problems are:

  • “In what order should I execute certain tasks such that the overall processing time gets minimized and certain restrictions for concurrency etc. are adhered?”
  • “Out of several investment options, which ones should I choose so that risk of loss gets minimized while covering as many investment classes as possible?”
  • “How should I distribute a set of containers to a certain numbers of ships so that the distribution is as even as possible?”

Image 1 illustrates the process for solving these types of problems: Business problem specifications (step 1) cannot directly be submitted to Azure Quantum. The solvers have no understanding of “processing time”, “risk”, “weight difference” or any other metric, you’d like to minimize.

The overall workflow for solving optimization problems with QIO
Image 1: The overall workflow for solving optimization problems with Azure Quantum QIO

An optimization problem needs to be translated into a form the optimization solver can understand (step 2 and step 3). That form is a cost function or - to be more precise - a binary quadratic model (BQM). A BQM describes how the metric that needs to be minimized behaves in relation to variables representing the different options to be evaluated. These variables are binary, i.e. depending on the model type they can be either \( \lbrace 0, 1 \rbrace \) for QUBO (quadratic unconstrained binary optimization) models or \( \lbrace -1, 1 \rbrace \) for Ising models.

Quantum jobs containing the specification of a BQM can then be submitted to an Azure Quantum workspace (step 4) to be processed by a quantum solver. After the job completes, a “configuration” representing an optimum solution is returned.

That configuration is a series of \( 0 \) and \( 1 \) (for QUBO) or \( -1 \) and \( +1 \) (for Ising). The information encoded into this configuration needs to be validated and converted into a business solution representation (step 5) as you’re not interested in a series of binary values but something like

  • “First complete task C, then task A, then task B” or
  • “Put x% of your money in stocks, y% in bonds, z% in commodities” or
  • “Load containers 3, 5, and 6 on ship A, and containers 1, 2, and 5 on ship B”

In part 2 of this blog series, you’ll learn what a binary quadratic model (BQM) mathematically is and how to derive one from a given optimization problem: from a set of soccer players, assign each player to one out of two or more teams so that all resulting teams are of (near-)equal strength and each team has one goalkeeper.

For diving deeper into this topic, I’d recommend following resources:

Important pages on the official Azure Quantum documentation

Online courses on MS Learn