Quantum optimization algorithms: Difference between revisions

Revision as of 23:26, 6 May 2024

Revision as of 19:07, 7 May 2024

Line 89:

# Defining a ''mixer Hamiltonian'' <math>H_M</math>.

# Defining the oracles <math>U_C(\gamma)= \exp(-\imath \gamma H_C)</math> and <math>U_M(\alpha)= \exp(-\imath \alpha H_M)</math>, with parameters <math>\gamma</math> and α.

# Repeated application of the oracles <math>U_C</math> and <math>U_M</math>, in the order: <math>U(\boldsymbol\gamma, \boldsymbol\alpha) = \coprod_{i=1}^N (U_C(\gamma_i) U_M(\alpha_i))</math>

<math>U(\boldsymbol\gamma, \boldsymbol\alpha) = \coprod_{i=1}^N (U_C(\gamma_i) U_M(\alpha_i))</math>

# Preparing an initial state, that is a superposition of all possible states and apply <math>U(\boldsymbol\gamma, \boldsymbol\alpha)</math> to the state.

# 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. The optimal solution will be the one that maximises the expectation value of the cost Hamiltonian <math>H_C</math>.

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

InThe generallayout of the algorithm, viz, the heartuse of cost and mixer Hamiltonians are inspired from the [[Quantum Adiabatic Theorem|Quantum Adiabatic theorem]], which states that starting in the ground state of a time-dependent Hamiltonian, if the Hamiltonian evolves slowly enough, the final state will be the 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 state encodes 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 boolean 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 ===

Line 118 ⟶ 116:

A rigorous comparison of QAOA with classical algorithms can give estimates on depth <math> p </math> and number of qubits required for quantum advantage. A study of QAOA and [[Maximum cut|MaxCut]] algorithm shows that <math>p>11</math> is required for scalable advantage.<ref name="Lykov Wurtz Poole Saffman p. ">{{cite journal | last1=Lykov | first1=Danylo | last2=Wurtz | first2=Jonathan | last3=Poole | first3=Cody | last4=Saffman | first4=Mark | last5=Noel | first5=Tom | last6=Alexeev | first6=Yuri | title=Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm | journal=npj Quantum Information | year=2023 | volume=9 | page=73 | doi=10.1038/s41534-023-00718-4 | arxiv=2206.03579 | bibcode=2023npjQI...9...73L }}</ref>

=== Variations of QAOA ===

Several variations to the basic structure of QAOA have been proposed<ref>{{Cite journal |last=Blekos |first=Kostas |last2=Brand |first2=Dean |last3=Ceschini |first3=Andrea |last4=Chou |first4=Chiao-Hui |last5=Li |first5=Rui-Hao |last6=Pandya |first6=Komal |last7=Summer |first7=Alessandro |date=2024-06 |title=A Review on Quantum Approximate Optimization Algorithm and its Variants |url=http://arxiv.org/abs/2306.09198 |journal=Physics Reports |volume=1068 |pages=1–66 |doi=10.1016/j.physrep.2024.03.002}}</ref>, which include variations to the ansatz of the basic algorithm. The choice of ansatz typically depends on the problem type, such as combinatorial problems represented as graphs, or problems strongly influenced by hardware design. However, ansatz design must balance specificity and generality to avoid overfitting and maintain applicability to a wide range of problems. For this reason, designing optimal ansatze for QAOA is an extensively researched and widely investigated topic. Some of the proposed variants are:

# Mullti-angle QAOA<ref>{{Cite journal |last=Herrman |first=Rebekah |last2=Lotshaw |first2=Phillip C. |last3=Ostrowski |first3=James |last4=Humble |first4=Travis S. |last5=Siopsis |first5=George |date=2022-04-26 |title=Multi-angle quantum approximate optimization algorithm |url=https://www.nature.com/articles/s41598-022-10555-8 |journal=Scientific Reports |language=en |volume=12 |issue=1 |doi=10.1038/s41598-022-10555-8 |issn=2045-2322 |pmc=PMC9043219 |pmid=35474081}}</ref>

# QAOA+<ref>{{Cite journal |last=Chalupnik |first=Michelle |last2=Melo |first2=Hans |last3=Alexeev |first3=Yuri |last4=Galda |first4=Alexey |date=2022-09 |title=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer |url=https://ieeexplore.ieee.org/document/9951267/ |publisher=IEEE |pages=97–103 |doi=10.1109/QCE53715.2022.00028 |isbn=978-1-6654-9113-6}}</ref>

# Digitised counteradiabatic QAOA<ref>{{Cite journal |last=Chandarana |first=P. |last2=Hegade |first2=N. N. |last3=Paul |first3=K. |last4=Albarrán-Arriagada |first4=F. |last5=Solano |first5=E. |last6=del Campo |first6=A. |last7=Chen |first7=Xi |date=2022-02-22 |title=Digitized-counterdiabatic quantum approximate optimization algorithm |url=https://link.aps.org/doi/10.1103/PhysRevResearch.4.013141 |journal=Physical Review Research |language=en |volume=4 |issue=1 |doi=10.1103/PhysRevResearch.4.013141 |issn=2643-1564}}</ref>

# Quantum alternating operator ansatz<ref>{{Cite journal |last=Hadfield |first=Stuart |last2=Wang |first2=Zhihui |last3=O'Gorman |first3=Bryan |last4=Rieffel |first4=Eleanor |last5=Venturelli |first5=Davide |last6=Biswas |first6=Rupak |date=2019-02-12 |title=From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz |url=http://www.mdpi.com/1999-4893/12/2/34 |journal=Algorithms |language=en |volume=12 |issue=2 |pages=34 |doi=10.3390/a12020034 |issn=1999-4893}}</ref>,which allows for constrains on the optimization problem etc.

Another variation of QAOA focuses on techniques for parameter optimization, which aims at selecting the optimal set of initial parameters for a given problem and avoiding barren plateaus, which represent parameters leading to eigenstates which correspond to plateaus in the energy landscape of the cost Hamiltonian.

Finally, there has been significant research interest in leveraging specific hardware to enhance the performance of QAOA across various platforms, such as trapped ion, neutral atoms, superconducting qubits, and photonic quantum computers. The goals of these approaches include overcoming hardware connectivity limitations and mitigating noise-related issues to broaden the applicability of QAOA to a wide range of combinatorial optimization problems.

== See also ==