Skip to main content

Quantum Approximate Optimization Algorithm

🔍

strangeworks-qaoa​

The strangeworks-qaoa package allows users to run construct and solve problems with the QAOA algorithm on multiple hardware providers. 

pip install -U pip strangeworks-qaoa

📑 Package Documentation

PyPI version PyPI - Python Version

In order to submit quantum jobs through the Strangeworks Platform, you must have a Quantum Resources enabled in your workspace.

🔑

Authentication​

First, authenticate via the Strangeworks SDK with your api-key taken from the Portal homepage: ​

import strangeworks as sw
from strangeworks_qaoa.sdk import StrangeworksQAOA

sw.authenticate(api_key)
🖥️

Backends​

List compatible backends for the QAOA product:

sw_qaoa = StrangeworksQAOA()
sw_qaoa.backends()

You will need to have the particular Quantum Resources enabled in your workspace to run on those backends.

Loading quantum backends...
📚

Overview​

​ The Quantum Approximate Optimization Algorithm (QAOA) is designed to solve quadratic unconstrained binary optimization (QUBO) problems by leveraging quantum resources. As a hybrid classical-quantum algorithm, QAOA combines the strengths of both classical and quantum computing. The algorithm involves applying a quantum circuit with variational parameters to qubits, measuring the qubits, and repeating the process to gather statistics. These results are then used to compute a cost function, which is optimized by a classical CPU. This iterative process continues, alternating between quantum measurements and classical optimization, until the lowest cost solution is found.

The strangeworks-qaoa package implements StrangeworksQAOA, an enhanced version of QAOA that improves upon standard implementations by tracking and reporting the best individual bitstring solution found throughout the optimization process, rather than only using the average cost over all measurements. This enhancement can lead to better solution quality without additional computational or financial overhead. For more details on the benchmarking and performance improvements of StrangeworksQAOA, see our case study on solving the aircraft cargo loading problem using Amazon Braket.

QAOA addresses QUBO problems with binary variables xn={0,1}x_n = \{0, 1 \}, characterized by the general cost function:

C=∑n,m>nAn,mxnxm+∑nBnxn.C = \sum_{n,m>n} A_{n,m} x_n x_m + \sum_n B_{n} x_n.

In typical scenarios, to map the problem to a quantum format suitable for qubits, the binary variables xn={0,1}x_n = \{0, 1 \} are transformed into a new set of variables, zn={−1,1}z_n = \{-1, 1 \}, converting the cost function into a Quantum Ising Hamiltonian. However, in this service, this transformation step is omitted unless the 'ising' field in the problem parameter dictionary is set to True. This omission does not affect the validity or performance of the algorithm; it only changes the value of the cost function (the "energy") that is outputted. In both cases, the optimal solution remains the same.

When defining a QUBO problem for input into the service, the problem is directly minimized, and the value of the cost function is displayed. By default, when 'ising'=False, the QUBO is optimized rather than the Ising Hamiltonian.

References​

🚀

Quickstart​

Get started with Strangeworks QAOA by following these steps:

  1. Authenticate with your API key (see Authentication above)
  2. Create a problem in one of the supported formats (see Problem Formats below)
  3. Configure parameters including optional algorithm variants like cVAR or QRR (see Parameters section)
  4. Run a job on a compatible backend (see Job Management below)

AWS Braket​

Here is an example run for a small problem on an AWS Braket simulator:

import strangeworks as sw
from strangeworks_qaoa.sdk import StrangeworksQAOA
import strangeworks_qaoa.utils as utils

sw.authenticate(api_key)
sw_qaoa = StrangeworksQAOA()

################################
######## Create problem from QUBO
nodes = 4
seed = 0
n = 3
problem = utils.get_nReg_MaxCut_QUBO(n, nodes, seed)
################################

################################
######## Define algorithm parameters
problem_params = {
    # Required parameters
    "nqubits": nodes,           # Number of variables in the problem / number of qubits
    "maxiter": 50,              # Maximum number of iterations in algorithm
    "shotsin": 1000,            # Number of times quantum circuit is measured at each iteration
    
    # Optional: Circuit depth and initialization
    "p": 1,                     # Controls the depth of the Quantum Circuit ansatz. Default: 1
    "theta0": [1.0, 1.0],       # Starting point for variational parameters. If specified, must be equal to 2p
    
    # Optional: Algorithm variants (see Algorithm Variants section below)
    "alpha": 0.1,               # cVAR parameter: float between 0 and 1. Default: 1.0 (standard QAOA)
    "qrr": False,               # Enable Quantum Relax and Round QAOA. Default: False (standard QAOA)
    
    # Optional: Optimizer selection
    "optimizer": "COBYLA",      # Classical optimizer to use. Default: 'COBYLA'
                                # Available: 'COBYLA', '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'
    
    # Optional: Problem format
    "ising": False,             # Problem format: True for Ising ({-1, +1}), False for QUBO ({0, 1}). Default: False
    }

