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 facilities to 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.
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 facilities to 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.
Combinatorial optimization problems play a central role in computer science with many real world applications. A number of relevant problems remain computationally difficult to solve as they lie in the NP-hard complexity class. We present a unified framework for solving such optimization problems represented in the quadratic unconstrained binary optimization (QUBO) formalism, namely two-SAT, XOR-SAT, mixed-two-XOR-SAT, set packing, quadratic assignment, binary clustering, and protein folding, by expanding the domain of applications of \textit{PRR, 6(2), 023031}. A direct mapping from the QUBO form of these problems onto the Rydberg quantum platform is demonstrated as our first step. This mapping to the Rydberg system depends on distance-dependent long-range interactions and configurable local detuning, thus reducing resource overhead and improving scalability. Following-up on the encoding, the solution is reached by steering the system toward the ground state of the target Hamiltonian using an optimized quantum annealing protocol that controls the time-dependent detuning and Rabi frequency profiles. The framework can handle a variety of problems, each with different complexity. To quantify the complexity of any problem, a generalized hardness parameter is introduced that compares different problems based on the structure of their optimization landscapes. This is a proceedings contribution to the Athens Workshop in Theoretical Physics: 10th Anniversary, held at the National and Kapodistrian University of Athens on December 17-19 2025.
Qubit routing is a fundamental problem in quantum compilation, known to be NP-hard. Its dynamic nature makes local routing decisions propagate and compound over time, making global efficient solutions challenging. Existing heuristic methods rely on local rules with limited lookahead, while recent learning-based approaches often treat routing as a generic sequential decision problem without fully exploiting its underlying structure. In this paper, we introduce QAP-Router, framing qubit routing based on a dynamic Quadratic Assignment Problem (QAP) formulation. By modeling logical interactions, or quantum gates, as flow matrices and hardware topology as a distance matrix, our approach captures the interaction-distance coupling in a unified objective, which defines the reward in the reinforcement learning environment. To further exploit this structure, the policy network employs a solution-aware Transformer backbone that encodes the interaction between the flow matrix and the distance matrix into the attention mechanism. We also integrate a lookahead mechanism that blends naturally into the QAP framework, preventing myopic decisions. Extensive experiments on 1,831 real-world quantum circuits from the MQTBench, AgentQ and QUEKO datasets show that our method substantially reduces the CNOT gate count of routed circuits by 15.7%, 30.4% and 12.1%, respectively, relative to existing industry compilers.
We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective.
Combinatorial optimization problems represent a wide range of real-world scenarios where complicated interactions make it difficult to find the best solution. One example is the quadratic assignment problem (QAP), which involves determining the optimal placement of facilities at set locations which minimizes the products of material flow and facility distance. This representation is descriptive of many real-world scenarios, including the aggregate transportation costs of a supply chain. In this work, a probabilistic Ising machine (PIM) approach is implemented using probabilistic d-dimensional variables (p-dits), which are generalized, multi-state and multi-dimensional extensions to probabilistic bits (p-bits). Each p-dit corresponds to a location and stochastically oscillates between facility assignments based on the influence of the other p-dits. We show that with the same runtime and CPU, the PIM finds the best-known solution on 95% of considered instances from the QAP Library dataset, compared to just 36% for the standard Gurobi solver. For the unique largest problem in the library, a 2 to 3 order-of-magnitude decrease is observed in the time needed to reach specific solution qualities. We also show parallelization of our PIM through GPU implementations. A comparison to state-of-the-art QAP solver algorithms shows that they are consistently outperformed by both CPU and GPU implementations of the p-dit Ising machine.
The performance of the Quantum Approximate Optimisation Algorithm (QAOA) in solving the Quadratic Assignment Problem (QAP) is evaluated, with the Variational Quantum Eigensolver (VQE) as a benchmark. The QAP is directly revelant to numerous industry scenarios. The QAP, a Combinatorial Optimisation Problem (COP), is classified asNP-Hard. This classification means CPU time increases exponentially as the problem size scales when solving the QAP using deterministic optimisation techniques. Therefore, this work investigates the QAOA in search of a non-deterministic optimisation technique to efficiently obtain solutions to the QAP. This research compares two warm start techniques to solve QAP instances of sizes 3 to 7. The metrics of comparison - that measure efficiency and solution quality - were introduced in previous work on this topic. For the QAOA, the impact of the p-value, a determination of circuit depth, is investigated. Of the two quantum hybrid heuristics, the VQE retrieves solutions in a shorter computational time with a smaller circuit size, which allows for solving instances with a larger problem size. Compared to the VQE, the QAOA performs better in terms of feasibility as the problem size scales. The quantum warm start method results implies that the QAOA may not maintain higher solution quality for instances larger than size 4. Still, further investigation should be conducted once quantum devices with more qubits and higher quantum volumes are available.
Programmable quantum systems utilizing Rydberg atoms have recently been shown to efficiently encode combinatorial optimization problems. The relationships among the variables in these optimization problems can be transformed into a maximum weighted independent set problem within the Rydberg atom system, requiring at most a quadratic overhead in terms of the number of qubits. Although experiments with current Rydberg quantum systems have demonstrated linear speedup compared to classical algorithms, the overhead in both the number of qubits and time remains substantial. To further reduce the overhead of encoding these optimization problems in Rydberg atom systems, we propose a simplification strategy and design a new heuristic algorithm that incorporates a topological sort approach to optimize the encoding process. We conduct extensive experiments on small graphs with dozens of qubits. The numerical results demonstrate the effectiveness of our algorithm in both runtime and optimization efficiency. Specifically, our algorithm reduces the number of required encoding qubits by 12.0% compared to existing methods. Additionally, our approach reduces the time complexity to a quadratic overhead, enabling experiments on larger graphs. The results further indicate that our algorithm provides significant time advantages over existing solutions.