The quantum version of the shifted power method and its application in quadratic binary optimization

Abstract

In this paper, we present a direct quantum adaptation of the classical shifted power method. The method is very similar to the iterative phase estimation algorithm; however, it does not require any initial estimate of an eigenvector, and as in the classical case its convergence and the required number of iterations are directly related to the eigengap. If the amount of the gap is in the order of 1/poly(n), then the algorithm can converge to the dominant eigenvalue in O(poly(n)) time. The method can be potentially used for solving any eigenvalue related problem and finding minimum/maximum of a data set in lieu of Grover's search algorithm. In addition, if the solution space of an optimization problem with n parameters is encoded as the eigenspace of an 2n dimensional unitary operator in O(poly(n)) time and the eigengap is not too small, then the solution for such a problem can be found in O(poly(n)). As an example, using the quantum gates, we show how to generate the solution space of the quadratic unconstrained binary optimization as the eigenvectors of a diagonal unitary matrix and find the solution for the problem.