backend = "SV1" # Change this to another ibm backend name or an aws device name
sw_job = sw_qaoa.run(backend, problem, problem_params)

result = sw_qaoa.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.

Qiskit Runtime​

Here is an example run for a small problem on an Qiskit Runtime simulator:

import strangeworks as sw
from strangeworks_qaoa.sdk import StrangeworksQAOA
import strangeworks_qaoa.utils as utils

sw.authenticate(api_key)
sw_qaoa = StrangeworksQAOA()

################################
######## Create problem from QUBO
nodes = 4
seed = 0
n = 3
problem = utils.get_nReg_MaxCut_QUBO(n, nodes, seed)
################################

################################
######## Define algorithm parameters
problem_params = {
    # Required parameters
    "nqubits": nodes,           # Number of variables in the problem / number of qubits
    "maxiter": 50,              # Maximum number of iterations in algorithm
    "shotsin": 1000,            # Number of times quantum circuit is measured at each iteration
    
    # Optional: Circuit depth and initialization
    "p": 1,                     # Controls the depth of the Quantum Circuit ansatz. Default: 1
    "theta0": [1.0, 1.0],       # Starting point for variational parameters. If specified, must be equal to 2p
    
    # Optional: Algorithm variants (see Algorithm Variants section below)
    "alpha": 0.1,               # cVAR parameter: float between 0 and 1. Default: 1.0 (standard QAOA)
    "qrr": False,               # Enable Quantum Relax and Round QAOA. Default: False (standard QAOA)
    
    # Optional: Optimizer selection
    "optimizer": "COBYLA",      # Classical optimizer to use. Default: 'COBYLA'
                                # Available: 'COBYLA', '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'
    
    # Optional: Problem format
    "ising": False,             # Problem format: True for Ising ({-1, +1}), False for QUBO ({0, 1}). Default: False
    }

backend = "ibmq_qasm_simulator" # Change this to another ibm backend name or an aws device name
sw_job = sw_qaoa.run(backend, problem, problem_params)

result = sw_qaoa.get_results(sw_job,calculate_exact_sol=True, display_results=True)
⚡

Algorithm Variants​

Strangeworks QAOA supports several advanced variants that can improve convergence and solution quality. These variants can be enabled through parameters in the problem_params dictionary.

Conditional Value at Risk (cVAR) QAOA​

The Conditional Value at Risk (cVAR) variant of QAOA modifies the cost function calculation to focus on the best-performing solutions (those with the lowest energy). While classical cVAR methods typically focus on the "tail" or worst parts of a probability distribution, quantum probability distributions from QAOA are typically almost completely flat, meaning the entire distribution effectively acts as a tail.

How it works: The alpha parameter (ranging from 0 to 1) controls what fraction of solutions to consider. When alpha=1.0 (default), the algorithm behaves like standard QAOA, optimizing the full expected value over all measurements. As alpha decreases toward 0, the algorithm uses only the alpha% of solutions with the lowest energy when calculating the cost function, effectively focusing on the best-performing solutions.

When to use: cVAR-QAOA is particularly useful when:

  • You want to improve solution quality by focusing on the best solutions rather than the average
  • Standard QAOA is not converging to satisfactory solutions
  • You're working with problems where the best individual solutions are more important than the average performance

Parameter: Set alpha in problem_params to a value between 0 and 1. Default is 1.0 (standard QAOA).

Reference: Conditional Value-at-Risk: Quantifying Quantum Advantage

Quantum Relax and Round (QRR) QAOA​

Quantum Relax and Round (QRR) QAOA is a variant that combines classical relaxation techniques with quantum optimization. The algorithm first relaxes the binary constraints of the problem, solves the relaxed version, and then uses quantum optimization to round the solution back to valid binary values. This approach can significantly improve solution quality and convergence.

