# Hybrid Optimize

The `strangeworks-hybrid-optimize`

package allows users to run, construct and solve problems with the hybrid QAOA + annealer algorithm on multiple hardware providers.

## Overview

The hybrid QAOA + annealer algorithm allows you to solve large quadratic unconstrained binary optimization (QUBO) and Ising problems by making use of the power of quantum and quantum insipred resources. It is a classical-quantum hybrid algorithm: the general idea is that we break up the problem/graph into many sub-problems/graphs and solve each of these seperately on either gate-based devices with the Strangeworks QAOA algorithm or quantum or quantum inspired annealers through our Strangeworks Optimization service. We then take the solutions to each of these sub-problems and perform one final optimization on a gate-based quantum device to calculate the final answer, see below for more details.

This page will describe how to install and begin to use the Strangeworks Hybrid service as well as giving some technical details of the algorithm.

## Prerequisites

In order to use the AWS Hybrid job service and/or the IBM Cloud devices, the user must have a billing account properly enabled. Without this, the user can still utilize qiskit runtime jobs through IBMs free services.

## Installation

To get started, make sure you have **Python 3.10 or 3.11** (installation) and are familiar with setting up and using virtual environments.

Install packages using pip:

`pip install -U pip && pip install strangeworks-hybrid-optimize`

Import package into python:

`from strangeworks_hybrid_optimize import StrangeworksHybrid`

### Authentication

Any issues authenticating, you may need to add a Hybrid Optimize resource to your account through the Platform, https://portal.strangeworks.com

## Usage

Before running:

- Set up your environment and install
`strangeworks-hybrid-optimize`

- In the portal, Activate Strangeworks Hybrid Optimize Service to create a Resource
- Replace
`your-api-key`

with your key from the Portal homepage - Use examples below to utilize the various functionality. See Examples section below for an example script.

Authenticate with strangeworks python sdk using users API token:

`strangeworks.authenticate(api_key="your-api-key")`

Get a Hybrid Optimize resource using qaoa sdk extension and users resource slug:

`sw_hybrid = StrangeworksHybrid(resource_slug="your-resource-slug"))`

List compatible backends for the qaoa product:

`sw_hybrid.backends()`

List all user qaoa jobs:

`jobs = sw_hybrid.job_list()`

Add credentials for sub-service:

`sw_hybrid.add_sub_resource_credentials(resource_slug="your-child-job-resource-slug")`

Run problem:

`sw_job = sw_hybrid.run(backend,`

backend_sub=backend,

problem=problem,

hybrid_params=hybrid_params,

problem_params=sub_problem_params)

Retrieve job with specific slug and check status:

`sw_job = sw_hybrid.get_job(job_slug)`

status = sw_job.get("status")

Display results

`result = sw_hybrid.get_results(sw_job,calculate_exact_sol=True, display_results=True)`

## Examples

### Gate-Based sub problems: AWS Braket

Here is an example run for a small problem on an AWS Braket simulator. In this case we run both the sub-problems and the final optimization on the same backend.

`import strangeworks`

from strangeworks_hybrid_optimize import StrangeworksHybrid, QAOAParams, HybridParams

import strangeworks_hybrid_optimize.utils as utils

strangeworks.authenticate(api_key=" ", store_credentials=False)

################################

######## Create problem from QUBO

nodes = 10

seed = 0

n = 3

problem = utils.get_nReg_MaxCut_QUBO(n, nodes, seed)

################################

################################

######## Define algorithm parameters for sub-jobs

sub_problem_params = QAOAParams(

maxiter=50, # Maximum number of iterations in algorithm

shotsin=1000, # Number of times quantum circuit is measured at each iteration

p=1, # Optional Input: Controls the depth of the Quantum Circuit ansatz. Default p=1

theta0=[1.0, 1.0], # Optional Input: Starting point for variational parameters. If specified must be equal to 2p

alpha=0.1, # Optional Input: Cvar parameter, float between 0 and 1 - https://arxiv.org/pdf/1907.04769.pdf. Default alpha=1.0

optimizer="COBYLA", # Optional Input: Classical optimizer to use:

# Possible Values:

# 'COBYLA' (Default), 'Nelder-Mead', 'Powell', 'CG', 'BFGS', 'Newton-CG', 'L-BFGS-B', 'TNC',

# 'SLSQP', 'trust-constr', 'dogleg', 'trust-ncg', 'trust-exact', 'trust-krylov'

# Additionals for IBM backends: 'SPSA', 'NFT'

ising=False, # Optional Input: is the problem an Ising problem or a QUBO problem, i.e. are the values of the variables {-1/2,+1/2} (Ising) or {0,1} (QUBO, Default)

warm_start=False, # Optional Input: Run warm start qaoa or not - https://arxiv.org/abs/2009.10095. Default False: Standard QAOA ansatz

)

