Quantum optimization algorithms - Revision history

Kvng: layout

2025-03-29T17:39:13Z

layout

← Previous revision		Revision as of 17:39, 29 March 2025
Line 138:		Line 138:
	*[[Adiabatic quantum computation]]		*[[Adiabatic quantum computation]]
	*[[Quantum annealing]]		*[[Quantum annealing]]
			{{clear}}

	== References ==		== References ==

OAbot: Open access bot: arxiv updated in citation with #oabot.

2025-03-03T03:12:07Z

Open access bot: arxiv updated in citation with #oabot.

← Previous revision		Revision as of 03:12, 3 March 2025
Line 121:		Line 121:

	# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>		# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>
	# Expressive QAOA (XQAOA)<ref>{{Cite journal \|last=Vijendran \|first=V \|last2=Das \|first2=Aritra \|last3=Koh \|first3=Dax Enshan \|last4=Assad \|first4=Syed M \|last5=Lam \|first5=Ping Koy \|date=2024-04-01 \|title=An expressive ansatz for low-depth quantum approximate optimisation \|url=https://iopscience.iop.org/article/10.1088/2058-9565/ad200a \|journal=Quantum Science and Technology \|volume=9 \|issue=2 \|pages=025010 \|doi=10.1088/2058-9565/ad200a \|issn=2058-9565}}</ref>		# Expressive QAOA (XQAOA)<ref>{{Cite journal \|last=Vijendran \|first=V \|last2=Das \|first2=Aritra \|last3=Koh \|first3=Dax Enshan \|last4=Assad \|first4=Syed M \|last5=Lam \|first5=Ping Koy \|date=2024-04-01 \|title=An expressive ansatz for low-depth quantum approximate optimisation \|url=https://iopscience.iop.org/article/10.1088/2058-9565/ad200a \|journal=Quantum Science and Technology \|volume=9 \|issue=2 \|pages=025010 \|doi=10.1088/2058-9565/ad200a \|issn=2058-9565\|arxiv=2302.04479 }}</ref>
	# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>		# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>
	# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>		# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>

Quantumop at 05:08, 28 February 2025

2025-02-28T05:08:35Z

← Previous revision		Revision as of 05:08, 28 February 2025
Line 121:		Line 121:

	# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>		# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>
			# Expressive QAOA (XQAOA)<ref>{{Cite journal \|last=Vijendran \|first=V \|last2=Das \|first2=Aritra \|last3=Koh \|first3=Dax Enshan \|last4=Assad \|first4=Syed M \|last5=Lam \|first5=Ping Koy \|date=2024-04-01 \|title=An expressive ansatz for low-depth quantum approximate optimisation \|url=https://iopscience.iop.org/article/10.1088/2058-9565/ad200a \|journal=Quantum Science and Technology \|volume=9 \|issue=2 \|pages=025010 \|doi=10.1088/2058-9565/ad200a \|issn=2058-9565}}</ref>
	# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>		# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>
	# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>		# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>

Kvng: improve recent contribution

2025-02-24T15:11:28Z

improve recent contribution

← Previous revision		Revision as of 15:11, 24 February 2025
Line 130:		Line 130:

	==QAOA algorithm Qiskit implementation==		==QAOA algorithm Qiskit implementation==
