QUBO models preprocessing toolchain for quantum solvers

Combinatorial optimization problems aim to find the configuration of inputs that minimizes a cost function and can be employed in many real-world applications. Most of them are known to be NP-complete or NP-hard, thus classically solvable with exponential complexity. Quadratic Unconstrained Binary Optimization (QUBO) formulation can express them in a format suitable for quantum solvers, which can reduce the computational complexity by exploiting the quantum principles. One of the most recent solvers, the Grover Adaptive Search (GAS), is a successive approximation method that iteratively shifts the cost function whenever a negative value is obtained until the minimum is achieved. It encodes the function in a quantum state as key-value pairs and exploits Grover’s Search (GS), a quantum routine able to explore an unordered dataset with lower complexity than the classical counterpart, for obtaining negative samples. Since current quantum hardware still has a limited number of qubits, this thesis seeks to build a QUBO preprocessing toolchain for quantum solvers, in particular for GAS algorithm, focused on reducing the number of variables of the problem. The toolchain uses Cython to bridge between Python, which is used by most quantum backend APIs, and C++, which is used to implement the algorithms guaranteeing the efficiency of a compiled language. The toolchain consists of many steps of at most polynomial complexity. First, the cost function is transformed to an equivalent network form to find persistencies, i.e., variables to which binary values valid in at least one optimal solution can be assigned. Two routines exploit graph traversals and Strongly Connected Components (SCCs), which are subgraphs where every node is reachable from any other node, to find these assignments. Finally, by eliminating the persistencies, a homogeneously quadratic function is obtained. After these procedures, decomposition routines divide the network into smaller ones: separating the disconnected components, which correspond to independent subfunctions, and extracting the remaining SCCs. The latter operation is needed because the minimum of a purely quadratic function can be obtained just by finding the minima of the subfunctions associated with these components. In this way, when solving the networks with no SCCs the minimum is known in advance, thus applying GS instead of GAS is sufficient to obtain the optimal solution, which significantly decreases the execution time. The presented mechanisms also permit the decomposition of specific classes of problems and the computation of a lower bound for the optimal solution, which allows the estimation of the number of qubits necessary for representing the cost function values in a quantum state. Finally, if the available hardware resources are still insufficient, the Shannon decomposition partitions the problem into two functions: one in which a chosen variable is equal to 1 and the other in which it is 0. Besides, if the variable removal breaks an SCC into two, the subfunction can be in turn decomposed. The results show that the persistency-finding techniques are very efficient in removing all the variables that are not part of SCCs. For many benchmarks, once persistencies are taken out, decompositions reveal that functions are composed of a unique SCC. Moreover, the SCC usually has a size not small enough to directly run GS on currently available backends. Hence, breaking down SCCs is the only way to furtherly reduce the number of variables.