Qubit allocation is a central step in adapting abstract quantum circuits to noisy intermediate-scale quantum devices, yet exact approaches for solving it face severe scalability limitations. In this work, we revisit the formulation of qubit allocation as a permutation-based quadratic assignment problem and develop a branch-and-bound algorithm for its exact resolution. We first establish a refined sequential implementation that achieves significantly faster runtimes than previous exact approaches on most problem instances, thereby setting a new state-of-the-art for this formulation. Building on this foundation, we extend the approach to a performance-aware parallel implementation that exploits both intra-node and inter-node parallelism on High-Performance Computing (HPC) infrastructures. Our experimental evaluation demonstrates near-linear strong scaling at the intra-node level and substantial scalability in distributed settings across nodes. Leveraging these capabilities, we provide reference optimal solutions for challenging benchmark circuits of up to 26 qubits—significantly larger than previously reported instances. These results show that large-scale parallelization can effectively extend the reach of exact methods for qubit allocation, thereby advancing the integration of combinatorial optimization and HPC techniques in quantum computing.
Qubit allocation is a central step in adapting abstract quantum circuits to noisy intermediate-scale quantum devices, yet exact approaches for solving it face severe scalability limitations. In this work, we revisit the formulation of qubit allocation as a permutation-based quadratic assignment problem and develop a branch-and-bound algorithm for its exact resolution. We first establish a refined sequential implementation that achieves significantly faster runtimes than previous exact approaches on most problem instances, thereby setting a new state-of-the-art for this formulation. Building on this foundation, we extend the approach to a performance-aware parallel implementation that exploits both intra-node and inter-node parallelism on High-Performance Computing (HPC) infrastructures. Our experimental evaluation demonstrates near-linear strong scaling at the intra-node level and substantial scalability in distributed settings across nodes. Leveraging these capabilities, we provide reference optimal solutions for challenging benchmark circuits of up to 26 qubits—significantly larger than previously reported instances. These results show that large-scale parallelization can effectively extend the reach of exact methods for qubit allocation, thereby advancing the integration of combinatorial optimization and HPC techniques in quantum computing.
Static qubit allocation maps a circuit's logical qubits to a sparse physical device while minimising an interaction-weighted physical-distance cost function, yielding a rectangular quadratic assignment problem. Existing work combines strong lower bounds with distributed branch-and-bound. We integrate graph-aware exact reductions with an engineering bundle for a lightweight assignment-bound path: unavoidable assigned-cost filtering, incrementally maintained root-orbit and prefix-stabilizer symmetry pruning, conditioned parent-LAP screening, and circuit-independent physical device profiles. On 21 relatively easy Melbourne instances and six Boeblingen instances completed by the GLB baseline, the final single-thread configuration provides geometric-mean speedups of 2.98x and 13.27x, respectively. With 60 threads on one shared-memory server, all instances in the final Boeblingen--Cairo experiment are certified optimal within half an hour, excluding one-time device-artifact construction. These results show that graph-aware node processing and engineering the search process substantially reduce the resources required for exact allocation.
Abstract In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms formulated in the circuit model of computation onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (Optimal qubit assignment and routing via integer programming, 2021, http://arxiv.org/abs/2106.06446 ), we formulate the allocation subproblem as a binary linear program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. We present numerical results for the fully integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of artificial gates and output circuit depth when compared to various state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods.
Quantum circuit simulation enables the execution of large-scale quantum algorithms by partitioning qubits across multiple computational nodes. However, an inefficient qubit placement leads to excessive inter-node communication, limiting performance and scalability. This work introduces a framework that computes a communication-aware qubit placement offline, minimizing data exchange among nodes, and selects, before circuit execution, the largest node count whose performance degradation stays below a user-defined threshold. The framework is integrated with the QuEST simulator. Evaluations on synthetic benchmarks and real-world QASMBench circuits show that optimized placements reduce communication and achieve runtime speedups of up to 2.3x over the identity placement, particularly in circuits with sparse, structured interactions. Our results show that qubit placement strongly affects the efficiency of distributed simulation and provide a practical, resource-scalable solution for quantum workload
Due to the expected disparity in quantum vs. classical clock speeds, quantum advantage for branch and bound algorithms is more likely achievable in settings involving large search trees and low operator evaluation costs. Therefore, in this paper, we describe and experimentally validate an exact classical branch and bound solver for quadratic unconstrained binary optimization (QUBO) problems that matches these criteria. Our solver leverages cheap-to-implement bounds from the literature previously proposed for Ising models, including that of Hartwig, Daske, and Kobe from 1984. We detail a variety of techniques from high-performance computing and operations research used to boost solver performance, including a global variable reordering heuristic, a primal heuristic based on simulated annealing, and a truncated computation of the recursive bound. We also outline a number of simple and inexpensive bound extrapolation techniques. Finally, we conduct an extensive empirical analysis of our solver, comparing its performance to state-of-the-art QUBO and MaxCut solvers, and discuss the challenges of a speedup via quantum branch and bound beyond those faced by any quadratic quantum speedup.
Solving optimization problems is critical across many research domains, but the high dimensionality of parameter spaces often poses significant challenges. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for accelerating optimization in the Noisy Intermediate-Scale Quantum (NISQ) era by leveraging both classical and quantum computational resources. However, its performance can vary depending on the underlying quantum hardware architecture. In this work, we evaluate the performance of QAOA on different quantum hardware platforms, specifically, superconducting transmon qubits and trapped-ion qubits, targetting real-world optimization problems formulated as fully connected Quadratic Unconstrained Binary Optimization (QUBO) instances. We evaluate both the solution quality and time-to-solution using dense QUBO matrices. Furthermore, we show that large-scale problems, such as a 100-bit QUBO instance, can be effectively tackled by integrating quantum computing with high-performance computing (HPC) resources. This study provides practical insights into the strengths and limitations of different qubit technologies and advances the application of quantum computing in solving real-world optimization problems.
Scaling fault-tolerant quantum computing to practical advantage requires distributing quantum circuits across networks of heterogeneous processors. However, managing physical qubit overhead while satisfying strict logical error targets remains a critical bottleneck. We introduce the Error-Aware Distributed Quantum Computing (EA-DQC) problem, a unified framework for minimizing the physical footprint of distributed circuits under global error and per-processor capacity constraints. To drive our algorithm design and enable formal performance guarantees, we leverage an aggregation model that frames single-qubit allocation as a Generalized Assignment Problem (GAP), allowing us to prove the optimality of our main algorithm (BPF) in several hardware-specific cases. We also consider the generalized setting of multi-qubit block-encodings, which introduce sub-additive costs and non-monotonic scaling that break standard assignment frameworks, necessitating a density-aware algorithm (BCF-Set) to exploit synergistic resource efficiencies. We evaluate our framework on a diverse set of synthetic and benchmark circuits (QFT, QPE, GHZ) across heterogeneous network topologies. Our results show that our combinatorial heuristics achieve up to a 50% reduction in physical-qubit overhead compared to stochastic baselines such as Simulated Annealing. This work provides a rigorous bridge between quantum error correction and classical optimization, offering a scalable path for resource-efficient faulttolerant distributed quantum architectures.