Quantum optimization algorithms

Mathematical optimization deals with finding the best solution to a problem (according to some criteria) from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. The power of quantum computing may allow solving problems which are not practically feasible on classical computers, or suggest a considerable speed up in respect to the best known classical algorithm. Among other quantum algorithms, there are quantum optimization algorithms which might suggest improvement in solving optimization problems.

Quantum Data Fitting

Data fitting is a process of constructing a mathematical function that best fits a set of data points. The fit's quality is measured by some criteria, usually the distance between the function and the data points.

Quantum Least Squares Fitting

One of the most common types of data fitting is solving the least squares problem, minimizing the sum of the squares of the differences between the data points and the fitted function.

The algorithm is given as input ${\displaystyle N}$  data points ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})}$ , and ${\displaystyle M}$  continuous functions ${\displaystyle f_{1},f_{2},...,f_{M}}$ . The algorithm finds and gives as output a continuous function ${\displaystyle f}$  that is a linear combination of ${\displaystyle f_{j}}$ :

${\displaystyle f(x,\lambda )=\sum _{j=1}^{M}f_{j}(x)\lambda _{j}.}$ 

In other words, the algorithm finds the complex coefficients ${\displaystyle \lambda _{j}}$ .

The algorithm is aimed at minimizing the error, that is given by:

${\displaystyle E=\sum _{i=1}^{N}|f(x_{i},\lambda )-y_{i}|^{2}=\sum _{i=1}^{N}|\sum _{j=1}^{M}f_{j}(x_{i})\lambda _{j}-y_{i}|^{2}=|F\lambda -y|^{2}}$ 

where we define ${\displaystyle F}$  to be the following matrix:

${\displaystyle \mathbf {F} ={\begin{pmatrix}f_{1}(x_{1})&\cdots &f_{M}(x_{1})\\f_{1}(x_{2})&\cdots &f_{M}(x_{2})\\\vdots &\ddots &\vdots \\f_{1}(x_{N})&\cdots &f_{M}(x_{N})\\\end{pmatrix}}}$ 

The quantum least-squares fitting algorithm^[1] takes use in a version of Harrow, Hassidim, and Lloyd's quantum algorithm for linear systems of equations (HHL), and produces fit parameters and a fit quality estimation. It is consisted of three subroutines: an algorithm for performing pseudo-inverse operation, one routine for the fit quality estimation, and an algorithm for learning the fit parameters.

The required inputs are a quantum state which holds the data of the ${\displaystyle y_{i},i=1...N}$ , an upper bound to the condition number, namely the ratio between the maximal and minimal eigenvalues of ${\displaystyle FF^{\dagger }}$  and ${\displaystyle F^{\dagger }F}$ , the sparseness of ${\displaystyle F}$ , a maximal number of inner fit functions allowed, and the error and quality thresholds.

As the quantum algorithm is mainly based on the HHL algorithm, it suggests exponential improvement^[2] in the case where ${\displaystyle F}$  is sparse, and the condition number of ${\displaystyle FF^{\dagger }}$  and ${\displaystyle F^{\dagger }F}$  is small.

Quantum Semidefinite Programming

Semidefinite programming (SDP) is an optimization subfield dealing with the optimization of a linear objective function (a user-specified function to be minimized or maximized), over the intersection of the cone of positive semidefinite matrices with an affine space. The objective function is phrased as a function of the variable ${\displaystyle X}$ , which is a positive semidefinite matrix, usually as an inner product of ${\displaystyle X}$  with a given matrix ${\displaystyle C}$ . The inner product for matrices can be defined by:

${\displaystyle \langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.}$ 

The SDP problem may have additional given constrains, also usually formulated as an inner product of given matrices ${\displaystyle A_{k}}$  with the optimization variable ${\displaystyle X}$  being smaller than a specified value ${\displaystyle b_{k}}$ . Finally, The SDP problem can be written as:

${\displaystyle {\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}}$ 

The classical state-of-the-art algorithm in terms of worst-case bounds is polynomial-timed. The quantum algorithm provides a quadratic improvement in the general case, and an exponential improvement, when the input matrices are low-rank.

The quantum algorithm

The algorithm inputs are oracles for ${\displaystyle A_{1}...A_{m},C,b_{1}...b_{m}}$  and parameters regarding the solution trace, precision and optimal value. The quantum algorithm reduces the problem to a feasibility problem, performing a binary search on the solution. One algorithm iteration can either output a feasible solution with an objective smaller than some value, or indicate that the optimal objective is larger than an other value, when these values are determined by chosen input parameters. Therefore, it can be run again with different parameters, binary searching the optimal objective value and solution. The algorithm takes use in a Gibbs sampler, as a probabilistic oracle sampler for estimating the mixed states of the density matrix through iterations. These samples of the density matrix oracle are used to determine final solution^[3].

Quantum Approximate Optimization

Approximate optimization is a way to find an approximate solution to an optimization problem, which is often NP-hard. For combinatorial optimization, there is a quantum algorithm^[4] that was previously considered to have a better approximation ratio than any polynomial-time classical algorithm (for a certain problem)^[5], until an efficient classical algorithm was proposed^[6]. However, the relative speedup of the quantum algorithm is an open research question.

The Combinatorial Optimization Problem

The objective function for a combinatorial optimization problem of ${\displaystyle n}$  bits and ${\displaystyle m}$  clauses can be written as:

${\displaystyle C(z)=\sum _{\alpha =1}^{m}C_{\alpha }(z)}$ 

Where ${\displaystyle z=z_{1}...z_{n}}$  is the bit string and ${\displaystyle C_{\alpha }(z)=1}$  if ${\displaystyle z}$  satisfies clause ${\displaystyle \alpha }$  (and 0 otherwise). The approximated solution is a string ${\displaystyle z}$  that is close to maximizing ${\displaystyle C(z)}$ .

Quantum Approximation Optimization Algorithm (QAOA)

The heart of the algorithm relies on the use ofunitary operators dependent on ${\displaystyle 2p}$  angles, where ${\displaystyle p>1}$  in an input integer. These operators are applied iteratively on the completely mixed state, namely a state that is a superposition of all possible states with equal probability. In each iteration, the state is measured in the computational basis and ${\displaystyle C(z)}$  is being calculated. After a sufficient amount of repetitions, the value of ${\displaystyle C(z)}$  is almost optimal, and the state being measured is close to optimal as well.

See also

• Adiabatic quantum computation
• Quantum annealing

References

1. Wiebe, Nathan; Braun, Daniel; Lloyd, Seth (2 August 2012). "Quantum Algorithm for Data Fitting". Physical Review Letters. 109 (5). doi:10.1103/PhysRevLett.109.050505.
2. Montanaro, Ashley (12 January 2016). "Quantum algorithms: an overview". npj Quantum Information. 2: 15023. doi:10.1038/npjqi.2015.23.
3. Brandao, Fernando G. S. L.; Svore, Krysta (18 September 2016). "Quantum Speed-ups for Semidefinite Programming". arXiv:1609.05537 [quant-ph].
4. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (14 November 2014). "A Quantum Approximate Optimization Algorithm". arXiv:1411.4028 [quant-ph].
5. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (18 December 2014). "A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem". arXiv:1412.6062 [quant-ph].
6. Barak, Boaz; Moitra, Ankur; O'Donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John (13 May 2015). "Beating the random assignment on constraint satisfaction problems of bounded degree". arXiv:1505.03424 [cs].