Quantum Computing for Solving Spatial Optimization Problems

Paul-Amaury Matt, Marco Roth

We introduce a novel quantum computing heuristic for solving the irregular strip packing problem, a significant challenge in optimizing material usage across various industries. This problem involves arranging a set of irregular polygonal pieces within a fixed-height, rectangular container to minimize waste. Traditional methods heavily rely on manual optimization by specialists, highlighting the complexity and computational difficulty of achieving quasi-optimal layouts. The proposed algorithm employs a quantum-inspired heuristic that decomposes the strip packing problem into two sub-problems: ordering pieces via the traveling salesman problem and spatially arranging them in a rectangle packing problem. This strategy facilitates a novel application of quantum computing to industrial optimization, aiming to minimize waste and enhance material efficiency. Experimental evaluations using both classical and quantum computational methods demonstrate the algorithm's efficacy. We evaluate the algorithm's performance using the quantum approximate optimization algorithm and the quantum alternating operator ansatz, through simulations and real quantum computers, and compare it to classical approaches.

Z. N. Zakaryayev, N. Z. Zakarya

Junze Yao, Junjie Yu

Combinatorial optimization problems are challenging for classical computing architectures, motivating the development of specialized hardware like Ising machines. The Spatial Photonic Ising Machine (SPIM) and its enhanced versions have shown promise in solving such problems by mapping them to the Ising model and leveraging optical parallelism to compute Hamiltonian energies efficiently. However, the 0-1 knapsack problem, as a representative combinatorial optimization problem, has only been reported to be solved effectively in small-scale SPIM. In this work, we analyze the factors that limit the spin scalability and propose a novel hardware-aware Hamiltonian mapping scheme to overcome this limitation. Based on this enhanced SPIM, the scheme is validated through simulated annealing experiments on a 102400-spin 0-1 knapsack problem, achieving high solution accuracy. Our method not only enables efficient solutions to large-scale 0-1 knapsack problems but also offers generalizability to other combinatorial optimization problems with similar coupling configurations. This work demonstrates the potential of SPIMs as scalable and adaptable solvers for real-world optimization challenges.

Nikolay Raychev

Dilnoz Muhamediyeva, Rustam Raximov, Shavkat Urokov

Yuh-Lin Chang, Amr Magdy, Federico M. Spedalieri

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.