Quantum optimization algorithms

Short description: Optimization algorithms using quantum computing

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems.[1] 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, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. 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.

## Contents

* 1 Quantum data fitting
* 1.1 Quantum least squares fitting
* 2 Quantum semidefinite programming
* 2.1 The quantum algorithm
* 3 Quantum combinatorial optimization
* 3.1 Quantum approximate optimization algorithm
* 3.2 QAOA for finding the minimum vertex cover of a graph
* 3.3 Generalization of QAOA to constrained combinatorial optimisation
* 3.4 Variations of QAOA
* 4 QAOA algorithm Qiskit implementation
* 5 See also
* 6 References
* 7 External links

## 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 (x1,y1),(x2,y2),...,(xN,yN) and M continuous functions f1,f2,...,fM. The algorithm finds and gives as output a continuous function fλ→ that is a linear combination of fj:

fλ→(x)=∑j=1Mfj(x)λj

In other words, the algorithm finds the complex coefficients λj, and thus the vector λ→=(λ1,λ2,...,λM).

The algorithm is aimed at minimizing the error, which is given by:

E=∑i=1N|fλ→(xi)−yi|2=∑i=1N|∑j=1Mfj(xi)λj−yi|2=|Fλ→−y→|2

where F is defined to be the following matrix:

F=(f1(x1)⋯fM(x1)f1(x2)⋯fM(x2)⋮⋱⋮f1(xN)⋯fM(xN))

The quantum least-squares fitting algorithm[2] makes use of a version of Harrow, Hassidim, and Lloyd's quantum algorithm for linear systems of equations (HHL), and outputs the coefficients λ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[3] in the case where F is sparse and the condition number (namely, the ratio between the largest and the smallest eigenvalues) of both FF† and F†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 𝕊n the space of all n×n symmetric matrices. The variable X must lie in the (closed convex) cone of positive semidefinite symmetric matrices 𝕊+n. The inner product of two matrices is defined as:

⟨A,B⟩𝕊n=tr(ATB)=∑i=1,j=1nAijBij.

The problem may have additional constraints (given as inputs), also usually formulated as inner products. Each constraint forces the inner product of the matrices Ak (given as an input) with the optimization variable X to be smaller than a specified value bk (given as an input). Finally, the SDP problem can be written as:

minX∈𝕊n⟨C,X⟩𝕊nsubject to⟨Ak,X⟩𝕊n≤bk,k=1,…,mX⪰0

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.[4]

### The quantum algorithm

The algorithm inputs are A1...Am,C,b1...bm and parameters regarding the solution's trace, precision and optimal value (the objective function's value at the optimal point).

The quantum algorithm[5] consists of several iterations. In each iteration, it solves a feasibility problem, namely, finds any solution satisfying the following conditions (giving a threshold t):

⟨C,X⟩𝕊n≤t⟨Ak,X⟩𝕊n≤bk,k=1,…,mX⪰0

In each iteration, a different threshold t is chosen, and the algorithm outputs either a solution X such that ⟨C,X⟩𝕊n≤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.

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.

## 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α:{0,1}n->{0,1} gets as input the n-bit string z=z1z2…zn 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)=∑α=1mCα(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)[6] briefly had a better approximation ratio than any known polynomial time classical algorithm (for a certain problem),[7] until a more effective classical algorithm was proposed.[8] The relative speed-up of the quantum algorithm is an open research question.

QAOA consists of the following steps:

1. Defining a cost Hamiltonian HC such that its ground state encodes the solution to the optimization problem.
2. Defining a mixer Hamiltonian HM.
3. Defining the oracles UC(γ)=exp⁡(−ıγHC) and UM(α)=exp⁡(−ıαHM), with parameters γ and α.
4. Repeated application of the oracles UC and UM, in the order: U(γ,α)=∐i=1N(UC(γi)UM(αi))
5. Preparing an initial state, that is a superposition of all possible states and apply U(γ,α) to the state.
6. Using classical methods to optimize the parameters γ,α 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 HC.

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, 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 HM and the final Hamiltonian with HC, 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(γ,α). 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.[9]

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

The goal here is to find a 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.

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-X operations on each node of the graph and they are given by:

HC=−0.25Z3+0.5Z0+0.5Z1+1.25Z2+0.75(Z0Z1+Z0Z2+Z2Z3+Z1Z2)

HM=X0+X1+X2+X3

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

### Generalization of QAOA to constrained combinatorial optimisation

In principle the optimal value of C(z) can be reached up to arbitrary precision, this is guaranteed by the adiabatic theorem[10][11] or alternatively by the universality of the QAOA unitaries.[12] 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 to variables (problem density) placing a limiting restriction on the algorithm's capacity to minimize a corresponding objective function.[13]

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).[14]

In the paper How many qubits are needed for quantum computational supremacy submitted to arXiv,[15] the authors conclude that a QAOA circuit with 420 qubits and 500 constraints would require at least one century to be simulated using a classical simulation algorithm running on state-of-the-art supercomputers so that would be sufficient for quantum computational supremacy.

