Quantum optimization algorithms are
quantum algorithms
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite se ...
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 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
Mechanics (from Ancient Greek: μηχανική, ''mēkhanikḗ'', "of machines") is the area of mathematics and physics concerned with the relationships between force, matter, and motion among physical objects. Forces applied to object ...
,
economics
Economics () is the social science that studies the production, distribution, and consumption of goods and services.
Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analyzes ...
and
engineering
Engineering is the use of scientific principles to design and build machines, structures, and other items, including bridges, tunnels, roads, vehicles, and buildings. The discipline of engineering encompasses a broad range of more speciali ...
, 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 problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.
Quantum data fitting
Data fitting is a process of constructing a
mathematical function
In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the functi ...
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 as input
data points
and
continuous functions
. The algorithm finds and gives as output a continuous function
that is a
linear combination of
:
:
In other words, the algorithm finds the
complex
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
coefficients
, and thus finds the vector
.
The algorithm is aimed at minimizing the error, which is given by:
:
where we define
to be the following matrix:
:
The quantum least-squares fitting algorithm makes use of a version of Harrow, Hassidim, and Lloyd's
quantum algorithm for linear systems of equations
The quantum algorithm for linear systems of equations, also called HHL algorithm, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, is a quantum algorithm published in 2008 for solving linear systems. The algorithm estimates the result ...
(HHL), and outputs the coefficients
and the fit quality estimation
. 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
is
sparse and the
condition number (namely, the ratio between the largest and the smallest
eigenvalues) of both
and
is small.
Quantum semidefinite programming
Semidefinite programming Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of positive ...
(SDP) is an optimization subfield dealing with the optimization of a linear
objective function
In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...
(a user-specified function to be minimized or maximized), over the intersection of the
cone
A cone is a three-dimensional geometric shape that tapers smoothly from a flat base (frequently, though not necessarily, circular) to a point called the apex or vertex.
A cone is formed by a set of line segments, half-lines, or lines con ...
of
positive semidefinite matrices
In mathematics, a symmetric matrix
In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally,
Because equal matrices have equal dimensions, only square matrices can be symmetric.
The entries of ...
with an
affine space
In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related ...
. The objective function is an
inner product
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often ...
of a matrix
(given as an input) with the variable
. Denote by
the space of all
symmetric matrices. The variable
must lie in the (closed convex) cone of positive semidefinite symmetric matrices
. The inner product of two matrices is defined as:
The problem may have additional constraints (given as inputs), also usually formulated as inner products. Each constraint forces the inner product of the matrices
(given as an input) with the optimization variable
to be smaller than a specified value
(given as an input). Finally, the SDP problem can be written as:
:
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
and parameters regarding the solution's
trace
Trace may refer to:
Arts and entertainment Music
* ''Trace'' (Son Volt album), 1995
* ''Trace'' (Died Pretty album), 1993
* Trace (band), a Dutch progressive rock band
* ''The Trace'' (album)
Other uses in arts and entertainment
* ''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
):
:
In each iteration, a different threshold
is chosen, and the algorithm outputs either a solution
such that
(and the other constraints are satisfied, too) or an indication that no such solution exists. The algorithm performs a
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
to find the minimal threshold
for which a solution
still exists: this gives the minimal solution to the SDP problem.
The quantum algorithm provides a quadratic improvement over the best classical algorithm in the general case, and an exponential improvement when the input matrices are of low
rank
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* ...
.
Quantum combinatorial optimization
The
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
problem is aimed at finding an optimal object from a
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...
of objects. The problem can be phrased as a maximization of an
objective function
In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...
which is a sum of
boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...
s. Each boolean function
gets as input the
-bit string
and gives as output one bit (0 or 1). The combinatorial optimization problem of
bits and
clauses is finding an
-bit string
that maximizes the function
:
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
that is close to maximizing
.
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.
The heart of QAOA relies on the use of
unitary operators
In functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and ...
dependent on
angle
In Euclidean geometry, an angle is the figure formed by two rays, called the '' sides'' of the angle, sharing a common endpoint, called the '' vertex'' of the angle.
Angles formed by two rays lie in the plane that contains the rays. Angles a ...
s, where
is an input integer. 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
is estimated. The angles are then updated classically to increase
. After this procedure is repeated a sufficient number of times, the value of
is almost optimal, and the state being measured is close to being optimal as well.
In 2020, it was shown that QAOA exhibits a strong dependence on the ratio of a problem's
constraint to
variables (problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding
objective function
In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...
.
It was soon recognized that a generalization of the QAOA process is essentially an alternating application of a continuous-time quantum walk on an underlying graph followed by a quality-dependent phase shift applied to each solution state. This generalized QAOA was termed as QWOA (Quantum Walk-based Optimisation Algorithm).
In the paper ''How many qubits are needed for quantum computational supremacy'' submitted to arXiv,
the authors conclude that a QAOA circuit with 420
qubits
In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
and 500
constraints would require at least one century to be simulated using a classical simulation algorithm running on
state-of-the-art supercomputers
A supercomputer is a computer with a high level of performance as compared to a general-purpose computer. The performance of a supercomputer is commonly measured in floating-point operations per second (FLOPS) instead of million instructions p ...
so that would be
sufficient
In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...
for
quantum computational supremacy.
A rigorous comparison of QAOA with classical algorithms can give estimates on depth
and number of qubits required for quantum advantage. A study of QAOA and
MaxCut algorithm shows that
is required for scalable advantage.
See also
*
Adiabatic quantum computation
Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to do calculations and is closely related to quantum annealing.
Description
First, a (potentially complicated) Hamiltonian is found whose g ...
*
Quantum annealing
Quantum annealing (QA) is an optimization process for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states), by a process using quantum fluctuations. Quantum annealing is used mainl ...
References
{{Quantum information
Quantum algorithms