⚫	The quantum circuit shown here is from [https://learning.quantum.ibm.com/tutorial/quantum-approximate-optimization-algorithm 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.

	[[File:QAOA quantum circuit.png\|thumb\|QAOA quantum circuit]]		[[File:QAOA quantum circuit.png\|thumb\|QAOA quantum circuit]]

		⚫	The quantum circuit shown here is from a simple example of how the QAOA algorithm can be implemented in Python<ref>{{cite web \|url=https://learning.quantum.ibm.com/tutorial/quantum-approximate-optimization-algorithm \|title=Solve utility-scale quantum optimization problems \|access-date=2025-02-24}}</ref> using [[Qiskit]], an open-source quantum computing software development framework by IBM.

	== See also ==		== See also ==
Line 140:		Line 140:
	== References ==		== References ==
	{{reflist}}		{{reflist}}

	==External links==		==External links==
	* [https://short.classiq.io/qaoa_knapsack Implementation of the QAOA algorithm for the knapsack problem with Classiq]		* [https://short.classiq.io/qaoa_knapsack Implementation of the QAOA algorithm for the knapsack problem with Classiq]

JavaFXpert: Added short section entitled QAOA algorithm Qiskit implementation

2025-02-20T23:05:41Z

Added short section entitled QAOA algorithm Qiskit implementation

← Previous revision		Revision as of 23:05, 20 February 2025
Line 128:		Line 128:

	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.		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.

			==QAOA algorithm Qiskit implementation==
			The quantum circuit shown here is from [https://learning.quantum.ibm.com/tutorial/quantum-approximate-optimization-algorithm 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.

			[[File:QAOA quantum circuit.png\|thumb\|QAOA quantum circuit]]

	== See also ==		== See also ==

Kvng: WP:ADOPTYPO boolean -> Boolean

2024-09-23T17:14:35Z

WP:ADOPTYPO boolean -> Boolean

← Previous revision		Revision as of 17:14, 23 September 2024
Line 74:		Line 74:

	==Quantum combinatorial optimization==		==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~~ function]]s. Each ~~boolean~~ 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		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 function]]s. Each Boolean 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>		:<math>
	C(z) = \sum_{\alpha=1}^m C_\alpha(z)		C(z) = \sum_{\alpha=1}^m C_\alpha(z)
Line 93:		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>.		# 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]]		[[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 ~~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>		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 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 ===		=== QAOA for finding the minimum vertex cover of a graph ===

85.27.138.187: /* Quantum approximate optimization algorithm */ Fixed two typos.

2024-08-28T20:54:55Z

Quantum approximate optimization algorithm: Fixed two typos.

← Previous revision		Revision as of 20:54, 28 August 2024
Line 93:		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>.		# 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]]		[[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) ~~stated~~ gives the optimal ~~solutiond~~. 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>		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 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 ===		=== QAOA for finding the minimum vertex cover of a graph ===

LennartBinkowski: For reference (DOI: 10.1088/1367-2630/ad59bb): Replaced specific publishing date with publishing year

2024-08-15T19:00:49Z

For reference (DOI: 10.1088/1367-2630/ad59bb): Replaced specific publishing date with publishing year

← Previous revision		Revision as of 19:00, 15 August 2024
Line 108:		Line 108:

	=== Generalization of QAOA to constrained combinatorial optimisation ===		=== Generalization of QAOA to constrained combinatorial optimisation ===
	In principle the optimal value of <math> C(z) </math> can be reached up to arbitrary precision, this is guaranteed by the adiabatic theorem<ref>{{cite arXiv\|last1=Farhi\|first1=Edward\|last2=Goldstone\|first2=Jeffrey\|last3=Gutmann\|first3=Sam\|title=A Quantum Approximate Optimization Algorithm\|eprint=1411.4028\|class=quant-ph\|year=2014}}</ref><ref>{{Cite journal\|last1=Binkowski\|first1=Lennart \|last2=Koßmann\|first2=Gereon \|last3=Ziegler\|first3=Timo \|last4=Schwonnek\|first4=René \|~~date~~=2024~~-07-01~~\|title=Elementary proof of QAOA convergence\|journal=New Journal of Physics\|volume=26\|issue=7\|pages=073001\|doi=10.1088/1367-2630/ad59bb\|arxiv=2302.04968 }}</ref> or alternatively by the universality of the QAOA unitaries.<ref>{{Cite journal\|last1=Morales\|first1=M. E. \|last2=Biamonte\|first2=J. D.\|last3=Zimborás\|first3=Z. \|date=2019-09-20\|title=On the universality of the quantum approximate optimization algorithm\|journal=Quantum Information Processing\|volume=19\|issue=9 \|pages=291\|doi=10.1007/s11128-020-02748-9\|arxiv=1909.03123 }}</ref> However, it is an open question whether this can be done in a feasible way.		In principle the optimal value of <math> C(z) </math> can be reached up to arbitrary precision, this is guaranteed by the adiabatic theorem<ref>{{cite arXiv\|last1=Farhi\|first1=Edward\|last2=Goldstone\|first2=Jeffrey\|last3=Gutmann\|first3=Sam\|title=A Quantum Approximate Optimization Algorithm\|eprint=1411.4028\|class=quant-ph\|year=2014}}</ref><ref>{{Cite journal\|last1=Binkowski\|first1=Lennart \|last2=Koßmann\|first2=Gereon \|last3=Ziegler\|first3=Timo \|last4=Schwonnek\|first4=René \|year=2024\|title=Elementary proof of QAOA convergence\|journal=New Journal of Physics\|volume=26\|issue=7\|pages=073001\|doi=10.1088/1367-2630/ad59bb\|arxiv=2302.04968 }}</ref> or alternatively by the universality of the QAOA unitaries.<ref>{{Cite journal\|last1=Morales\|first1=M. E. \|last2=Biamonte\|first2=J. D.\|last3=Zimborás\|first3=Z. \|date=2019-09-20\|title=On the universality of the quantum approximate optimization algorithm\|journal=Quantum Information Processing\|volume=19\|issue=9 \|pages=291\|doi=10.1007/s11128-020-02748-9\|arxiv=1909.03123 }}</ref> However, it is an open question whether this can be done in a feasible way.
	For example, it was shown that QAOA exhibits a strong dependence on the ratio of a problem's [[Constraint (mathematics)\|constraint]] to [[Variable (mathematics)\|variables]] (problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding [[Loss function\|objective function]].<ref name=":0">{{Cite journal\|last1=Akshay\|first1=V.\|last2=Philathong\|first2=H.\|last3=Morales\|first3=M. E. S.\|last4=Biamonte\|first4=J. D.\|date=2020-03-05\|title=Reachability Deficits in Quantum Approximate Optimization\|journal=Physical Review Letters\|volume=124\|issue=9\|pages=090504\|doi=10.1103/PhysRevLett.124.090504\|pmid=32202873\|arxiv=1906.11259\|bibcode=2020PhRvL.124i0504A\|s2cid=195699685}}</ref>		For example, it was shown that QAOA exhibits a strong dependence on the ratio of a problem's [[Constraint (mathematics)\|constraint]] to [[Variable (mathematics)\|variables]] (problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding [[Loss function\|objective function]].<ref name=":0">{{Cite journal\|last1=Akshay\|first1=V.\|last2=Philathong\|first2=H.\|last3=Morales\|first3=M. E. S.\|last4=Biamonte\|first4=J. D.\|date=2020-03-05\|title=Reachability Deficits in Quantum Approximate Optimization\|journal=Physical Review Letters\|volume=124\|issue=9\|pages=090504\|doi=10.1103/PhysRevLett.124.090504\|pmid=32202873\|arxiv=1906.11259\|bibcode=2020PhRvL.124i0504A\|s2cid=195699685}}</ref>

LennartBinkowski: Within the QAOA section: possible degeneracy of classical objective function and hence objective hamiltonian is consistently accounted for by e.g. replacing "the optimal solution" with "an optimal solution"/"optimal solutions". New reference (DOI: 10.1088/1367-2630/ad59bb) is added for convergence of QAOA for degenerate problems.

2024-08-15T18:52:27Z

Within the QAOA section: possible degeneracy of classical objective function and hence objective hamiltonian is consistently accounted for by e.g. replacing "the optimal solution" with "an optimal solution"/"optimal solutions". New reference (DOI: 10.1088/1367-2630/ad59bb) is added for convergence of QAOA for degenerate problems.

78.104.97.27: Typo "Mullti" -> "Multi"

2024-06-22T14:55:29Z

Typo "Mullti" -> "Multi"

← Previous revision		Revision as of 14:55, 22 June 2024
Line 120:		Line 120:
	Several variations to the basic structure of QAOA have been proposed,<ref>{{Cite journal \|last1=Blekos \|first1=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=June 2024 \|title=A Review on Quantum Approximate Optimization Algorithm and its Variants \|journal=Physics Reports \|volume=1068 \|pages=1–66 \|doi=10.1016/j.physrep.2024.03.002\|arxiv=2306.09198 \|bibcode=2024PhR..1068....1B }}</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:		Several variations to the basic structure of QAOA have been proposed,<ref>{{Cite journal \|last1=Blekos \|first1=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=June 2024 \|title=A Review on Quantum Approximate Optimization Algorithm and its Variants \|journal=Physics Reports \|volume=1068 \|pages=1–66 \|doi=10.1016/j.physrep.2024.03.002\|arxiv=2306.09198 \|bibcode=2024PhR..1068....1B }}</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 \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>		# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>
	# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>		# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>
	# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>		# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>

← Previous revision		Revision as of 03:12, 3 March 2025
Line 121:		Line 121:

	# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>		# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>
	# Expressive QAOA (XQAOA)<ref>{{Cite journal \|last=Vijendran \|first=V \|last2=Das \|first2=Aritra \|last3=Koh \|first3=Dax Enshan \|last4=Assad \|first4=Syed M \|last5=Lam \|first5=Ping Koy \|date=2024-04-01 \|title=An expressive ansatz for low-depth quantum approximate optimisation \|url=https://iopscience.iop.org/article/10.1088/2058-9565/ad200a \|journal=Quantum Science and Technology \|volume=9 \|issue=2 \|pages=025010 \|doi=10.1088/2058-9565/ad200a \|issn=2058-9565}}</ref>		# Expressive QAOA (XQAOA)<ref>{{Cite journal \|last=Vijendran \|first=V \|last2=Das \|first2=Aritra \|last3=Koh \|first3=Dax Enshan \|last4=Assad \|first4=Syed M \|last5=Lam \|first5=Ping Koy \|date=2024-04-01 \|title=An expressive ansatz for low-depth quantum approximate optimisation \|url=https://iopscience.iop.org/article/10.1088/2058-9565/ad200a \|journal=Quantum Science and Technology \|volume=9 \|issue=2 \|pages=025010 \|doi=10.1088/2058-9565/ad200a \|issn=2058-9565\|arxiv=2302.04479 }}</ref>
	# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>		# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>
	# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>		# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>

← Previous revision		Revision as of 05:08, 28 February 2025
Line 121:		Line 121:

	# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>		# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>
			# Expressive QAOA (XQAOA)<ref>{{Cite journal \|last=Vijendran \|first=V \|last2=Das \|first2=Aritra \|last3=Koh \|first3=Dax Enshan \|last4=Assad \|first4=Syed M \|last5=Lam \|first5=Ping Koy \|date=2024-04-01 \|title=An expressive ansatz for low-depth quantum approximate optimisation \|url=https://iopscience.iop.org/article/10.1088/2058-9565/ad200a \|journal=Quantum Science and Technology \|volume=9 \|issue=2 \|pages=025010 \|doi=10.1088/2058-9565/ad200a \|issn=2058-9565}}</ref>
	# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>		# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>
	# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>		# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>

← Previous revision		Revision as of 14:55, 22 June 2024
Line 120:		Line 120:
	Several variations to the basic structure of QAOA have been proposed,<ref>{{Cite journal \|last1=Blekos \|first1=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=June 2024 \|title=A Review on Quantum Approximate Optimization Algorithm and its Variants \|journal=Physics Reports \|volume=1068 \|pages=1–66 \|doi=10.1016/j.physrep.2024.03.002\|arxiv=2306.09198 \|bibcode=2024PhR..1068....1B }}</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:		Several variations to the basic structure of QAOA have been proposed,<ref>{{Cite journal \|last1=Blekos \|first1=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=June 2024 \|title=A Review on Quantum Approximate Optimization Algorithm and its Variants \|journal=Physics Reports \|volume=1068 \|pages=1–66 \|doi=10.1016/j.physrep.2024.03.002\|arxiv=2306.09198 \|bibcode=2024PhR..1068....1B }}</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 \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>		# Multi-angle QAOA<ref>{{Cite journal \|last1=Herrman \|first1=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 \|journal=Scientific Reports \|language=en \|volume=12 \|issue=1 \|page=6781 \|doi=10.1038/s41598-022-10555-8 \|issn=2045-2322 \|pmc=9043219 \|pmid=35474081\|arxiv=2109.11455 \|bibcode=2022NatSR..12.6781H }}</ref>
	# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>		# QAOA+<ref>{{Cite book \|last1=Chalupnik \|first1=Michelle \|last2=Melo \|first2=Hans \|last3=Alexeev \|first3=Yuri \|last4=Galda \|first4=Alexey \|chapter=Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer \|date=September 2022 \|title=2022 IEEE International Conference on Quantum Computing and Engineering (QCE) \|chapter-url=https://ieeexplore.ieee.org/document/9951267 \|publisher=IEEE \|pages=97–103 \|doi=10.1109/QCE53715.2022.00028 \|arxiv=2205.01192 \|isbn=978-1-6654-9113-6}}</ref>
	# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>		# Digitised counteradiabatic QAOA<ref>{{Cite journal \|last1=Chandarana \|first1=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 \|page=013141 \|doi=10.1103/PhysRevResearch.4.013141 \|arxiv=2107.02789 \|bibcode=2022PhRvR...4a3141C \|issn=2643-1564}}</ref>

← Previous revision		Revision as of 18:52, 15 August 2024
Line 91:		Line 91:
	# 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>		# 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>
	# Preparing an initial state, that is a superposition of all possible states and apply <math>U(\boldsymbol\gamma, \boldsymbol\alpha)</math> to the state.		# 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>.		# 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]]		[[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 ~~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>		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) stated gives the optimal solutiond. 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 ===		=== QAOA for finding the minimum vertex cover of a graph ===
	The goal here is to find ~~the~~ [[Vertex cover\|minimum vertex cover]] of a graph: a collection of vertices such that each edge in the graph contains at least one of the vertices in the cover. Hence, these vertices “cover” all the edges. We wish to find ~~the~~ vertex cover that has the smallest possible number of vertices. Vertex covers can be represented by a bit string where each bit denotes whether the corresponding vertex is present in the cover. For example, the bit string 0101 represents a cover consisting of the second and fourth vertex in a graph with four vertices.		The goal here is to find a [[Vertex cover\|minimum vertex cover]] of a graph: a collection of vertices such that each edge in the graph contains at least one of the vertices in the cover. Hence, these vertices “cover” all the edges. We wish to find a vertex cover that has the smallest possible number of vertices. Vertex covers can be represented by a bit string where each bit denotes whether the corresponding vertex is present in the cover. For example, the bit string 0101 represents a cover consisting of the second and fourth vertex in a graph with four vertices.
	[[File:GraphforQAOA.png\|thumb\|220x220px\|Sample graph to illustrate the minimum vertex cover problem.]]		[[File:GraphforQAOA.png\|thumb\|220x220px\|Sample graph to illustrate the minimum vertex cover problem.]]
	Consider the graph given in the figure. It has four vertices and there are two minimum vertex cover for this graph: vertices 0 and 2, and the vertices 1 and 2. These can be respectively represented by the bit strings 1010 and 0110. The goal of the algorithm is to sample these bit strings with high probability. In this case, the cost Hamiltonian has two ground states, \|1010⟩ and \|0110⟩, coinciding with the solutions of the problem. The mixer Hamiltonian is the simple, non-commuting sum of [[Pauli matrices\|Pauli-X]] operations on each node of the graph and they are given by:		Consider the graph given in the figure. It has four vertices and there are two minimum vertex cover for this graph: vertices 0 and 2, and the vertices 1 and 2. These can be respectively represented by the bit strings 1010 and 0110. The goal of the algorithm is to sample these bit strings with high probability. In this case, the cost Hamiltonian has two ground states, \|1010⟩ and \|0110⟩, coinciding with the solutions of the problem. The mixer Hamiltonian is the simple, non-commuting sum of [[Pauli matrices\|Pauli-X]] operations on each node of the graph and they are given by:

	<math>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)</math>		<math>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)</math>

	<math>H_M = X_0 + X_1 + X_2 + X_3</math>		<math>H_M = X_0 + X_1 + X_2 + X_3</math>
	[[File:QAOAoutput.png\|thumb\|<nowiki>Output of QAOA implementation in Qiskit for minimum vertex cover problem. Note that the bit string \|1010> is ~~fliped~~ as \|0101> as Qiskit uses reverse ordering of bits.</nowiki>]]		[[File:QAOAoutput.png\|thumb\|<nowiki>Output of QAOA implementation in Qiskit for minimum vertex cover problem. Note that the bit string \|1010> is flipped as \|0101> as Qiskit uses reverse ordering of bits.</nowiki>]]
	[[File:QAOAcircuitforGraph.png\|thumb\|Qiskit implementation of QAOA for minimum vertex cover problem.]]		[[File:QAOAcircuitforGraph.png\|thumb\|Qiskit implementation of QAOA for minimum vertex cover problem.]]
	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.		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.

	=== ~~Generalisation~~ of QAOA to constrained combinatorial optimisation ===		=== Generalization of QAOA to constrained combinatorial optimisation ===
	In principle the optimal value of <math> C(z) </math> can be reached up to arbitrary precision, this is guaranteed by the adiabatic theorem<ref>{{cite arXiv\|last1=Farhi\|first1=Edward\|last2=Goldstone\|first2=Jeffrey\|last3=Gutmann\|first3=Sam\|title=A Quantum Approximate Optimization Algorithm\|eprint=1411.4028\|class=quant-ph\|year=2014}}</ref> or alternatively by the universality of the QAOA unitaries.<ref>{{Cite journal\|last1=Morales\|first1=M. E. \|last2=Biamonte\|first2=J. D.\|last3=Zimborás\|first3=Z. \|date=2019-09-20\|title=On the universality of the quantum approximate optimization algorithm\|journal=Quantum Information Processing\|volume=19\|issue=9 \|pages=291\|doi=10.1007/s11128-020-02748-9\|arxiv=1909.03123 }}</ref> However, it is an open question whether this can be done in a feasible way.		In principle the optimal value of <math> C(z) </math> can be reached up to arbitrary precision, this is guaranteed by the adiabatic theorem<ref>{{cite arXiv\|last1=Farhi\|first1=Edward\|last2=Goldstone\|first2=Jeffrey\|last3=Gutmann\|first3=Sam\|title=A Quantum Approximate Optimization Algorithm\|eprint=1411.4028\|class=quant-ph\|year=2014}}</ref><ref>{{Cite journal\|last1=Binkowski\|first1=Lennart \|last2=Koßmann\|first2=Gereon \|last3=Ziegler\|first3=Timo \|last4=Schwonnek\|first4=René \|date=2024-07-01\|title=Elementary proof of QAOA convergence\|journal=New Journal of Physics\|volume=26\|issue=7\|pages=073001\|doi=10.1088/1367-2630/ad59bb\|arxiv=2302.04968 }}</ref> or alternatively by the universality of the QAOA unitaries.<ref>{{Cite journal\|last1=Morales\|first1=M. E. \|last2=Biamonte\|first2=J. D.\|last3=Zimborás\|first3=Z. \|date=2019-09-20\|title=On the universality of the quantum approximate optimization algorithm\|journal=Quantum Information Processing\|volume=19\|issue=9 \|pages=291\|doi=10.1007/s11128-020-02748-9\|arxiv=1909.03123 }}</ref> However, it is an open question whether this can be done in a feasible way.
	For example, it was shown that QAOA exhibits a strong dependence on the ratio of a problem's [[Constraint (mathematics)\|constraint]] to [[Variable (mathematics)\|variables]] (problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding [[Loss function\|objective function]].<ref name=":0">{{Cite journal\|last1=Akshay\|first1=V.\|last2=Philathong\|first2=H.\|last3=Morales\|first3=M. E. S.\|last4=Biamonte\|first4=J. D.\|date=2020-03-05\|title=Reachability Deficits in Quantum Approximate Optimization\|journal=Physical Review Letters\|volume=124\|issue=9\|pages=090504\|doi=10.1103/PhysRevLett.124.090504\|pmid=32202873\|arxiv=1906.11259\|bibcode=2020PhRvL.124i0504A\|s2cid=195699685}}</ref>		For example, it was shown that QAOA exhibits a strong dependence on the ratio of a problem's [[Constraint (mathematics)\|constraint]] to [[Variable (mathematics)\|variables]] (problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding [[Loss function\|objective function]].<ref name=":0">{{Cite journal\|last1=Akshay\|first1=V.\|last2=Philathong\|first2=H.\|last3=Morales\|first3=M. E. S.\|last4=Biamonte\|first4=J. D.\|date=2020-03-05\|title=Reachability Deficits in Quantum Approximate Optimization\|journal=Physical Review Letters\|volume=124\|issue=9\|pages=090504\|doi=10.1103/PhysRevLett.124.090504\|pmid=32202873\|arxiv=1906.11259\|bibcode=2020PhRvL.124i0504A\|s2cid=195699685}}</ref>