QAOA

Similar to VQE, QAOA in Divi operates in multiple modes: a single-instance mode and a 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 mode is more specialized, focusing on solving larger, less tractable problems through a divide-and-conquer approach.

Single-instance QAOA

A QAOA constructor expects a problem. 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 can optionally override the initial state by passing an InitialState instance (e.g., ZerosState(), SuperpositionState()). By default, each problem class provides its own recommended initial state. In addition, a user can determine how many layers of the QAOA ansatz to apply.

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 via concrete problem classes in divi.qprog.problems:

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

Divi also provides a visualization function for computed solutions:

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.

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.

Partitioning QAOA

GraphPartitioningQAOA solves optimization problems like MaxCut 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 GraphPartitioningConfig class (passed to the problem constructor), 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.

Execution Flow

The partitions can also be visualized through the function draw_partitions:

QUBO Partitioning Example

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.

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.

📖 For code examples and detailed API usage, visit the Divi Documentation.