A rigorous comparison of QAOA with classical algorithms can give estimates on depth p and number of qubits required for quantum advantage. A study of QAOA and MaxCut algorithm shows that p>11 is required for scalable advantage.[16]

### Variations of QAOA

Several variations to the basic structure of QAOA have been proposed,[17] 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:

1. Multi-angle QAOA[18]
2. Expressive QAOA (XQAOA)[19]
3. QAOA+[20]
4. Digitised counteradiabatic QAOA[21]
5. Quantum alternating operator ansatz[22],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.

## QAOA algorithm Qiskit implementation

QAOA quantum circuit

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

## See also

* Adiabatic quantum computation
* Quantum annealing

## References

1. ↑ Moll, Nikolaj; Barkoutsos, Panagiotis; Bishop, Lev S.; Chow, Jerry M.; Cross, Andrew; Egger, Daniel J.; Filipp, Stefan; Fuhrer, Andreas et al. (2018). "Quantum optimization using variational algorithms on near-term quantum devices". Quantum Science and Technology 3 (3): r 030503. doi:10.1088/2058-9565/aab822. Bibcode: 2018QS&T....3c0503M.
2. ↑ Wiebe, Nathan; Braun, Daniel; Lloyd, Seth (2 August 2012). "Quantum Algorithm for Data Fitting". Physical Review Letters 109 (5). doi:10.1103/PhysRevLett.109.050505. PMID 23006156. Bibcode: 2012PhRvL.109e0505W.
3. ↑ Montanaro, Ashley (12 January 2016). "Quantum algorithms: an overview". npj Quantum Information 2 (1). doi:10.1038/npjqi.2015.23. Bibcode: 2016npjQI...215023M.
4. ↑ Ramana, Motakuri V. (1997). "An exact duality theory for semidefinite programming and its complexity implications". Mathematical Programming 77: 129–162. doi:10.1007/BF02614433.
5. ↑ Brandao, Fernando G. S. L.; Svore, Krysta (2016). "Quantum Speed-ups for Semidefinite Programming". arXiv:1609.05537 [quant-ph].
6. ↑ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2014). "A Quantum Approximate Optimization Algorithm". arXiv:1411.4028 [quant-ph].
7. ↑ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2014). "A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem". arXiv:1412.6062 [quant-ph].
8. ↑ Barak, Boaz; Moitra, Ankur; O'Donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John (2015). "Beating the random assignment on constraint satisfaction problems of bounded degree". arXiv:1505.03424 [cs.CC].
9. ↑ Ceroni, Jack (2020-11-18). "Intro to QAOA" (in en). PennyLane Demos. https://pennylane.ai/qml/demos/tutorial_qaoa_intro.
10. ↑ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2014). "A Quantum Approximate Optimization Algorithm". arXiv:1411.4028 [quant-ph].
11. ↑ Binkowski, Lennart; Koßmann, Gereon; Ziegler, Timo; Schwonnek, René (2024). "Elementary proof of QAOA convergence". New Journal of Physics 26 (7): 073001. doi:10.1088/1367-2630/ad59bb. Bibcode: 2024NJPh...26g3001B.
12. ↑ Morales, M. E.; Biamonte, J. D.; Zimborás, Z. (2019-09-20). "On the universality of the quantum approximate optimization algorithm". Quantum Information Processing 19 (9): 291. doi:10.1007/s11128-020-02748-9.
13. ↑ Akshay, V.; Philathong, H.; Morales, M. E. S.; Biamonte, J. D. (2020-03-05). "Reachability Deficits in Quantum Approximate Optimization". Physical Review Letters 124 (9). doi:10.1103/PhysRevLett.124.090504. PMID 32202873. Bibcode: 2020PhRvL.124i0504A.
14. ↑ Marsh, S.; Wang, J. B. (2020-06-08). "Combinatorial optimization via highly efficient quantum walks". Physical Review Research 2 (2). doi:10.1103/PhysRevResearch.2.023302. Bibcode: 2020PhRvR...2b3302M.
15. ↑ Dalzell, Alexander M.; Harrow, Aram W.; Koh, Dax Enshan; La Placa, Rolando L. (2020-05-11). "How many qubits are needed for quantum computational supremacy?". Quantum 4. doi:10.22331/q-2020-05-11-264. ISSN 2521-327X. Bibcode: 2020Quant...4..264D.
16. ↑ Lykov, Danylo; Wurtz, Jonathan; Poole, Cody; Saffman, Mark; Noel, Tom; Alexeev, Yuri (2023). "Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm". npj Quantum Information 9 (1). doi:10.1038/s41534-023-00718-4. Bibcode: 2023npjQI...9...73L.
17. ↑ Blekos, Kostas; Brand, Dean; Ceschini, Andrea; Chou, Chiao-Hui; Li, Rui-Hao; Pandya, Komal; Summer, Alessandro (June 2024). "A Review on Quantum Approximate Optimization Algorithm and its Variants". Physics Reports 1068: 1–66. doi:10.1016/j.physrep.2024.03.002. Bibcode: 2024PhR..1068....1B.
18. ↑ Herrman, Rebekah; Lotshaw, Phillip C.; Ostrowski, James; Humble, Travis S.; Siopsis, George (2022-04-26). "Multi-angle quantum approximate optimization algorithm" (in en). Scientific Reports 12 (1): 6781. doi:10.1038/s41598-022-10555-8. ISSN 2045-2322. PMID 35474081. Bibcode: 2022NatSR..12.6781H.
19. ↑ Vijendran, V; Das, Aritra; Koh, Dax Enshan; Assad, Syed M; Lam, Ping Koy (2024-04-01). "An expressive ansatz for low-depth quantum approximate optimisation". Quantum Science and Technology 9 (2): 025010. doi:10.1088/2058-9565/ad200a. ISSN 2058-9565. Bibcode: 2024QS&T....9b5010V. https://iopscience.iop.org/article/10.1088/2058-9565/ad200a.
20. ↑ Chalupnik, Michelle; Melo, Hans; Alexeev, Yuri; Galda, Alexey (September 2022). "Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer". 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE. pp. 97–103. doi:10.1109/QCE53715.2022.00028. ISBN 978-1-6654-9113-6.
21. ↑ Chandarana, P.; Hegade, N. N.; Paul, K.; Albarrán-Arriagada, F.; Solano, E.; del Campo, A.; Chen, Xi (2022-02-22). "Digitized-counterdiabatic quantum approximate optimization algorithm" (in en). Physical Review Research 4 (1). doi:10.1103/PhysRevResearch.4.013141. ISSN 2643-1564. Bibcode: 2022PhRvR...4a3141C. https://link.aps.org/doi/10.1103/PhysRevResearch.4.013141.
22. ↑ Hadfield, Stuart; Wang, Zhihui; O'Gorman, Bryan; Rieffel, Eleanor; Venturelli, Davide; Biswas, Rupak (2019-02-12). "From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz" (in en). Algorithms 12 (2): 34. doi:10.3390/a12020034. ISSN 1999-4893.
23. ↑ "Solve utility-scale quantum optimization problems". https://learning.quantum.ibm.com/tutorial/quantum-approximate-optimization-algorithm.

