Quantum Modeling of Spatial Contiguity Constraints

Quantum computing has demonstrated potential for solving complex optimization problems; however, its application to spatial regionalization remains underexplored.Spatial contiguity, a fundamental constraint requiring spatial entities to form connected components, significantly increases the complexity of regionalization problems, which are typically challenging for quantum modeling.This paper proposes novel quantum formulations based on a flow model that enforces spatial contiguity constraints.Our scale-aware approach employs a Discrete Quadratic Model (DQM), solvable directly on quantum annealing hardware for small-scale datasets.In addition, it designs a hybrid quantum-classical approach to manage larger-scale problems within existing hardware limitations.This work establishes a foundational framework for integrating quantum methods into practical spatial optimization tasks. CCS Concepts Theory of computation Quantum query complexity.