To explore and execute the Graph Decomposition and Scatter-Gather flow on the live canvas, start Quanifi in Docker: 

docker compose up -d

Wait ~30–60 seconds for NiFi to report healthy (docker compose ps). Then open https://localhost:8443/nifi in your browser (Username: admin, Password: quanifipassword). For processor selection and environment options, see the Docker Quickstart Guide.

Module 6: Divide-and-Conquer QAOA & Disconnected Graph Decomposition

Learn how to scale quantum combinatorial optimization to large graphs by leveraging graph structure. Based on the Classiq Maximum Independent Set (MIS) example, discover why disconnected subgraphs decouple mathematically, and see how Quanifi maps this decomposition naturally into a resilient, parallel Scatter-Gather Apache NiFi dataflow.

1. The Problem: Scaling Quantum Graph Algorithms

In graph theory and network optimization, problems such as Maximum Independent Set (MIS), Max-Cut, and Minimum Vertex Cover are fundamental NP-hard challenges. They drive applications in:

  • Telecommunications & 5G: Allocating non-interfering wireless frequencies to cellular towers.
  • Cybersecurity: Finding minimum sets of critical servers to patch to disconnect attack kill-chains.
  • Bioinformatics & Drug Discovery: Identifying non-interacting molecular structures or diverse chemical libraries.

However, today's NISQ quantum devices have severe physical constraints: limited qubit counts (typically dozens to a few hundred), sparse qubit connectivity (heavy-hex or square grids), and short coherence times. Attempting to solve a 50-node or 100-node graph with a single monolithic quantum circuit fails due to noise and exponential gate compilation overhead.

💡 Software Engineering Analogy: Monolith vs. Microservices (Divide & Conquer)

In classical software architecture, you never process a distributed dataset with a single giant in-memory lock. You partition the data into independent shards and process them with worker pools.

Similarly, real-world graphs (like communication backbones or vulnerability dependency graphs) are rarely fully connected cliques; they naturally partition into disconnected components (isolated sub-graphs). By decomposing the graph into these components, we can run independent, low-depth quantum sub-circuits in parallel, achieving exponential state-space reduction!

2. Mathematical Formulation: Maximum Independent Set (MIS)

Given an undirected graph \(G = (V, E)\) with vertex set \(V\) and edge set \(E\), an independent set \(I \subseteq V\) is a subset of vertices such that no two vertices in \(I\) are adjacent (i.e., there is no edge connecting them):

$$(u, v) \in E \implies u \notin I \lor v \notin I$$

The Maximum Independent Set Problem asks for an independent set with the largest possible cardinality \(|I|\).