## External links

* Implementation of the QAOA algorithm for the knapsack problem with Classiq

* v
* t
* e

Quantum information science

General|

* Quantum computing
* Qubit
* physical vs. logical
* DiVincenzo's criteria
* Quantum information
* Quantum programming
* Quantum processors
* Cloud-based quantum computing
* Timeline of quantum computing

Theorems|

* Bell's theorem
* Gleason's theorem
* Gottesman–Knill theorem
* Holevo's theorem
* Margolus–Levitin theorem
* No-broadcast theorem
* No-cloning theorem
* No-communication theorem
* No-deleting theorem
* No-hiding theorem
* No-teleportation theorem
* PBR theorem
* Quantum threshold theorem

Quantum
communication|

* Quantum capacity
* Classical capacity
* Entanglement-assisted classical capacity
* Quantum channel
* Quantum network
* Quantum cryptography
* Quantum key distribution
* BB84
* SARG04
* Three-stage quantum cryptography protocol
* Quantum teleportation
* Superdense coding
* LOCC
* Entanglement distillation

Quantum algorithms|

* Universal quantum simulator
* Deutsch–Jozsa algorithm
* Grover's algorithm
* Quantum Fourier transform
* Shor's algorithm
* Simon's problem
* Quantum phase estimation algorithm
* Quantum counting algorithm
* Quantum annealing
* Quantum algorithm for linear systems of equations
* Amplitude amplification

Quantum
complexity theory|

* Quantum Turing machine
* EQP
* BQP
* QMA
* PostBQP
* QIP

Quantum
computing models|

* Quantum circuit
* Quantum logic gate
* One-way quantum computer
* cluster state
* Adiabatic quantum computation
* Topological quantum computer

Quantum
error correction|

* Stabilizer codes
* Entanglement-Assisted Quantum Error Correction
* Shor code
* Steane code
* CSS code
* Quantum convolutional codes
* Toric code

Physical
implementations|

| Quantum optics|

* Cavity QED
* Circuit QED
* Linear optical quantum computing
* KLM protocol
* Boson sampling

|

Ultracold atoms|

* Trapped ion quantum computer
* Optical lattice

Spin-based|

* Nuclear magnetic resonance QC
* Kane QC
* Loss–DiVincenzo QC
* Nitrogen-vacancy center

Superconducting
quantum computing|

* Charge qubit
* Flux qubit
* Phase qubit
* Transmon

Software|

* libquantum
* OpenQASM
* Q#
* Qiskit
* IBM Q Experience

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Quantum optimization algorithms. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Quantum_optimization_algorithms&oldid=3988380"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template