QAOA

Similar to VQE, QAOA in Divi operates in multiple modes: a single-instance mode, a graph partitioning mode, and a QUBO partitioning mode. The single-instance mode can be used to find a solution to a single graph-based or QUBO-based optimization problem. The partitioning modes are more specialized, focusing on solving larger, less tractable problems through a divide-and-conquer approach.

Single-instance QAOA

A QAOA constructor expects a problem. As we will show in the examples, the form of input triggers a different execution pathway under the hood. However, there are some common arguments that one must pay attention to.

A user has the ability to choose the initial state of the quantum system before the optimization. By default (when the argument initial_state = "Recommended" is passed), a problem-specific initial state would be chosen. Other accepted values are "Zero", "Ones", and "Superposition". In addition, a user can determine how many layers of the QAOA ansatz to apply.

Finally, the solution of the QAOA problem can be accessed through the solution variable, which, based on the problem at hand, would have different formats. For a graph problem, it will contain a set of node IDs that correspond to one of the partitions of the solution. For QUBO optimization, it will return the solution bitstring as a list of 1’s and 0’s.

Graph Problems

Divi includes built-in support for several common graph-based optimization problems whose cost Hamiltonians are available through PennyLane’s qaoa module. You can specify these using the graph_problem parameter when initializing a QAOA-based program. They are available through a GraphProblem enum.

For all problems with the exception of Max-Cut, the constrained version of the Hamiltonian is available by passing the keyword argument is_constrained=True to the constructor. Refer to the PennyLane documentation for more details.

The following is an example for finding the max-clique of the bull graph:

import networkx as nx

from divi import ParallelSimulator
from divi.qprog import QAOA, GraphProblem
from divi.qprog.optimizers import ScipyOptimizer, ScipyMethod

G = nx.bull_graph()

qaoa_problem = QAOA(
    problem=G,
    graph_problem=GraphProblem.MAX_CLIQUE,
    n_layers=2,
    optimizer=ScipyOptimizer(ScipyMethod.NELDER_MEAD),
    max_iterations=10,
    is_constrained=True,
    backend=ParallelSimulator(),
)

qaoa_problem.run()
qaoa_problem.compute_final_solution()

losses = qaoa_problem.losses[-1]
print(f"Minimum Energy Achieved: {min(losses.values()):.4f}")

print(f"Total circuits: {qaoa_problem.total_circuit_count}")

print(f"Classical solution:{nx.algorithms.approximation.max_clique(G)}")
print(f"Quantum Solution: {set(qaoa_problem.solution)}")

qaoa_problem.draw_solution()

As you can see, Divi provides a visualization function after computing the solution. Running the code above will generate the following plot:

The solution can also be accessed through the solution property, which would generate the following list of node IDs corresponding to the Max-Clique:

>>> qaoa_problem.solution
[0, 1, 2]

QUBO-based Problems

Divi’s QAOA solver can also take a QUBO (Quadratic Unconstrained Binary Optimization) formulated problem instead of a graph. Divi supports the following QUBO input formats:

• NumPy array: A dense N×N matrix
• SciPy sparse matrix: For large, sparse QUBOs
• D-Wave’s BinaryQuadraticModel: From the dimod library

In contrast to graph-based QAOA instances, the solution format for QUBO-based QAOA instances is a binary numpy array representing the value for each variable in the original QUBO.

NumPy Array-based Input

For illustration purposes, we use D-Wave’s dimod to generate a random QUBO.

from divi.qprog import QAOA
from divi.qprog.optimizers import ScipyOptimizer, ScipyMethod
from divi import QoroService, JobConfig

# For generating the problem
import dimod

q_service = QoroService(QORO_API_KEY, config=JobConfig(shots=10000))

bqm = dimod.generators.randint(5, vartype="BINARY", low=-10, high=10, seed=1997)
qubo_array = bqm.to_numpy_matrix()

qaoa_problem = QAOA(
    problem=qubo_array,
    n_layers=2,
    optimizer=ScipyOptimizer(ScipyMethod.L_BFGS_B),
    max_iterations=5,
    backend=q_service,
)

qaoa_problem.run()
qaoa_problem.compute_final_solution()
sol = qaoa_problem.solution

BinaryQuadraticModel Input

You can also pass a BinaryQuadraticModel directly:

import dimod
from divi.qprog import QAOA
from divi.qprog.optimizers import ScipyOptimizer, ScipyMethod
from divi import ParallelSimulator

bqm = dimod.generators.randint(8, vartype="BINARY", low=-5, high=5, seed=42)

qaoa_problem = QAOA(
    problem=bqm,
    n_layers=2,
    optimizer=ScipyOptimizer(ScipyMethod.COBYLA),
    max_iterations=10,
    backend=ParallelSimulator(),
)

qaoa_problem.run()
qaoa_problem.compute_final_solution()
sol = qaoa_problem.solution

