Tensor Network QAOA for Document Graphs: Narrative Map Extraction from News

Selecting a compact subgraph of a document graph while maximising a learned coherence function, subject to flow conservation and temporal ordering, is important in storyline detection, event threading, and Narrative Map extraction. Existing Narrative Map methods either recover a single optimal path (a Narrative Trail) or solve a linear program with an output size which grows with graph density (Narrative Maps). We propose a hybrid classical–quantum pipeline that casts the problem as a Quadratic Unconstrained Binary Optimisation (QUBO) problem and solves it both with the Quantum Approximate Optimisation Algorithm (QAOA) and with off-the-shelf classical QUBO solvers (simulated annealing, Tabu search) on the same Hamiltonian; this approach uses a classical mean field active space reduction and Matrix Product State tensor network simulation to scale beyond 16 qubits. We evaluate node- and edge-level qubit encodings under a range of QAOA circuit variants (transverse field and XY mixers; classical warm-start deeper circuits) on a 418-document news corpus across four graph densities and ten endpoint pairs, and audit their reproducibility across optimiser seeds. The QUBO formulations—whether solved by QAOA or by classical QUBO solvers on the same Hamiltonian—produce maps averaging 4.7–9.0 nodes versus 26.6 for Narrative Maps (p<10−7) and they are far more focused on their main storyline (main path fraction 0.61–0.99 versus 0.20). The Hamming-weight-preserving XY mixer goes the furthest: the node-level XY mixer variant produces the most compact (4.7 nodes) and most spine-focused (0.99 main path fraction) maps of any method tested, and a multi-seed audit identifies it as the most reproducible of the eight QAOA variants we compared. Main path coherence is on par with Narrative Maps’ and 0.031–0.072 below the bottleneck-optimising baselines—Narrative Trails (0.770) and Iterative Maximin (0.758). These results position QAOA not as a uniformly stronger alternative but as a distinct trade-off region favouring compactness and spine focus over raw bottleneck coherence and corpus topic breadth.