Hybrid QAOA

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 inspired 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 separately 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 give some technical details of the algorithm.

Prerequisites

To use Strangeworks Hybrid Optimize, you must meet the following prerequisites:

You must have the QAOA service set up on your account.
You must have access to the Strangeworks Hybrid service. (Reach out to your account manager to discuss activating this if needed.)
To use the AWS Hybrid job service and/or IBM Cloud devices, you must have relevant provider access and a billing account properly enabled.
To use the Optimization service, you must have it enabled on your account as well as access to at least one compatible optimization provider (such as D-Wave or Toshiba).

Please ensure all necessary services and provider access are configured before getting started.

Installation

To get started, make sure you have PyPI - Python Version and are familiar with setting up and using virtual environments.

Install packages using pip:

pip install -U pip strangeworks-hybrid-optimize

Import package into Python:

from strangeworks_hybrid_optimize import StrangeworksHybrid

Authentication

For 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 the Examples section below for an example script.

Authenticate with Strangeworks Python SDK using the user's API token:

import strangeworks as sw
sw.authenticate(api_key)

Get a Hybrid Optimize resource using QAOA SDK extension and user's 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 Subproblems: 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'
                            # Additional 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 specified: 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? Contact us at support@strangeworks.com for assistance.

StrangeworksOptimization Subproblems: AWS Braket + D-Wave

Here is an example run for a small problem, where the sub-problems are run on D-Wave 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: D-Wave 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 specified: 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? Contact us at support@strangeworks.com for assistance.

Accepted Problem Input Types

NetworkX 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)

D-Wave/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 subsystem. 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 bonds 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 of $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 negative 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 threshold, 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 QAOA

Overview​

Prerequisites​

Installation​

Authentication​

Usage​

Examples​

Gate-Based Subproblems: AWS Braket​

StrangeworksOptimization Subproblems: AWS Braket + D-Wave​

Accepted Problem Input Types​

NetworkX Graph​

QUBO Matrix​

Qiskit PauliSumOp​

D-Wave/Dimod BQM​

Algorithm Details​

Sub-systems​

Final Optimization​

Troubleshooting​

Further Reading​