Quantum optimization algorithms

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 9 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. 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 of a target functional.

For combinatorial optimization problems no proven exponential speed up has ever been found. Most provable results are similar to Grover's algorithm and have the potential for a modest polynomial speed up.

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 differences between the data points and the fitted function. The algorithm is given N input data points (x_1, y_1), (x_2, y_2), ... , (x_N, y_N) and M continuous functions f_{1}, f_{2}, ... , f_{M} .

The algorithm finds and gives as output a continuous function f_{\vec{\lambda}} that is a linear combination of f_j : f_{\vec{\lambda}}(x) = \sum_{j=1}^M f_{j}(x)\lambda_{j} In other words, the algorithm finds the complex coefficients \lambda_j , and thus the vector \vec{\lambda} = (\lambda_1, \lambda_2, ..., \lambda_M) . The algorithm is aimed at minimizing the error, which is given by: E=\sum_{i=1}^N \left\vert f_{\vec{\lambda}}(x_i)-y_i \right\vert^2 = \sum_{i=1}^N \left\vert \sum_{j=1}^M f_{j}(x_i)\lambda_{j}-y_i \right\vert^2 = \left\vert F\vec{\lambda}-\vec{y} \right\vert^2 where F is defined to be the following matrix: {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 makes use of a version of Harrow, Hassidim, and Lloyd's quantum algorithm for linear systems of equations (HHL), and outputs the coefficients \lambda_j and the fit quality estimation E . It consists of three subroutines: an algorithm for performing a pseudo-inverse operation, one routine for the fit quality estimation, and an algorithm for learning the fit parameters. Because the quantum algorithm is mainly based on the HHL algorithm, it suggests an exponential improvement in the case where F is sparse and the condition number (namely, the ratio between the largest and the smallest eigenvalues) of both F F^\dagger and 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 an inner product of a matrix C (given as an input) with the variable X . Denote by \mathbb{S}^n the space of all n \times n symmetric matrices.

The variable X must lie in the (closed convex) cone of positive semidefinite symmetric matrices \mathbb{S}^{n}_+ . The inner product of two matrices is defined as: \langle A,B\rangle_{\mathbb{S}^n} = {\rm tr}(A^T B) = \sum_{i=1,j=1}^n A_{ij}B_{ij}. The problem may have additional constraints (given as inputs), also usually formulated as inner products.

Each constraint forces the inner product of the matrices A_k (given as an input) with the optimization variable X to be smaller than a specified value b_k (given as an input). Finally, the SDP problem can be written as: \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 best classical algorithm is not known to unconditionally run in polynomial time.

The corresponding feasibility problem is known to either lie outside of the union of the complexity classes NP and co-NP, or in the intersection of NP and co-NP.

The quantum algorithm

The algorithm inputs are A_1 ... A_m, C , b_1 ... b_m and parameters regarding the solution's trace, precision and optimal value (the objective function's value at the optimal point). The quantum algorithm consists of several iterations.

In each iteration, it solves a feasibility problem, namely, finds any solution satisfying the following conditions (giving a threshold t ): \begin{array}{lr} \langle C, X \rangle_{\mathbb{S}^n} \leq t \\ \langle A_k, X \rangle_{\mathbb{S}^n} \leq b_k, \quad k = 1,\ldots,m \\ X \succeq 0 \end{array} In each iteration, a different threshold t is chosen, and the algorithm outputs either a solution X such that \langle C, X\rangle_{\mathbb{S}^n} \leq t (and the other constraints are satisfied, too) or an indication that no such solution exists. The algorithm performs a binary search to find the minimal threshold t for which a solution X still exists: this gives the minimal solution to the SDP problem.

Quantum SDP algorithms provide a generic quadratic improvement in certain oracle or query models. For low-rank SDPs, algorithms can have polylogarithmic dependence on the matrix dimension n when the input matrices are supplied in a fully quantum input model, such as quantum states, and when only a succinct or sampled representation of the solution is required.

However, comparable low-rank and sampling-access assumptions also permit quantum-inspired classical algorithms with polylogarithmic dependence on n; therefore, this does not establish a general exponential quantum advantage for low-rank SDPs given explicitly as classical input.

Quantum combinatorial optimization

