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

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

PDF

___

1] Nielsen MA, Chuang I. Quantum computation and quantum information. Cambridge, UK: Cambridge University Press, 2002
2] Shor PW. Algorithms for quantum computation: Discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science; New York, USA; 1994. pp. 124-134.
[3] Harrow AW, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Physical Review Letters 2009; 103 (15): 150502.
[4] Kassal I, Whitfield JD, Perdomo-Ortiz A, Yung MH, Aspuru-Guzik A. Simulating chemistry using quantum computers. Annual Review of Physical Chemistry 2011; 62: pp. 185-207.
[5] Brown KL, Munro WJ, Kendon VM. Using quantum computers for quantum simulation. Entropy 2010; 12 (11): pp. 2268-2307.
[6] Farhi E, Goldstone J, Gutmann S, Sipser M. Quantum computation by adiabatic evolution. arXiv preprint quant- ph/0001106 2000.
[7] Farhi E, Goldstone J, Gutmann S, Lapan J, Lundgren A, Preda D. A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science 2001; 292 (5516): pp. 472-475.
[8] Farhi E, Goldstone J, Gutmann S. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 2014.
[9] Wossnig L, Zhao Z, Prakash A. Quantum linear system algorithm for dense matrices. Physical Review Letters 2018; 120 (5): 050502.
[10] Rebentrost P, Schuld M, Wossnig L, Petruccione F, Lloyd S. Quantum gradient descent and Newton’s method for constrained polynomial optimization. arXiv preprint arXiv:1612.01789 2016.
[11] Kerenidis I, Prakash A. Quantum gradient descent for linear systems and least squares. arXiv preprint arXiv:1704.04992 2017.
[12] Shao, C. Quantum arnoldi and conjugate gradient iteration algorithm. arXiv preprint arXiv:1807.07820 2018.
[13] Brandao FG, Svore KM. Quantum speed-ups for solving semidefinite programs. In: 58th Annual Symposium on Foundations of Computer Science (FOCS); Berkeley, California, USA; 2017. pp. 415-426.
[14] Van Apeldoorn J, Gilyén A, Gribling S, de Wolf, R. Quantum sdp-solvers: Better upper and lower bounds. In: 58th Annual Symposium on Foundations of Computer Science (FOCS); Berkeley, California, USA; 2017. pp. 403-414.
[15] van Apeldoorn J, Gilyén A, Gribling S, de Wolf R. Convex optimization using quantum oracles. arXiv preprint arXiv:1809.00643 2018.
[16] Saad Y. Numerical Methods for Large Eigenvalue Problems. Philadelphia, PA, USA: Siam, 2011.
[17] Grover LK. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters 1997; 79 (2): 325.
[18] Durr C, Hoyer P. A quantum algorithm for finding the minimum. arXiv preprint quant-ph/9607014 1996.
[19] Lucas A. Ising formulations of many np problems. Frontiers in Physics 2014; 2: 5.
[20] Loiola EM, de Abreu NMM, Boaventura-Netto PO, Hahn P, Querido T. A survey for the quadratic assignment problem. European Journal of Operational Research 2007; 176 (2): pp. 657-690.
[21] Rendl F, Pardalos P, Wolkowicz H. The quadratic assignment problem: A survey and recent developments. In: Proceedings of the DIMACS Workshop on Quadratic Assignment problems; New Jersey, USA; 1993. pp. 1-42