QDrift Integration

QAOA supports QDrift as a trotterization strategy, which can reduce circuit depth for problems with many Hamiltonian terms. Pass a TrotterizationStrategy to enable it:

from divi.qprog import QAOA, GraphProblem
from divi.qprog._hamiltonians import QDrift

qaoa_problem = QAOA(
    problem=G,
    graph_problem=GraphProblem.MAXCUT,
    n_layers=2,
    trotterization_strategy=QDrift(n_samples=50),
    optimizer=ScipyOptimizer(ScipyMethod.COBYLA),
    max_iterations=10,
    backend=ParallelSimulator(),
)

Graph-Partitioning QAOA

This example demonstrates how to use Divi’s GraphPartitioningQAOA class to solve a MaxCut problem on large graphs. Instead of executing a single large QAOA circuit, the graph is partitioned into smaller subgraphs (clusters), and individual QAOA instances are executed in parallel across these subgraphs, before aggregating the results, in a divide-and-conquer manner.

This enables scalable quantum optimization, even for graphs that exceed the size limits of a single quantum backend.

Configuring the Partitioning

The partitioning strategy is configured using the PartitioningConfig class, which offers the following options:

• max_n_nodes_per_cluster: This specifies the maximum number of nodes allowed in each subgraph or cluster. This is crucial for ensuring that each subproblem fits within the constraints of a single quantum backend.

• minimum_n_clusters: This parameter sets the minimum number of clusters to be created.

• partitioning_algorithm: A parameter that determines the algorithm used to partition the graph. The available options are:

  • spectral: This refers to spectral clustering ¹, an algorithm that uses the eigenvectors of the graph’s Laplacian matrix to partition the vertices. It’s known for producing high-quality partitions by minimizing the number of edges cut between the subgraphs. However, it might lead to unevenly sized partitions, based on the input graph.
  • metis: Employs the popular METIS program ² through py-metis. This algorithm generally generates more evenly sized partitions compared to spectral clustering.
  • kernighan_lin Iteratively applies the classical Kernighan-Lin ³ bipartitioning algorithm until the desired number of clusters is achieved.

At least one of max_n_nodes_per_cluster and minimum_n_clusters must be provided to the class. In case both are provided, the partitioning logic would first attempt creating the minimum number of desired partitions first, before breaking down any oversized partitions further to meet the constraint on the number of nodes.

Code Example

from divi.qprog import GraphPartitioningQAOA, GraphProblem, PartitioningConfig
from divi.qprog.optimizers import MonteCarloOptimizer
from divi import QoroService

q_service = QoroService(QORO_API_KEY)

def analyze_results(quantum_solution, classical_cut_size):
    cut_edges = 0

    for u, v in graph.edges():
        if (u in quantum_solution) != (v in quantum_solution):
            cut_edges += 1

    print(
        f"Quantum Cut Size to Classical Cut Size Ratio = {cut_edges / classical_cut_size}"
    )

graph = # A NetworkX graph

config = PartitioningConfig(max_n_nodes_per_cluster=4, partitioning_algorithm="metis")

qaoa_batch = GraphPartitioningQAOA(
    graph_problem=GraphProblem.MAXCUT,
    graph=graph,
    n_layers=2,
    partitioning_config=config,
    optimizer=MonteCarloOptimizer(),
    max_iterations=5,
    backend=q_service,
)

qaoa_batch.create_programs()
qaoa_batch.run()
qaoa_batch.compute_final_solutions()
quantum_solution = qaoa_batch.aggregate_results()

print(f"Total circuits: {qaoa_batch.total_circuit_count}")

analyze_results(quantum_solution, classical_cut_size)

What’s Happening?

The partitions can also be visualized through the function draw_partitions:

QUBO-Partitioning QAOA

For QUBO problems that are too large to solve directly, QUBOPartitioningQAOA applies a similar partitioning strategy, but operates on the QUBO matrix structure rather than graph topology:

from divi.qprog import QUBOPartitioningQAOA, PartitioningConfig
from divi.qprog.optimizers import ScipyOptimizer, ScipyMethod
from divi import ParallelSimulator

config = PartitioningConfig(max_n_nodes_per_cluster=8)

qubo_batch = QUBOPartitioningQAOA(
    qubo_matrix=qubo_array,
    n_layers=2,
    partitioning_config=config,
    optimizer=ScipyOptimizer(ScipyMethod.COBYLA),
    max_iterations=10,
    backend=ParallelSimulator(),
)

qubo_batch.create_programs()
qubo_batch.run()
qubo_batch.compute_final_solutions()
solution = qubo_batch.aggregate_results()

Why Partition?

Quantum hardware is limited in the number of qubits and circuit depth. For large problems:

• Full QAOA is intractable.
• Partitioned QAOA trades global optimality for scalability and parallel execution.
• It enables fast, approximate solutions using many small quantum jobs rather than one large one.