Solving the binary optimization problem for linear regression with Grover Adaptive Search

Quantum computing can solve in some cases optimization problems faster than classical one, since quantum mechanics phenomena could speed up the optimum search; in particular, it suits the formulation of Quadratic Unconstrained Binary Optimization (QUBO) problems, which can model many scenarios, such as finance and machine learning. The problem to be solved is mapped onto a cost function over binary variables, with weights involving at most couples of bits. QUBO problems can be solved with both quantum annealers and general-purpose gate-array-based quantum computers. The former mimics the behaviour of simulated annealing in a quantum framework; the latter exploits quantum superposition to explore the solution space concurrently, as the Grover Adaptive Search (GAS) algorithm, which is the object of this thesis, does through Grover Search (GS) algorithm. GS algorithm allows to find one or more items in an unordered database, mapped onto a superposition of qubit states, by labelling the elements to be found and amplifying their probability amplitude with interference mechanism. In the context of interest, a quantum dictionary circuit, entangling a first set of qubits (keys register) to a second one (values register), is exploited for obtaining a superposition of all domain-image couples of the QUBO function, and GS finds negative values of it. GAS is a hybrid quantum-classical algorithm which iteratively exploits GS for finding the optimal value. In particular, after the initialization of the QUBO function at the beginning of the algorithm, two steps are repeated until no negative values are present in the function and the optimal solution has a null value: execution of GS to sample a negative value of the cost function and translation of it by subtracting the value of the last measured sample. The goals of this thesis are the design and the implementation of GAS and its exploitation for solving linear regression problems, described as a QUBO model, identifying the quadratic error between the points and the interpolating line as the cost function. The quantum circuit for GS has been implemented in Python using the ETH Zurich’s framework ProjectQ and it has been tested on a noiseless qubits classical simulator, as the large number of the needed qubits precludes the execution on the available quantum computers. The obtained results have shown that, in order to maximize the probability of sampling a negative value, the central routine of GS must be iterated a number of times depending on the search domain and that, unfortunately, this is not known a priori. Moreover, another crucial point of the GAS algorithm is identifying the achievement of the minimum, i.e. the end of the algorithm. Different strategies to optimize both the degrees of freedom have been studied. It has been ascertained that the most reasonable approaches are choosing randomly the GS iterations and evaluating multiple times the GS result, in the same iteration of GAS, to avoid a false minimum. Ultimately, the GAS results for linear regression problems have been compared with those of Quantum and Simulated Annealing. GAS has been proven to get higher success probability than Quantum Annealing. It is expected that GAS could be improved by establishing rules to forecast the best parameters for the algorithm, also taking into account the QUBO problem to be solved. Exploiting statistical calibrations or formulating machine learning models are possible approaches for obtaining these.