Quantum optimization algorithms: Difference between revisions

Revision as of 20:54, 28 August 2024

Revision as of 17:14, 23 September 2024

Line 74:

==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 [[booleanBoolean function]]s. Each booleanBoolean function <math>\,C_\alpha \colon \lbrace {0,1 \rbrace}^n \rightarrow \lbrace {0,1} \rbrace </math> gets as input the <math>n</math>-bit string <math>z = z_1 z_2 \ldots z_n</math> and gives as output one bit (0 or 1). The combinatorial optimization problem of <math>n</math> bits and <math>m</math> clauses is finding an <math>n</math>-bit string <math>z</math> that maximizes the function

:<math>

C(z) = \sum_{\alpha=1}^m C_\alpha(z)

Line 93:

# Using classical methods to optimize the parameters <math>\boldsymbol\gamma, \boldsymbol\alpha</math> 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 <math>H_C</math>.

[[File:QAOAcircuit.png|thumb|457x457px|Sample QAOA ansatz for a three qubit circuit]]

The layout of the algorithm, viz, the use of cost and mixer Hamiltonians are inspired from the [[Quantum Adiabatic Theorem|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 <math>H_M</math> and the final Hamiltonian with <math>H_C</math>, 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 <math> 2p </math> [[angle]]s (parameters), where <math> p>1 </math> is an input integer, which can be identified the number of layers of the oracle <math>U(\boldsymbol\gamma, \boldsymbol\alpha)</math>. 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 booleanBoolean function <math> C(z) </math> is estimated. The angles are then updated classically to increase <math> C(z) </math>. After this procedure is repeated a sufficient number of times, the value of <math> C(z) </math> 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.<ref>{{Cite journal |last=Ceroni |first=Jack |date=2020-11-18 |title=Intro to QAOA |url=https://pennylane.aiundefined/ |journal=PennyLane Demos |language=en}}</ref>

=== QAOA for finding the minimum vertex cover of a graph ===