Quantum Approaches to the Quadratic Assignment Problem

Nathan Daly, Thomas Krauss, Julia Shapiro · 2025

Read Quantum Approaches to the Quadratic Assignment Problem by Nathan Daly, Thomas Krauss, Julia Shapiro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00182.txt.

Introduction

Assigning factories to sites so that transport costs stay low is a classic hard puzzle, known since 1957 as the quadratic assignment problem. Even modest versions defeat exact classical search. Nathan Daly, Thomas Krauss, and Julia Shapiro open a new front on it: quantum hardware built from Rydberg atoms, whose interactions can mirror the puzzle's cost structure.

They give an algorithm that uses the atom array to find valid and optimal assignments. Alongside it they develop circuit theory that makes it easy to phrase other hard problems for the same machinery. The work is a first step rather than a finished solver. It sets out how this quantum platform could attack a problem that sits at the heart of logistics and chip design.

Catalog record

CREATORNathan Daly, Thomas Krauss, Julia Shapiro
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-00182

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Approaches to the Quadratic Assignment Problem Nathan Daly, Thomas Krauss, Julia Shapiro Abstract The Quadratic Assignment Problem (QAP) is an NP-hard fundamental combinatorial optimization problem introduced by Koopmans and Beckmann in 1957. The problem is to assign n n facilities to n n different locations with the goal of minimizing the cost of the total distances between facilities weighted by the corresponding flows. We initiate the study of using Rydberg arrays to find optimal solutions to the QAP and provide a complementing circuit theory to facilitate an easy representation of other hard problems. We provide an algorithm for finding valid and optimal solutions to the QAP using Rydberg arrays. Keywords— quadratic assignment problem, neutral atom, algorithms, circuits 1 Introduction The QAP was introduced by Koopsman and Beckmann in [ 9 ] and is a fundamental problem in combinatorial optimization and operations research. It represents a challenging class of problems related to assigning a set of n facilities to a set of n locations with the goal of minimizing the cost associated with the assignments. The cost is a product of the distances between locations and the pair-wise flow between facilities, making the Quadratic Assignment Problem particularly useful in scenarios where both spatial positioning and inter-facility interactions are critical. Originally formulated to address facility layout issues, Quadratic Assignment Problem has since found applications in various fields: for instance, in manufacturing, it optimizes layout to reduce transportation costs or improve process efficiency; in data centers, it helps assign servers to physical locations to minimize latency and energy use. Beyond these, Quadratic Assignment Problem has applications in DNA sequencing [ 4 ] , airport terminal planning [ 5 ] , and backboard layout [ 14 ] . Solving Quadratic Assignment Problem is computationally intensive and research in the field focuses on both exact and heuristic approaches. Many research directions for finding optimal solutions to the Quadratic Assignment Problem have focused on classical methods [ 2 , 3 , 10 , 7 , 8 , 11 , 12 , 15 , 16 , 1 , 17 , 18 , 19 ] but these methods are constrained to small problem sizes. Recent work using Rydberg arrays and QuEra’s Aquilas hardware, a 256 neutral atom quantum computer, to solve the Maximum Independent Set (MIS) problem yielded promising results [ 6 ] . In [ 13 ] , the authors introduce a general framework for mapping combinatorial optimization problems to unit disk graphs (UDG) and Rydberg arrays such as the MIS problem and the Maximum Weighted Independent Set (MWIS) problem and extend this to general classes of constrained binary optimization problems. In this paper, we initiate the study of the Quadratic Assignment Problem using Rydberg arrays. In particular, we provide a general framework for circuit construction for classes of constrained binary optimization problems and we apply the gadget construction provided in [ 13 ] to enforce constraints for the Quadratic Assignment Problem problem. The framework provided facilitates the design of the reduction from the Quadratic Assignment Problem to UDG-MWIS and of quantum algorithms for other problems. We show, through the general framework provided and the reduction of QAP to UDG-MWIS, that Rydberg arrays can not only be used to solve other hard problems but also be optimized for improved performance. This paper is organized as follows. In Section 2 , we will discuss the problem set up and the Rydberg array approach to solving the maximum independent set and maximum weighted independent set problems provided in [ 13 ] . In Section 3 , we present our framework for circuit construction of a broader class of constrained binary optimization problems. In Section 4 , we extend the techniques applied to the MIS and MWIS problems in [ 13 ] and provide a general process for mapping Quadratic Assignment Problem to an instance of MWIS and show that this reduction encodes valid and optimal solutions of the Quadratic Assignment Problem. We then provide an optimized algorithm that reduces the number of variables needed to represent instance of the Quadratic Assignment Problem. We show that the MWIS of the graph constructed in the reduction corresponds to optimal solutions of the original Quadratic Assignment Problem instance. 2 Preliminaries and Prior Work In this section, we formally introduce the Quadratic Assignment Problem and the approach to solving the Maximum Independent Set and Maximum Weighted Independent Set on Rydberg neutral atom hardware using the formulation provided in [ 13 ] . 2.1 The Quadratic Assignment Problem The Quadratic Assignment Problem models the following situation: given n facilities and n locations, assign all facilities to different locations with the goal of minimizing the cost, that is, the sum of the distances between locations multiplied by the corresponding flows between facilities. The model is based on the following constraints: 1. Each facility can only be in one location, 2. Each location can take only one facility, and, 3. The cost of this process is measured by the pair-wise distance between locations times flow between facilities at the locations Formally, an instance of the Quadratic Assignment Problem is the tuple I=(F,D) , where F is the flow matrix each of whose entries f_{xy} is the flow from facility x to facility y and D is the distance matrix each of whose entries d_{ij} is the distances between location i and location j . A valid assignment of facilities to locations is a permutation \pi:[n]\to[n], where [n]:=\{1,\ldots,n\} . We can represent \pi as a permutation matrix \Pi each of whose entries \pi_{xi} is 1 if \pi(x)=i (facility x is placed in location i ) and 0 otherwise. The cost function for the Quadratic Assignment Problem can be represented as C(\Pi)=\sum_{x,y,i,j=1}^{n}f_{xy}d_{ij}\pi_{xi}\pi_{yj}. The goal is to find the assignment of facilities to locations satisfying the above constraints that minimizes C(\Pi). For an n\times n Quadratic Assignment Problem problem, using brute force one would have to check n! assignments \Pi, as |S_{n}|=n! . As n grows larger, it becomes exponentially difficult to find the assignment \pi corresponding to the minimum cost C(\Pi) for the n\times n Quadratic Assignment Problem. 2.2 MIS Using Rydberg Arrays In [ 6 ] , the quantum optimization of the MIS problem utilizing Rydberg arrays and QuEra’s Aquila hardware showcased promising results for solving the MIS problem with Rydberg arrays. The authors observe a superlinear quantum speedup in finding exact solutions of the MIS problem. In this section, we discuss the formulation using encoding gadgets for the Maximum Independent Set and Maximum Weighted Independent Set Problems with Rydberg arrays as in [ 13 ] . We start with the following definitions. Definition 2.1 . A graph G=(V,E) is a pair consisting of a vertex set V(G) and an edge set E(G) , where an edge is a set of two vertices. Definition 2.2 . An independent set of a graph G is a subset of the vertices of G in which no two vertices in the subset are connected by an edge. Definition 2.3 . A maximum independent set (MIS) of a graph G is an independent set containing at least as many vertices as any other independent set. (a) An MIS example (b) A non MIS example Fig. 1 : Examples of MIS:

Read the complete text