In the field emulation of quantum many-body systems, which involve numerous interacting sites, the Bandwidth Minimization Problem (BMP) plays an essential role, particularly in improving the computational cost of handling Tensor Networks . Tensors are multi-dimensional arrays that generalize scalars, vectors, and matrices, and are fundamental in modeling quantum many-body systems and their interactions. Tensor Networks provide a mathematical framework that use these tensors, connecting them to represent quantum states and operators.
In this work, EQUALITY partners from Pasqal introduce a weighted-BMP, a variant of the Bandwidth Minimization Problem, with a significant application in optimizing quantum emulation. Weighted-BMP optimizes particles ordering to reduce the emulation costs, by designing a particle interaction matrix where strong interactions are placed as close as possible to the diagonal.
The authors formulate the problem using a Mixed Integer Linear Program (MILP) and solve it to optimality with a state of the art solver. To strengthen their MILP model, they introduce symmetry-breaking inequalities and establish a lower bound. Through extensive numerical analysis, they examine the impacts of these enhancements on the solver's performance. The introduced reinforcements result in an average CPU time reduction of 25.61 percent.
Additionally, the group conducted quantum emulations of realistic instances. Their numerical tests show that the weighted-BMP approach outperforms the Reverse Cuthill-McKee (RCM) algorithm, an efficient heuristic used for site ordering tasks in quantum emulation, achieving an average memory storage reduction of 24.48 percent.
From an application standpoint, this study is the first to apply an exact optimization method, weighted-BMP, that considers interactions for site ordering in quantum emulation pre-processing, and shows its crucial role in cost reduction. From an algorithmic perspective, it contributes by introducing important reinforcements and lays the groundwork for future research on further enhancements, particularly on strengthening the weak linear relaxation of the MILP.
Read the paper by clicking on the link below.
