Partitioned QAOA

Docs

Divi

Partitioned QAOA

This example demonstrates how to use Divi’s GraphPartitioningQAOA class to solve a MaxCut problem on large graphs using a divide-and-conquer strategy. 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.

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

Code Example

from divi.qprog import GraphPartitioningQAOA
from divi.qprog.optimizers import Optimizers
from divi.services import QoroService

q_service = QoroService(QORO_API_KEY)

graph = # A NetworkX graph

qaoa_batch = GraphPartitioningQAOA(
    problem="maxcut",
    graph=graph,
    n_layers=2,
    n_clusters=15,
    optimizer=Optimizers.MONTE_CARLO,
    max_iterations=5,
    qoro_service=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}")
print(f"Sim runtime: {qaoa_batch.total_run_time}")

analyze_results(quantum_solution, classical_cut_size)

What’s Happening?

Step	Description
`GraphPartitioningQAOA(...)`	Initializes a batch of QAOA programs, each solving a cluster of the original graph.
`n_clusters=15`	The graph is partitioned into 15 subgraphs using a clustering algorithm.
`optimizer=MONTE_CARLO`	A lightweight Monte Carlo optimizer is used to minimize circuit evaluation cost.
`create_programs()`	Generates QAOA circuits for each cluster.
`run()`	Executes all generated circuits — possibly in parallel across multiple quantum backends.
`compute_final_solutions()`	Optimized bitstrings are retrieved for each cluster.
`aggregate_results()`	The final MaxCut solution is formed by combining cluster-wise results.

Why Partition?

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

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.

Built-in Solvers

Divi includes built-in support for several common graph-based optimization problems. You can specify these using the problem parameter when initializing a QAOA-based program.

Problem	Description
`max_clique`	Finds the largest complete subgraph where every node is connected to every other.
`max_independent_set`	Finds the largest set of vertices with no edges between them.
`max_weight_cycle`	Identifies a cycle with the maximum total edge weight in a weighted graph.
`maxcut`	Divides a graph into two subsets to maximize the sum of edge weights between them.
`min_vertex_cover`	Finds the smallest set of vertices such that every edge is incident to at least one selected vertex.

Using QUBO Formulations

Divi’s QAOA solver can, instead of using a graph input, also take a (Quadratic Unconstrained Binary Optimization) QUBO formulated problem. There are only a few differences in the code to do so. Divi currently supports two methods of formulating the QUBO problem. The first is using the qiskit_optimization library to create QuadraticPrograms. The second is with a Numpy array that can be build with the dimod library.

1. Qiskit’s Quadratic Program

from divi.qprog import QAOA
from divi.qprog.optimizers import Optimizers
from divi.services import QoroService

# Using Qiskit's QUBO formulation package
from qiskit_algorithms import NumPyMinimumEigensolver
from qiskit_optimization import QuadraticProgram
from qiskit_optimization.algorithms import MinimumEigenOptimizer

q_service = QoroService(QORO_API_KEY)

qp = QuadraticProgram()
qp.binary_var("w")
qp.binary_var("x")
qp.binary_var("y")
qp.integer_var(lowerbound=0, upperbound=7, name="z")
qp.minimize(linear={"x": -3, "y": 2, "z": -1, "w": 10})

qaoa_problem = QAOA(
  qp,
  n_layers=2,
  optimizer=Optimizers.NELDER_MEAD,
  max_iterations=10,
  shots=10000,
  qoro_service=q_service,
)

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

2. Dimod’s Binary Quadratic Model

from divi.qprog import QAOA
from divi.qprog.optimizers import Optimizers
from divi.services import QoroService

# For generating the problem 
import dimod

q_service = QoroService(QORO_API_KEY)

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=Optimizers.L_BFGS_B,
    max_iterations=5,
    shots=10000,
    qoro_service=q_service,
)

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

Parallelized VQE Circuit Cutting