Discrete-time quantum walk-based optimization algorithm

Optimization is a collection of principles that are used for problem solving in a vast spectrum of disciplines. Given the specifics of a problem and a set of constraints, the objective is to find a collection of variables that minimize or maximize an objective function. We developed a novel quantum optimization algorithm based on discrete-time quantum walks that evolve under the effect of external potentials. Each discrete lattice site corresponds to a value of the objective function’s domain of definition. The objective function is expressed as the external potential that affects the quantum walks evolution. The quantum walker is able to find the global minimum by utilizing quantum superposition of the potential affected lattice sites where the evolution occurs. We tested its performance considering two use cases. First, we designed a neural network for binary classification, where we utilized the quantum walk-based optimizer to update the neurons’ weights. We compared the results with the ones of a classical optimizer, i.e., stochastic gradient descent, on four different datasets. The quantum walks-based optimization algorithm showed the ability to match the performance of the classical counterpart using less training steps, and in some cases, it was able to find near optimal weights in only one training iteration. Finally, we considered the case of hyperparameter fine-tuning where, the quantum walk-based optimizer was used to optimize the parameters of a classical machine learning model, to increase its accuracy.