The central research objective of the proposed project is to develop an exact solver, called QBIQ, for binary quadratic optimization problems with linear and quadratic constraints, denoted by (QBO). We want to compute provably optimum solution, so the this problem is NP-hard and we can expect to solve it only for small and medium sized instances. The main computational framework will be the branch-and-bound algorithm (B&B), which is an exponential-time algorithm. It will utilize the best available supercomputers and quantum computers in the EU, as well as the best available software libraries for parallel and quantum computing. The QBIQ solver will consist of three solvers: a high-performance solver, a hybrid quantum-classical solver, and a pure quantum solver. It will be accessible through a unified user interface complemented by an artificial intelligence (AI) module that will decide which solver to use. The code for QBIQ will be made publicly available. The research part of the project includes theoretical and numerical investigations on how to obtain very tight yet numerically tractable upper and lower bounds for the optimum solution of (QBO), how to efficiently explore the B&B tree in parallel, and how to organise the computations to take full advantage of shared memory and distributed memory parallelization.

ARIS