How it works: QRR-QAOA relaxes the binary constraints of the QUBO problem, allowing variables to take continuous values. The relaxed problem is solved, and then the quantum circuit is used to round these continuous solutions back to binary values while optimizing the original objective function. This two-stage approach leverages both classical relaxation methods and quantum optimization.

When to use: QRR-QAOA is beneficial when:

  • You're working with problems where relaxation provides good initial solutions
  • You want to combine classical relaxation techniques with quantum optimization
  • Standard QAOA is struggling with constraint satisfaction
  • You need improved solution quality for constrained optimization problems

Parameter: Set qrr=True in problem_params to enable. Default is False (standard QAOA).

Reference: Extending relax-and-round combinatorial optimization solvers with quantum correlations (arXiv:2307.05821)

🧪

Problem Formats​

Strangeworks QAOA accepts problems in several formats. Choose the format that best matches your data structure and workflow. All formats are converted internally to a QUBO representation for optimization.

NetworkX Graphs​

For graph-based problems (like MaxCut), you can use NetworkX graph objects. The service will automatically convert the graph to a QUBO problem.

import strangeworks_qaoa.utils as utils

nodes = 4
seed = 0
n = 3
problem = utils.get_nReg_MaxCut_graph(n, nodes, seed)

QUBO Format​

For problems already formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems, you can provide the QUBO directly. This format is ideal when you have explicit linear and quadratic coefficients.

import strangeworks_qaoa.utils as utils

nodes = 4
seed = 0
n = 3
problem = utils.get_nReg_MaxCut_QUBO(n, nodes, seed)

Binary Quadratic Model (BQM)​

For problems using the D-Wave Ocean SDK's BinaryQuadraticModel format, you can pass a BQM object directly. This is useful if you're already working with D-Wave's tooling or have a BQM from another source. 

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.
           }
📠

Job Management​

Once you've defined your problem and configured parameters, you can submit and manage QAOA jobs through the Strangeworks platform. Jobs run asynchronously, allowing you to submit multiple jobs and check their status independently.

Submitting a Job​

Submit a QAOA job by calling run() with your chosen backend, problem, and parameters. This returns a job object that you can use to track progress and retrieve results.

sw_qaoa = StrangeworksQAOA()
sw_job = sw_qaoa.run(backend, problem, problem_params)

The job will be queued and executed on the specified backend. You can monitor its progress using the job object.

Checking Job Status​

Check the current status of a job to see if it's queued, running, completed, or failed. The status is updated automatically when you call update_status().

sw_qaoa = StrangeworksQAOA()
status = sw_qaoa.update_status(sw_job)

Retrieving Results​

Once a job completes, retrieve the results using get_results(). This method returns the optimized solution, cost function value, and other relevant information. You can optionally calculate the exact solution for comparison and display formatted results.

sw_qaoa = StrangeworksQAOA()
result = sw_qaoa.get_results(sw_job, calculate_exact_sol=True, display_results=True)

Managing Multiple Jobs​

You can retrieve and manage jobs in several ways:

Retrieve a specific job by slug:

sw_job = sw.jobs(slug=slug)[0]

List all your QAOA jobs:

jobs = sw_qaoa.job_list(update_status=True)

​

⚙️

Parameters​

The problem_params dictionary accepts the following parameters:

Required Parameters​

  • nqubits (int): Number of variables in the problem / number of qubits
  • maxiter (int): Maximum number of iterations in the optimization algorithm
  • shotsin (int): Number of times the quantum circuit is measured at each iteration

Optional Parameters​

Circuit Configuration​

  • p (int): Controls the depth of the Quantum Circuit ansatz. Default: 1
  • theta0 (list): Starting point for variational parameters. If specified, must be a list of length 2p. Default: automatically initialized

Algorithm Variants​

  • alpha (float): cVAR parameter controlling the quantile level. Range: 0 to 1. Default: 1.0 (standard QAOA). See cVAR QAOA section for details.
  • qrr (bool): Enable Quantum Relax and Round QAOA algorithm. Default: False (standard QAOA). See Quantum Relax and Round (QRR) QAOA section for details.

Optimizer Selection​

  • optimizer (str): Classical optimizer to use. Default: 'COBYLA'
    • Available optimizers: 'COBYLA', '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'

Problem Format​

  • ising (bool): Problem format specification. True for Ising format (variables: {-1, +1}), False for QUBO format (variables: {0, 1}). Default: False