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.
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.
Narrative extraction algorithms construct storylines by finding coherent paths through document collections. The Narrative Trails algorithm frames this as maximum-capacity path optimization, where path quality depends on a coherence function measuring document relationships. We introduce quantum kernels as coherence functions for narrative extraction—to the best of our knowledge, the first systematic characterisation of quantum kernel methods for storyline extraction—and compare them against classical baselines on two corpora using a multi-seed protocol. The sweep covers 93 method evaluations (54 quantum kernels across three encoder families—RY+CNOT-ring, IQP/ZZ-feature-map, and a projected quantum kernel—and 39 classical kernels—cosine, RBF, and the cluster-aware Narrative Trails baseline). On 11,215 human navigation paths from Wikispeedia, evaluation metrics divide into two clusters that disagree with each other: alignment-based metrics (length-normalised DTW and per-step DTW similarity) favour methods that produce long alignment-rich paths, while set-overlap metrics (Jaccard and F1) favour methods that produce shorter paths with higher article overlap. On LLM-judged coherence for Cuban news storylines, evaluated under a 12-method × 5-seed × 30-endpoint-pair × 2-judge design (Claude Sonnet 4.5 and GPT-4o, both at T=0 via structured tool calling), the cluster-aware classical baseline is the top method in terms of mean overall coherence; the 5-method quantum-kernel pool and the 7-method classical-kernel pool on matched projection input show no significant differences after Holm correction. Cross-task analysis reveals that LLM coherence rank correlates with alignment-cluster Wikispeedia metrics (Spearman ρ≈+0.70) and anti-correlates with overlap-cluster metrics (ρ≈−0.62). A closed-form theoretical analysis shows that the depth-1 RY+CNOT-ring kernel reduces to a classical product-of-cosines kernel order equivalent to RBF, explaining the absence of empirical separation at low depth; deeper encoders break the cancellation but exponentially concentrate kernel values, eroding inter-pair distinguishability. Our results characterise quantum coherence kernels as competitive with classical kernels on the same projected input rather than decisively superior, with the cluster-aware classical baseline retaining a modest advantage attributable to its explicit topical structure.
Protein-protein interaction (PPI) network alignment combines topological and sequence information to identify conserved modules across species, but global alignment remains challenging: heuristics sacrifice optimality, while exact methods lack scalability. We model the alignment as a weighted maximum common induced subgraph problem and reformulate it through the modular product graph to a minimum-weight vertex cover on the complement, with node weights carrying sequence similarity. To solve this problem, we develop a hybrid framework combining kernelisation, branch-and-bound, and seven Quantum Approximate Optimisation Algorithm (QAOA) formulations. These formulations differ in how the cover constraints are enforced, from penalty terms in the cost Hamiltonian to mixers confined to the feasible subspace. For single round QAOA, we derive closed-form expressions for the expected cost of four circulant mixer variants, enabling performance characterisation without circuit simulation. Applied to synthetic and real-world networks reduced to KEGG pathways, the QAOA formulations achieve high topological conservation on the aligned core while at least maintaining biological conservation comparable to leading classical aligners, at the cost of reduced node coverage. Across selected KEGG pathways, the aligned subnetworks retain disease-associated proteins, preserving biologically relevant information. Cheaper formulations leave more edges uncovered, while enforcing feasibility in the mixer raises circuit depth by one to two orders of magnitude. Together, these results highlight the potential of quantum optimisation for PPI network alignment and the resource trade-offs that will shape its scalability as quantum hardware matures.
Sidechain packing is a critical stage in protein folding, with direct implications for structure-based drug discovery. Google DeepMind's tool, AlphaFold2, predicts protein backbone reliably but sidechain positioning less accurately. Recovering the lowest-energy rotamer assignment over a fixed backbone is NP-hard. We present a hybrid quantum-classical pipeline that repacks sidechains on the AlphaFold backbone using the Quantum Approximate Optimisation Algorithm (QAOA), encoding the one- and two-body energies as a quadratic unconstrained binary optimisation (QUBO) problem. We introduce a constraint-preserving ansatz, pairing a W-state initialisation with a cyclic XY ring mixer, that enforces one-hot rotamer validity without penalty terms while keeping two-qubit gate scaling linear in the rotamer count. We also define an asymptotic shot-scaling metric, measured against the experimentally resolved conformation, that fixes optimiser quality independently of the baseline; its fitted growth stays below the classical exhaustive-search rate at moderate rotamer flexibility. Evaluated on bovine pancreatic trypsin inhibitor (5PTI) across high- and moderate AlphaFold-confidence regions, the pipeline lowers conformational energy against the AlphaFold baseline.
Quadratic unconstrained binary optimization (QUBO) tasks are very important in chemistry, finance, job scheduling, and so on, which can be represented using graph structures, with the variables as nodes and the interaction between them as edges. Variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) and its variants, present a promising way, potentially exceeding the capabilities of classical algorithms, for addressing QUBO tasks. However, the possibility of using message-passing machines, inspired by classical graph neural networks, to enhance the power and performance of these quantum algorithms for QUBO tasks was not investigated. This study introduces a novel variational quantum graph optimization algorithm that integrates the message-passing mechanism, which demonstrates significant improvements in performance for solving QUBO problems in terms of resource efficiency and solution precision, compared to QAOA, its variants, and other quantum graph neural networks. Furthermore, in terms of scalability on QUBO tasks, our algorithm shows superior performance compared to QAOA, presenting a substantial advancement in the field of quantum approximate optimization.
Comparing solvers for quadratic unconstrained binary optimization (QUBO) requires distinguishing solution quality from optimality certification. We compare classical, tensor-network, and fixed-schedule quantum approaches on 180 benchmark instances from ten families with 14-48 variables, supplemented by harder synthetic instances with known optimal solutions, extending to 128 variables. On the main benchmark, a general-purpose branch-and-cut solver matches all reference energies and certifies 176 instances within a 600,s cap. When the known optima are moved to randomly chosen bitstrings, the search comparison changes: at n = 48 the branch-and-cut solver finds only four of ten optima and certifies none, whereas parallel tempering reaches every optimum in every tested run at a 60,s budget. Structural and trajectory diagnostics explain aspects of tensor-network performance. A treewidth bound ranks trajectory bond-dimension demand at Spearman ρ=0.78 in sample and 0.73 out of sample, but provides only a coarse runtime estimate. Controlled experiments identify excited-state trapping during warm-started density-matrix renormalization group (DMRG) sweeps and demonstrate mitigation by restarting the variational search. These diagnostics do not yield a validated solver-selection rule. The tested linear-ramp quantum approximate optimization algorithm (LR-QAOA) runs offer no solution-quality improvement over the classical comparators. In the separate Wishart scaling study, on the harder setting, none of the classical methods tested reaches the optimum at the sampled sizes from n = 72 onward within the tested budgets. While this does not provide evidence for quantum advantage, it identifies a domain for further investigation.
Approximate combinatorial optimisation has emerged as one of the most promising application areas for quantum computers, particularly those in the near term. In this work, we focus on the quantum approximate optimisation algorithm (QAOA) for solving the MaxCut problem. Specifically, we address two problems in the QAOA, how to initialise the algorithm, and how to subsequently train the parameters to find an optimal solution. For the former, we propose graph neural networks (GNNs) as a warm-starting technique for QAOA. We demonstrate that merging GNNs with QAOA can outperform both approaches individually. Furthermore, we demonstrate how graph neural networks enables warm-start generalisation across not only graph instances, but also to increasing graph sizes, a feature not straightforwardly available to other warm-starting methods. For training the QAOA, we test several optimisers for the MaxCut problem up to 16 qubits and benchmark against vanilla gradient descent. These include quantum aware/agnostic and machine learning based/neural optimisers. Examples of the latter include reinforcement and meta-learning. With the incorporation of these initialisation and optimisation toolkits, we demonstrate how the optimisation problems can be solved using QAOA in an end-to-end differentiable pipeline.