Quantum Layout Optimization for Data Lineage Graphs

Overview & Synopsis

Data lineage graphs are large and complex structures that represent how information flows across information systems. This paper presents a novel approach to graph layout optimization using the Quantum Approximate Optimization Algorithm (QAOA). We introduce a space-filling curve-based encoding method that maps 2D node positions to single scalar values, enabling efficient quantum optimization while preserving spatial locality. Our approach addresses multiple layout objectives including edge crossing minimization, technology-based node grouping, and distance optimization, all within the constraints of current quantum hardware (~150 qubits). We demonstrate a divide-and-conquer clustering strategy that makes the method practical for large-scale data lineage graphs and show that QAOA can be executed on real quantum hardware today with immediate applicability.