Binary Integer Formulation (As in Classiq's Pyomo Model)

We assign a binary decision variable \(x_v \in \{0, 1\}\) to each vertex \(v \in V\), where \(x_v = 1\) if vertex \(v\) is included in the set, and \(x_v = 0\) otherwise:

$$\max_{x \in \{0,1\}^{|V|}} \sum_{v \in V} x_v$$ $$\text{subject to} \quad x_u + x_v \le 1, \quad \forall (u, v) \in E$$

The constraint ensures that if node \(u\) is selected (\(x_u = 1\)), node \(v\) cannot be selected (\(x_v\) must be \(0\)).

The Cost Hamiltonian & Penalty Term

To solve this on a quantum processor with QAOA, the constrained optimization is transformed into an unconstrained minimization problem using a penalty multiplier \(P > 1\):

$$C(x) = -\sum_{v \in V} x_v + P \sum_{(u, v) \in E} x_u x_v$$

Using the standard Pauli substitution \(x_v = \frac{I - Z_v}{2}\), the cost function becomes a diagonal Cost Hamiltonian:

$$H_C = \sum_{v \in V} h_v Z_v + \sum_{(u, v) \in E} J_{uv} Z_u Z_v + \text{const}$$

Notice the crucial structure: two-qubit interaction terms (\(Z_u Z_v\)) exist if and only if there is an edge \((u, v) \in E\).

3. The Decomposition Secret: Why Disconnected Components Decouple

Suppose our graph \(G\) consists of \(k\) disconnected components:

$$G = C_1 \sqcup C_2 \sqcup \dots \sqcup C_k$$

where vertices are partitioned into disjoint sets \(V(G) = V(C_1) \cup \dots \cup V(C_k)\), and there are zero edges bridging different components:

$$E(C_i, C_j) = \emptyset \quad \forall i \ne j$$
Component C1 (|V1| = 3) Sub-Hamiltonian: HC(C1) 0 1 2 Component C2 (|V2| = 5) Sub-Hamiltonian: HC(C2) 3 4 5 6 7
Figure 6.1: Disconnected 8-node graph decomposed into two independent components (\(C_1\) with 3 nodes, \(C_2\) with 5 nodes). Red vertices indicate the Maximum Independent Set solution.

Mathematical Properties of the Decomposition:

  1. Additivity of the Cost Hamiltonian: Because there are no cross-terms \(Z_u Z_v\) between nodes in different components, the total Hamiltonian is the exact sum of component Hamiltonians: $$H_C(G) = H_C(C_1) \otimes I_{C_2} + I_{C_1} \otimes H_C(C_2)$$
  2. Tensor Product Factorization of the Quantum Unitary: Because \(H_C(C_1)\) and \(H_C(C_2)\) commute: $$e^{-i \gamma H_C(G)} = e^{-i \gamma H_C(C_1)} \otimes e^{-i \gamma H_C(C_2)}$$ The QAOA cost and mixer unitaries factorize identically! The quantum algorithm does not need to simulate both components simultaneously.
  3. Solution Reassembly: The global maximum independent set is simply the union of the independent sets of each component: $$I^*(G) = I^*(C_1) \cup I^*(C_2) \cup \dots \cup I^*(C_k)$$ $$\alpha(G) = \alpha(C_1) + \alpha(C_2) + \dots + \alpha(C_k)$$
🚀 The Exponential State-Space Advantage

For an 8-node graph:
• Monolithic approach: Requires 1 circuit with 8 qubits. State vector size = \(2^8 = 256\) amplitudes.
• Decomposed approach: Requires 1 circuit with 3 qubits (\(2^3 = 8\)) and 1 circuit with 5 qubits (\(2^5 = 32\)). Total evaluated state space = \(8 + 32 = 40\) amplitudes!

For a 30-node network with three 10-node components:
• Monolithic: \(2^{30} \approx 1.07 \times 10^9\) states (requires supercomputers or huge hardware).
• Decomposed: \(3 \times 2^{10} = 3,072\) states (runs in milliseconds on a laptop or small cloud QPU)!

4. Mapping to Quanifi: The Scatter-Gather NiFi Flow

In a Python notebook (like Classiq's), decomposing a graph requires manual coding: iterating over nx.connected_components(graph), instantiating separate Pyomo models, calling the synthesis engine in a loop, and stitching the dictionaries together.

In Quanifi, this is the classic Scatter-Gather Enterprise Integration Pattern. Apache NiFi was designed specifically to split large messages, process fragments concurrently across distributed worker pools, and merge them with correlation tracking.

Ingest Graph GenerateFlowFile (Raw 8-node Graph) Component Splitter GraphSplitter (BFS) Forks k FlowFiles QAOA Worker 1 Solves C1 (3 Qubits) Local Simulator QAOA Worker 2 Solves C2 (5 Qubits) IBM Heron QPU Join Solutions MergeContent Defragment Strategy
Figure 6.2: The Scatter-Gather Quantum Flow architectural model on the Apache NiFi canvas.
Maximum Independent Set QAOA Canvas Flow
Figure 6.3: Maximum Independent Set (MIS) vertex independence optimization flow on the NiFi canvas. 🔍 Click image to enlarge in lightbox
Maximum Clique QAOA Canvas Flow
Figure 6.4: Maximum Clique graph optimization flow with cost Hamiltonian encoding and RX mixer. 🔍 Click image to enlarge in lightbox

The 5 Pipeline Stages & FlowFile Attribute Contracts:

  1. 1
    Ingestion (GenerateFlowFile / ListenHTTP)

    Ingests the graph topology JSON. Attributes include graph.name = "enterprise-network-8" and the edge list.

  2. 2
    Graph Component Splitter (GraphSplitter)

    Runs classical Connected Components analysis (\(O(|V| + |E|)\)). It forks the incoming FlowFile into \(k\) child FlowFiles, injecting standard NiFi correlation attributes:
    • fragment.identifier: A unique UUID correlating this run (e.g. graph-run-12345).
    • fragment.index: The component index (0 for \(C_1\), 1 for \(C_2\)).
    • fragment.count: The total component count (2).
    • subgraph.nodes: [0, 1, 2] for \(C_1\); [3, 4, 5, 6, 7] for \(C_2\).

  3. 3
    Parallel Quantum Execution Lanes (ClassiqMIS / QrispQAOA → any simulator → QuantumQAOAEvaluator)

    Each sub-graph FlowFile enters a QAOA processor instance. Since 0.2.0, QrispQAOA only trains and emits the bound circuit as qasm2 — it does not sample — so each lane continues on to any counts simulator and then QuantumQAOAEvaluator, which scores the sampled independent set against the exact reference before the merge step below. Because each sub-graph is small, the circuit depth is shallow, reducing decoherence. Furthermore, NiFi allows dynamic routing: small sub-graphs can route to a fast local simulator, while larger sub-graphs route to a hardware execution queue!

  4. 4
    Solution Join & Aggregator (MergeContent)

    Using NiFi's native Defragment strategy, MergeContent holds incoming FlowFiles until all \(k\) fragments sharing the same fragment.identifier arrive. It then merges the independent sets: $$I^*(G) = I^*(C_1) \cup I^*(C_2)$$

  5. 5
    Reporter (QuanifiReport)

    Renders an interactive report card displaying the merged independent set nodes, total cardinality, and per-component energy metrics.

5. Classiq Qmod vs. Quanifi Dataflow: Architectural Comparison

Architectural Feature Monolithic Script / Notebook Quanifi Flow-Based Pipeline
Circuit Complexity 1 giant circuit (\(2^{|V|}\) Hilbert space). High gate depth, heavy two-qubit crosstalk. \(k\) small decoupled circuits (\(\sum 2^{|V_i|}\)). Drastically lower noise and gate error.
Concurrency & Latency Sequential execution in a Python loop. Native asynchronous parallelism across multiple QPU threads/workers.
Fault Tolerance & Retries If an execution fails or times out, the entire notebook must restart. FlowFile-level retries: only the failed component sub-graph retries via NiFi backpressure.
Heterogeneous QPU Routing Hard to route sub-problems to different hardware vendors in a single script. Visual conditional routing: send 3-qubit graphs to local simulator and 20-qubit graphs to IBM QPU.

6. How to Read and Interpret the Results

When the pipeline executes for the 8-node graph shown in Figure 6.1, inspect the output FlowFile attributes:

FlowFile Attribute Observed Value Explanation
mis.component_0.nodes [1] In \(C_1\) (a triangle \(K_3\)), any 1 node forms an independent set (e.g. node 1).
mis.component_1.nodes [3, 5, 7] In \(C_2\) (5-cycle with cross edge), nodes 3, 5, 7 form an independent set.
mis.global.nodes [1, 3, 5, 7] The unified global Maximum Independent Set. No two selected nodes share an edge!
mis.cardinality 4 The total independent set size: \(\alpha(G) = \alpha(C_1) + \alpha(C_2) = 1 + 3 = 4\).
fragment.count 2 Confirms 2 components were split and successfully merged.
Hands-on Exercise 6.1

Evaluating Graph Decomposition on a Bipartite + Star Graph

Consider an enterprise infrastructure graph \(G\) consisting of two disconnected server clusters:
• Cluster A (\(C_1\)): A complete bipartite graph \(K_{3,3}\) with 6 servers: partition \(A = \{0, 1, 2\}\) and partition \(B = \{3, 4, 5\}\). Every server in \(A\) connects to every server in \(B\).
• Cluster B (\(C_2\)): A star graph \(S_5\) with 5 servers: 1 central server (node 6) connected to 4 satellite servers (nodes 7, 8, 9, 10).

Your Task:

  1. Calculate the Maximum Independent Set size \(\alpha(C_1)\) for Cluster A, and \(\alpha(C_2)\) for Cluster B.
  2. What is the total MIS size \(\alpha(G)\) for the global network?
  3. Compare the quantum Hilbert space dimension required for a monolithic circuit versus the Quanifi decomposed pipeline.
  4. If worker 1 solving Cluster A takes 2.5 seconds and worker 2 solving Cluster B takes 1.1 seconds, explain how NiFi's MergeContent ensures accurate reassembly without race conditions.
👉 Click to Reveal Exercise Solution & Explanation

Solution:

  1. Component MIS Cardinalities:
    • Cluster A (\(K_{3,3}\)): In a complete bipartite graph, you can select either all nodes in partition \(A\) (size 3) or all nodes in partition \(B\) (size 3), but never both because all cross-edges exist. Thus, \(\alpha(C_1) = 3\) (e.g. nodes {0, 1, 2}).
    • Cluster B (\(S_5\)): In a star graph, you can either pick the 1 center node (size 1) or all 4 outer satellite nodes (size 4). The maximum is all outer satellites: \(\alpha(C_2) = 4\) (nodes {7, 8, 9, 10}).
  2. Global MIS Cardinality: $$\alpha(G) = \alpha(C_1) + \alpha(C_2) = 3 + 4 = 7$$ The global Maximum Independent Set has 7 nodes: {0, 1, 2, 7, 8, 9, 10}.
  3. Hilbert Space & Qubit Comparison:
    • Monolithic: Total nodes \(|V| = 6 + 5 = 11\) qubits. State vector size = \(2^{11} = 2,048\) complex amplitudes.
    • Decomposed (Quanifi): Circuit 1 requires 6 qubits (\(2^6 = 64\) amplitudes); Circuit 2 requires 5 qubits (\(2^5 = 32\) amplitudes).
      Total state space evaluated across both workers = \(64 + 32 = \mathbf{96}\) amplitudes!
      Decomposition reduces simulation/optimization complexity by over 95%!
  4. NiFi Reassembly Without Race Conditions: When GraphSplitter forked the FlowFiles, it tagged both with identical fragment.identifier = "graph-run-uuid" and set fragment.count = 2.
    When Worker 2 finishes first (1.1s), FlowFile 2 enters the queue of MergeContent. MergeContent inspects the attribute fragment.count = 2, recognizes that only 1 of 2 fragments has arrived, and safely parks FlowFile 2 in its internal correlation buffer.
    When Worker 1 finishes (2.5s), FlowFile 1 arrives. MergeContent detects that all fragments for that UUID are present, merges the payloads, and releases the consolidated FlowFile downstream. No race condition, no thread blocking, and zero custom synchronization code!
← Previous 5. QAOA Portfolio Optimization Curriculum Return to Overview →