The combinatorial optimization problem is aimed at finding an optimal object from a finite set of objects. The problem can be phrased as a maximization of an objective function which is a sum of Boolean functions.

Each Boolean function \,C_\alpha \colon \lbrace {0,1 \rbrace}^n \rightarrow \lbrace {0,1} \rbrace gets as input the n -bit string z = z_1 z_2 \ldots z_n and gives as output one bit (0 or 1). The combinatorial optimization problem of n bits and m clauses is finding an n -bit string z that maximizes the function C(z) = \sum_{\alpha=1}^m C_\alpha(z) Approximate optimization is a way of finding an approximate solution to an optimization problem, which is often NP-hard.

The approximated solution of the combinatorial optimization problem is a string z that is close to maximizing C(z) .

Quantum approximate optimization algorithm

For combinatorial optimization, the quantum approximate optimization algorithm (QAOA) briefly had a better approximation ratio than any known polynomial time classical algorithm (for a certain problem), until a more effective classical algorithm was proposed. The relative speed-up of the quantum algorithm is an open research question.

QAOA consists of the following steps: Defining a cost Hamiltonian H_C such that its ground state encodes the solution to the optimization problem. Defining a mixer Hamiltonian H_M . Defining the oracles U_C(\gamma)= \exp(-\imath \gamma H_C) and U_M(\alpha)= \exp(-\imath \alpha H_M) , with parameters \gamma and α.

Repeated application of the oracles U_C and U_M , in the order: U(\boldsymbol\gamma, \boldsymbol\alpha) = \coprod_{i=1}^N (U_C(\gamma_i) U_M(\alpha_i)) Preparing an initial state, that is a superposition of all possible states and apply U(\boldsymbol\gamma, \boldsymbol\alpha) to the state. Using classical methods to optimize the parameters \boldsymbol\gamma, \boldsymbol\alpha and measure the output state of the optimized circuit to obtain the approximate optimal solution to the cost Hamiltonian.

An optimal solution will be one that maximizes the expectation value of the cost Hamiltonian H_C . The layout of the algorithm, viz, the use of cost and mixer Hamiltonians are inspired from the Quantum Adiabatic theorem, which states that starting in a ground state of a time-dependent Hamiltonian, if the Hamiltonian evolves slowly enough, the final state will be a ground state of the final Hamiltonian. Moreover, the adiabatic theorem can be generalized to any other eigenstate as long as there is no overlap (degeneracy) between different eigenstates across the evolution.

Identifying the initial Hamiltonian with H_M and the final Hamiltonian with H_C , whose ground states encode the solution to the optimization problem of interest, one can approximate the optimization problem as the adiabatic evolution of the Hamiltonian from an initial to the final one, whose ground (eigen)state gives the optimal solution. In general, QAOA relies on the use of unitary operators dependent on 2p angles (parameters), where p>1 is an input integer, which can be identified the number of layers of the oracle U(\boldsymbol\gamma, \boldsymbol\alpha) .

These operators are iteratively applied on a state that is an equal-weighted quantum superposition of all the possible states in the computational basis. In each iteration, the state is measured in the computational basis and the Boolean function C(z) is estimated.

The angles are then updated classically to increase C(z) . After this procedure is repeated a sufficient number of times, the value of C(z) is almost optimal, and the state being measured is close to being optimal as well. A sample circuit that implements QAOA on a quantum computer is given in figure.

This procedure is highlighted using the following example of finding the minimum vertex cover of a graph. H_C = -0.25 Z_3 + 0.5 Z_0 + 0.5 Z_1 + 1.25 Z_2 + 0.75 (Z_0 Z_1 + Z_0 Z_2 + Z_2 Z_3 + Z_1 Z_2) H_M = X_0 + X_1 + X_2 + X_3 Implementing QAOA algorithm for this four qubit circuit with two layers of the ansatz in qiskit (see figure) and optimizing leads to a probability distribution for the states given in the figure.

This shows that the states |0110⟩ and |1010⟩ have the highest probabilities of being measured, just as expected.

QAOA algorithm Qiskit implementation

The quantum circuit shown here is from a simple example of how the QAOA algorithm can be implemented in Python using Qiskit, an open-source quantum computing software development framework by IBM.

Implementation of the QAOA algorithm for the knapsack problem with Classiq

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373565978 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.