################################

######## Define parameters for creating sub-problems and running final optimization

Nf = 2 # Size of final vqe

Ns = pow(2, Nf) # Number of sub-systems, upper bound, Ns = pow(2, Nf)

Ng = 4 # Size of sub-systems

# Options for final vqe/qaoa, below are the additional options for this hybrid qaoa and the mandatory ones.

# Other optional arguments may be specifed: https://docs.strangeworks.com/apps/qaoa

hybrid_params = HybridParams(

Nf=Nf, # Size of final vqe

Ns=Ns, # Number of sub-systems

Ng=Ng, # Size of sub-systems

problem_size=nodes, # Total problem size

type_subsystem="weighted_random", # How to break up problem into sub-problems

maxiter=50, # Maximum number of iterations in algorithm

shotsin=1000, # Number of times quantum circuit is measured at each iteration

)

# Currently need to specify the resource slug of the child-jobs

# Can either be a StrangeworksQAOA resource or a StrangeworksOptimize resource

sw_hybrid = StrangeworksHybrid(resource_slug="your-resource-slug")

sw_hybrid.add_sub_resource_credentials(resource_slug="your-child-job-resource-slug")

backend = "SV1" # Change this to ibm backend name or another aws device name

sw_job = sw_hybrid.run(backend,

backend_sub=backend,

problem=problem,

hybrid_params=hybrid_params,

problem_params=sub_problem_params)

result = sw_hybrid.get_results(sw_job,calculate_exact_sol=True, display_results=True)

🥳 Success! You may view your job in the portal.

😅 Something went wrong? Find us in Slack!

### StrangeworksOptimization sub problems: AWS Braket + Dwave

Here is an example run for a small problem, where the sub-problems are run on Dwave through the StrangeworksOptimization service and the final optimization is run on an AWS Braket simulator.

`import strangeworks`

from strangeworks_hybrid_optimize import StrangeworksHybrid, HybridParams

import strangeworks_hybrid_optimize.utils as utils

strangeworks.authenticate(api_key=" ", store_credentials=False)

sw_qaoa = StrangeworksHybrid(resource_slug=" ")

################################

######## Create problem from QUBO

nodes = 10

seed = 0

n = 3

problem = utils.get_nReg_MaxCut_QUBO(n, nodes, seed)

################################

################################

######## Define algorithm parameters for sub-jobs

backend = "dwave.Advantage_system4.1"

sub_problem_params = OptimizationParams(

solver={"solver": backend, "solver_options": {}},

resource_slug="optimization-service-child-resource-slug", # resource slug for child job: dwave service etc.

)

################################

######## Define parameters for creating sub-problems and running final optimization

Nf = 2 # Size of final vqe

Ns = pow(2, Nf) # Number of sub-systems, upper bound, Ns = pow(2, Nf)

Ng = 4 # Size of sub-systems

# Options for final vqe/qaoa, below are the additional options for this hybrid qaoa and the mandatory ones.

# Other optional arguments may be specifed: https://docs.strangeworks.com/apps/qaoa

hybrid_params = HybridParams(

Nf=Nf, # Size of final vqe

Ns=Ns, # Number of sub-systems

Ng=Ng, # Size of sub-systems

problem_size=nodes, # Total problem size

type_subsystem="weighted_random", # How to break up problem into sub-problems

maxiter=50, # Maximum number of iterations in algorithm

shotsin=1000, # Number of times quantum circuit is measured at each iteration

)

# Currently need to specify the resource slug of the child-jobs

# Can either be a StrangeworksQAOA resource or a StrangeworksOptimize resource

sw_hybrid = StrangeworksHybrid(resource_slug="your-resource-slug")

