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.

📑 Package Documentation

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 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:

import strangeworks as sw
sw.authenticate(api_key)

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

sw_hybrid = StrangeworksHybrid())

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 as sw
from strangeworks_hybrid_optimize import StrangeworksHybrid, QAOAParams, HybridParams
import strangeworks_hybrid_optimize.utils as utils

sw.authenticate(api_key)

################################
######## 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 as sw
from strangeworks_hybrid_optimize import StrangeworksHybrid, HybridParams
import strangeworks_hybrid_optimize.utils as utils

sw.authenticate(api_key)
sw_qaoa = StrangeworksHybrid()

################################
######## 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

|S\rangle = \sum_i^{N_s} C^i |GS_{sub}^i\rangle,

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,

Cost(\vec{C}(\vec{\theta})) = \langle\rm{sign}(S)| H|\rm{sign}(S)\rangle,

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.

Hybrid Optimize

Overview​

Prerequisites​

Installation​

Authentication​

Usage​

Examples​

Gate-Based sub problems: AWS Braket​

StrangeworksOptimization sub problems: AWS Braket + Dwave​

Accepted Problem Input Types​

Network X Graph​

QUBO Matrix​

Qiskit PauliSumOp​

Dwave/Dimod BQM​

Algorithm Details​

Sub-systems​

Final Optimization​

Troubleshooting​

Further Reading​