sw_hybrid.add_sub_resource_credentials(resource_slug="your-child-job-resource-slug")

backend = "SV1" # Change this to an ibm backend name or another aws device name

sw_job = sw_hybrid.run(backend,

backend_sub=backend,

problem=problem,

hybrid_params=hybrid_params,

problem_params=sub_problem_params)

result = sw_hybrid.get_results(sw_job,calculate_exact_sol=True, display_results=True)

🥳 Success! You may view your job in the portal.

😅 Something went wrong? Find us in Slack!

## Accepted Problem Input Types

### Network X Graph

`import strangeworks_qaoa.utils as utils`

nodes = 4

seed = 0

n = 3

problem = utils.get_nReg_MaxCut_graph(n, nodes, seed)

### QUBO Matrix

`import strangeworks_qaoa.utils as utils`

nodes = 4

seed = 0

n = 3

problem = utils.get_nReg_MaxCut_QUBO(n, nodes, seed)

### Qiskit PauliSumOp

`import strangeworks_qaoa.utils as utils`

nodes = 4

seed = 0

n = 3

problem = utils.get_nReg_MaxCut_PauliSumOp(n, nodes, seed)

### Dwave/Dimod BQM

`from dimod import BinaryQuadraticModel`

import dimod

linear = {1: -2, 2: -2, 3: -3, 4: -3, 5: -2}

quadratic = {(1, 2): 2, (1, 3): 2, (2, 4): 2, (3, 4): 2, (3, 5): 2, (4, 5): 2}

bqm = BinaryQuadraticModel(linear, quadratic,dimod.Vartype.BINARY)

problem = {"BQM": bqm,

"variable_order": bqm.variables, # Can specify custom variable order. This will correspond to the solution bitstring.

}

## Algorithm Details

### Sub-systems

We initially split up the problem by randomly selecting nodes for each subsytem. If the entry `type_subsystem="weighted_random"`

then we weight the random choice with whether to add a node to a given sub-system by the sum of the squares of the bond between the new node and all the other nodes in that sub-system. If the entry `type_subsystem="kernighan_lin_bisection"`

then we use the method from networkx.

### Final Optimization

With the solutions $|GS_{sub}^i\rangle$, for each of the $N_s$ sub-systems, we perform a final optimization on a gate-based quantum computer with qubit number, $N_f = \log_2(N_s)$. We construct a vector of the weighted sub-system ground states

where the $C^i$ are some undetermined coefficients. It is assumed that, $|\rm{sign}(S)\rangle \approx |GS_{full} \rangle$. i.e. that taking the sign of the vector entries of $|S\rangle$ is approximately equal to the true ground state of the full problem. Note that $|S\rangle$ is not the typical quantum state vector for a system iof $N_f$ qubits, but instead a classical vector of the size of the QUBO problem.

In order to solve for the coefficients $C^i$, we map each of the $|GS_{sub}^i\rangle$ to one of the $2^{Nf}$ basis states of the final qubit problem and optimize the cost function,

where the $\vec{\theta}$ are variational parameters of the quantum ansatz circuit in the VQE/QAOA algorithm.

First, the $C^i(\vec{\theta})$ are determined by measuring the amplitudes of each basis state after the application of the ansatz circuit. Next, the $|\rm{sign}(S)\rangle$ is constructed which is a classical bitstring of positive and negetive ones. We can then calculate the cost above by putting the bit-string into the graph/hamiltonian/QUBO.

As this final computation of the cost is computationally trivial, the StrangeworksHybrid algorithm also adds in additional checks: if the magnitude of the value of one of the entries in $|S\rangle$ is less than some small threshhold, we check both values ($\pm 1$) and take the one with the lowest cost.

## Troubleshooting

This section provides troubleshooting tips for the product or service this page covers.

## Further Reading

This section provides links to other pages in the documentation that are relevant to the product or service this page covers to drive further exploration and engagement.

[1] - More info on the hybrid QAOA annealer algorithm: https://arxiv.org/abs/2208.03283

[2] - More info on the QAOA algorithm: https://qiskit.org/textbook/ch-applications/qaoa.html

[3] - A list of problems that can be solved with QAOA: https://blog.xa0.de/post/List-of-QUBO-formulations/